Desafio:

Dado um número, obtenha o maior número primo estritamente menor que ele, subtraia-o desse número, faça-o novamente para esse novo número com o maior número primo menor e continue fazendo isso até que seja menor que 3. Se atingir 1, seu o programa deve gerar um valor verdadeiro; caso contrário, o programa deve gerar um valor falsey.

Exemplos:

Tudo isso deve dar um valor verdadeiro:

3
4
6
8
10
11
12
14
16
17
18
20
22
23
24
26
27
29
30
32
34
35
37
38
40
41
42
44
46
47
48
50

Todos estes devem dar valores falsey:

5
7
9
13
15
19
21
25
28
31
33
36
39
43
45
49

Regras:

• Você pode escrever um programa ou função.
• Você pode assumir que a entrada é maior que 2.
• Aplicam-se brechas padrão
• Isso é código-golfe, então a resposta mais curta vence!

Geléia , 9 8 bytes

’ÆRṪạµ¡Ḃ

Experimente online! ou verifique todos os casos de teste .

Como funciona

’ÆRṪạµ¡Ḃ  Main link. Argument: n

     µ    Combine all atoms to the left into a chain.
’           Decrement; yield n - 1.
 ÆR         Prime range; yield all primes in [2, ..., n -1].
   Ṫ        Tail; yield p, the last prime in the range.
            If the range is empty, this yields p = 0.
    ạ       Compute the absolute difference of p and n.
      ¡   Call the chain to the left n times.
          This suffices since each iteration decreases n, until one of the fixed
          points (1 or 2) is reached.
       Ḃ  Bit; return the parity of the fixed point.

Retina , 31 bytes

.+
$*
+`1(?!(11+)\1+$)11+
1
^1$

Imprime 0(falsy) ou 1(truth).

Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha.)

Explicação

.+
$*

Converta a entrada em unário, transformando a entrada Nem Ncópias de 1.

+`1(?!(11+)\1+$)11+
1

Remova repetidamente o maior número primo menor que a entrada. Isso é baseado no teste de primalidade padrão com regex .

^1$

Verifique se o resultado é único 1.

Pitão, 18 15 14 bytes

Obrigado a @Maltysen por -1 byte

#=-QefP_TUQ)q1

Um programa que recebe entrada no STDIN e imprime Trueou Falseconforme apropriado.

Experimente online

Como funciona

#=-QefP_TUQ)q1  Program. Input: Q
#          )    Loop until error statement (which occurs when Q<3):
         UQ      Yield [0, 1, 2, 3, ..., Q-1]
     fP_T        Filter that by primality
    e            Yield the last element of that
 =-Q             Q = Q - that
            q1  Q is 1 (implicit variable fill)
                Implicitly print

Versão antiga com redução, 18 bytes

qu-G*<HGH_fP_TSQQ1

Experimente online

Como funciona

qu-G*<HGH_fP_TSQQ1  Program. Input: Q
              SQ    Yield [1, 2, 3, ..., Q]
          fP_T      Filter that by primality
         _          Reverse it
 u                  Reduce it:
                Q    with base case Q and
                     function G, H -> 
     <HG              H<G
    *   H             *H (yields H if H<G, else 0)
  -G                  Subtract that from G
q                1  The result of that is 1
                    Implicitly print

JavaScript (ES6), 64 63 bytes

Guardado 1 byte graças a @Neil

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

Escrevi isso em 2 minutos ... e funcionou perfeitamente da primeira vez. Primeiro usuário a encontrar o bug inevitável vence ....

Experimente

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

<input type="number" value=3 min=3 onchange="A.innerHTML=f(this.value)"><br>
<p id=A>1</p>

Como funciona

Primeiro, definimos g (x) como a função que encontra o primeiro número primo p <= x . Isso é feito usando o seguinte processo:

1. Comece com n = x-1 .
2. Se n <2 , x é primo; retornar x .
3. Se x é divisível por n , diminua x e vá para o passo 1.
4. Caso contrário, diminua n e vá para o passo 2.

A solução para esse desafio, f (x) , agora é bastante direta:

1. Se x <3 , retorne x = 1 .
2. Caso contrário, subtraia g (x-1) e tente novamente.

Pyke, 15 11 bytes

WDU#_P)e-Dt

Experimente aqui!

            - stack = input
W           - while continue:
  U#_P)     -     filter(is_prime, range(stack))
       e    -    ^[-1]
 D      -   -   stack-^
         Dt -  continue = ^ != 1

Retorna 1se verdadeiro e gera uma exceção se falso

Julia, 32 bytes

Embora não seja a solução mais curta entre os idiomas, essa pode ser a menor das legíveis por humanos ...

!n=n>2?!(n-primes(n-1)[end]):n<2

Ou, para colocar em termos um pouco mais claros

function !(n)
  if n>2
    m=primes(n-1)[end]   # Gets largest prime less than n
    return !(n-m)        # Recurses
  else
    return n<2           # Gives true if n is 1 and false if n is 2
  end
end

Chamado com, por exemplo !37,.

Mathematica, 32 bytes

2>(#//.x_/;x>2:>x+NextPrime@-x)&

Esta é uma função sem nome que pega um número inteiro e retorna um booleano.

Explicação

Há muita sintaxe e ordem de leitura engraçada aqui, então ...

   #                               This is simply the argument of the function.
    //.                            This is the 'ReplaceRepeated' operator, which applies
                                   a substitution until the its left-hand argument stops
                                   changing.
       x_/;x>2                     The substitution pattern. Matches any expression x as
                                   long as that expression is greater than 2.
              :>                   Replace that with...
                  NextPrime@-x     Mathematica has a NextPrime built-in but no
                                   PreviousPrime built-in. Conveniently, NextPrime
                                   works with negative inputs and then gives you the 
                                   next "negative prime" which is basically a
                                   PreviousPrime function (just with an added minus sign).
                x+                 This gets added to x, which subtracts the previous
                                   prime from it.
2>(                           )    Finally, we check whether the result is less than 2.

Python3, 102 92 90 89 88 bytes

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

Sugestões de golfe são bem-vindas! Vejo que gmpycontém uma função next_prime, mas ainda não posso testá-la :(

-2 bytes, graças a @ JonathanAllan !

-1 byte, graças a @Aaron !

Casos de teste

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

s="3 4 6 8 10 11 12 14 16 17 18 20 22"
h="5 7 9 13 15 19 21 25 28 31 33 36 39"

for j in s.split(" "):print(f(int(j)))
for j in h.split(" "):print(f(int(j)))

A saída é 13 valores reais e 13 valores falsey. scontém os casos hverdadeiros e os falsos.

Python, com sympy, 60 bytes

import sympy
f=lambda n:n>2and f(n-sympy.prevprime(n))or n<2

Meu método anterior era de 83 bytes sem sympy usando recursão, mas entendi truthy / falsey como distinto e consistente, mas fui informado de que é uma interpretação incorreta. Não consigo salvá-lo devido à cauda, ​​mas vou deixá-lo aqui, caso alguém saiba como fazê-lo:

f=lambda n,p=0:n>2and(any(p%x==0for x in range(2,p))and f(n,p-1)or f(n-p,n+~p))or n

Vitsy, 28 26 bytes

Definitivamente, isso pode ser reduzido.

<]xN0)l1)-1[)/3D-];(pD-1[D

O que outras pessoas estão dizendo

<                    Traverse the code in this direction, rotating on the line.
                     For the sake of reading the code easier, I'm reversing the
                     code on this line. This will be the order executed.

 D[1-Dp(;]-D3/)[1-)1l)0Nx]
 D                         Duplicate the top member of the stack.
  [      ]                 Do the stuff in brackets until break is called.
   1-                      Subtract 1 from the top item of the stack.
     D                     Duplicate the top member of the stack.
      p(                   If the top member is a prime...
        ;                  break;
          -                Pop a, b, push a - b.
           D3/)[         ] If this value is less than 3, do the bracketed code.
                1-         Subtract the top item of the stack by 1.
                  )        If the top item is zero...
                   1       Push 1.
                    l)     If the length of the stack is zero...
                      0    Push 0.
                       N   Output the top member of the stack.
                        x  System.exit(0);

Experimente online!

MATL , 13 bytes

`tqZq0)-t2>}o

Experimente online! Ou verifique todos os casos de teste de uma só vez .

Explicação

`        % Do...while
  t      %   Duplicate. Takes input implicitly in the first iteration
  qZq    %   All primes less than that
  0)     %   Get last one
  -      %   Subtract (this result will be used in the next iteration, if any)
  t      %   Duplicate
  2>     %   Does it exceed 2? If so: next iteration. Else: execute the "finally" 
         %   block and exit do...while loop
}        % Finally
  o      %   Parity. Transforms 2 into 0 and 1 into 1
         % End do...while implicitly
         % Display implicitly

CJam , 21 16 bytes

Agradecimentos a Dennis por salvar 4 bytes.

ri{_1|{mp},W=-}h

Experimente online!

Explicação

ri       e# Read input and convert to integer N.
{        e# Run this block as long as N is positive (or until the program aborts
         e# with an error)...
  _1|    e#   Duplicate and OR 1. This rounds up to an odd number. For N > 2, this
         e#   will never affect the greatest prime less than N.
  {mp},  e#   Get all primes from 0 to (N|1)-1.
         e#   For N > 2, this will contain all primes less than N.
         e#   For N = 2, this will contain only 2.
         e#   For N = 1, this will be empty.
  W=     e#   Select the last element (largest prime up to (N|1)-1).
         e#   For N = 1, this will result in an error and terminate the program, which
         e#   still prints the stack contents though (which are 1, the desired output).
  -      e#   Subtract from N. Note that this gives us 0 for N = 2, which terminates the 
         e#   loop.
}h

Perl, 42 bytes

Inclui +1 para -p

Executar com entrada em STDIN

reach1.pl:

#!/usr/bin/perl -p
$_=1x$_;$_=$`while/\B(?!(11+)\1+$|$)|11$/

Usa o regex de primalidade clássico

Regex .NET, 38 bytes

Apenas para mostrar que ele pode ser verificado em um único regex.

^(?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+.$

A entrada é assumida como unária.

Explicação

Ele simplesmente implementa o requisito da palavra, removendo repetidamente o maior número primo e verifica se o restante é 1.

• (?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: O grupo sem backtracking garante que a maior prime encontrada não seja substituída e +simplesmente repita o processo de combinar a maior prime.

  • (?<=(.*))..+(?<!^\1\2+(.+.)|$): Corresponde ao maior número primo menor que o número restante

    • (?<=(.*)): Registre quanto subtraímos para estabelecer um ponto "âncora" para a afirmação.

    • ..+: Procure o maior número ...

    • (?<!^\1\2+(.+.)|$): ... que é primo e menor que o número restante.
      • (?<!^\1\2+(.+.)): A rotina usual de testes principais, com ^\1tachas na frente para garantir que estamos verificando o valor correspondente a..+
      • (?!<$): Afirmar menos que o número restante

Perl 6 ,  54 53 52  51 bytes

{($_,{$_-($_-1...2).first: *.is-prime}...3>*)[*-1]==1}
{($_,{$_-($_-1...2).first: *.is-prime}...3>*).any==1}
{any($_,{$_-($_-1...2).first: *.is-prime}...3>*)==1}

{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}

Explicação:

# bare block lambda with implicit parameter ｢$_｣
# used to generate all of the rest of the elements of the sequence
{
  # create an any Junction of the following list
  any(
    $_, # initialize sequence with the inner block's argument

    # bare block lambda with implicit parameter ｢$_｣
    {
      # take this inner block's argument and subtract
      $_ -

      ( ^$_ )            # Range up-to and excluding ｢$_｣
      .grep(*.is-prime)\ # find the primes
      [ * - 1 ]          # return the last value
    }

    ...   # keep doing that until

    3 > * # the result is less than 3

  # test that Junction against ｢1｣
  # ( returns an ｢any｣ Junction like ｢any(False, False, True)｣ )
  ) == 1
}

Exemplo:

# show what is returned and if it is truthy
sub show ($_) {
  # ｢.&{…}｣ uses the block as a method and implicitly against ｢$_｣
  my $value = .&{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}
  say join "\t", $_, ?$value, $value.gist;
}

show 3;  # 3    True    any(False, True)
show 4;  # 4    True    any(False, True)
show 5;  # 5    False   any(False, False)
show 10; # 10   True    any(False, False, True)
show 28; # 28   False   any(False, False, False)
show 49; # 49   False   any(False, False)
show 50; # 50   True    any(False, False, True)

Irregular , 63 bytes

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n
1(?!(11+)\1+$)11+~1
^11$~0
N

Eu criei esse idioma há dois dias e as premissas básicas são que não existem loops integrados, os únicos recursos são aritmética básica e tomada de decisão, e a avaliação do programa é baseada em expressões regulares.

Explicação

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n

Esta parte converte a entrada em unária. Subtrai repetidamente 1 da entrada até que seja igual a 0, acrescentando 1_cada vez. Em seguida, remove todos os _s. Se eu não tivesse esquecido um breakno meu código, poderia ser escrito da seguinte maneira:

p~?1_$-1p:;
_~
n=i(0)?1_$-1p:;

A próxima parte remove repetidamente o maior número primo da entrada até que seja igual a 1ou 11, 11sendo substituído por 0.

1(?!(11+)\1+$)11+~1
^11$~0
N

Eu usei o regex da resposta de Martin Ender .

Haskell, 79 bytes

Não é realmente curto, mas sem sentido :)

(<2).until(<3)(until(flip(`until`(+1))2.(.)(<1).mod>>=(==))pred.pred>>=flip(-))

PowerShell v2 +, 81 bytes

param($n)while($n-gt2){$n-=(($n-1)..2|?{'1'*$_-match'^(?!(..+)\1+$)..'})[0]}!--$n

Recebe entrada $n. Insere um whileloop desde que $nseja imóvel 3ou maior. Cada iteração subtrai um número de $n. O número é o resultado do teste de primalidade regex aplicado em um intervalo ($n-1)..2via operador Where-Object( ?) e, em seguida, o primeiro [0]dos resultados (como o intervalo está diminuindo, o resultado é o maior selecionado). Depois de concluir o loop, $nele será 1ou 2, por definição, então pré-decréscimo $n(transformando-o em um 0ou em 1) e pegamos o Booleano - não !. Isso é deixado no pipeline e a produção está implícita.

Exemplos

PS C:\Tools\Scripts\golfing> 3..20|%{"$_ --> "+(.\can-the-number-reach-one.ps1 $_)}
3 --> True
4 --> True
5 --> False
6 --> True
7 --> False
8 --> True
9 --> False
10 --> True
11 --> True
12 --> True
13 --> False
14 --> True
15 --> False
16 --> True
17 --> True
18 --> True
19 --> False
20 --> True

Matlab, 51 bytes

v=@(x)x-max(primes(x-1));while(x>=3)x=v(x);end;x==1

Isso é MUITO semelhante à solução JS6 da ETHProductions , mas precisa que a variável esteja no espaço de trabalho.

Python 2.7: 88 87 bytes

r=lambda n:n>2and r(n-[a for a in range(2,n)if all(a%b for b in range(2,a))][-1])or n<2

Thx @TuukkaX por -1 mais byte!

Floróide , 45 30 29 bytes

f=Bb:b<2Fb<3Gf(b-en(b-1)[-1])

Clojure, 125 bytes

#(loop[x %](if(> x 2)(recur(- x(loop[y(dec x)](if(some zero?(vec(for[z(range 2 y)](mod y z))))(recur(dec y))y))))(quot 1 x)))

Caramba, esse é um longo pedaço de código. A linguagem mais detalhada ataca novamente!

Ungolfed:

(defn subprime [n]
  (loop [x n]
    (if (> x 2)
      (recur
        (- x
          (loop [y (dec x)]
            (if (some zero? (vec (for [z (range 2 y)] (mod y z))))
              (recur (dec y)) y))))
      (quot 1 x))))