Reto:

Dado un número, tome el primo más grande estrictamente menor que él, reste de este número, haga esto nuevamente a este nuevo número con el primo mayor menor que él y continúe haciendo esto hasta que sea menor que 3. Si llega a 1, su el programa debería generar un valor verdadero, de lo contrario, el programa debería generar un valor falso.

Ejemplos:

Todo esto debería dar un valor verdadero:

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

Todo esto debería dar valores falsey:

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

Reglas:

• Puedes escribir un programa o una función.
• Puede suponer que la entrada es mayor que 2.
• Se aplican lagunas estándar
• Este es el código de golf, por lo que gana la respuesta más corta.

Jalea , 9 8 bytes

’ÆRṪạµ¡Ḃ

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo 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$

Impresiones 0(falsedad) o 1(verdad).

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

.+
$*

Convierta la entrada a unario convirtiendo la entrada Nen Ncopias de 1.

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

Repetidamente elimine el primo más grande menos que la entrada. Esto se basa en la prueba de primalidad estándar con regex .

^1$

Comprueba si el resultado es único 1.

Pyth, 18 15 14 bytes

Gracias a @Maltysen por -1 byte

#=-QefP_TUQ)q1

Un programa que toma información sobre STDIN e imprime Trueo Falsesegún corresponda.

Pruébalo en línea

Cómo 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

Versión antigua con reducción, 18 bytes

qu-G*<HGH_fP_TSQQ1

Pruébalo en línea

Cómo 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 gracias 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))

Escribí esto en 2 minutos ... y funcionó perfectamente la primera vez. El primer usuario en encontrar el error inevitable gana ...

Pruébalo

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>

Cómo funciona

Primero definimos g (x) como la función que encuentra el primer número primo p <= x . Esto se realiza mediante el siguiente proceso:

1. Comience con n = x-1 .
2. Si n <2 , x es primo; volver x .
3. Si x es divisible por n , decremente x y vaya al paso 1.
4. De lo contrario, disminuya ny vaya al paso 2.

La solución a este desafío, f (x) , ahora es bastante sencilla:

1. Si x <3 , devuelve x = 1 .
2. De lo contrario, reste g (x-1) e intente nuevamente.

Pyke, 15 11 bytes

WDU#_P)e-Dt

Pruébalo aquí!

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

Devuelve 1si es verdadero y genera una excepción si es falso

Julia, 32 bytes

Si bien no será la solución más corta entre los idiomas, esta podría ser la más corta de las legibles por humanos ...

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

O, para decirlo en términos un poco más 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

Llamado con, por ejemplo !37,.

Mathematica, 32 bytes

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

Esta es una función sin nombre que toma un número entero y devuelve un valor booleano.

Explicación

Aquí hay mucha sintaxis y un orden de lectura divertido, así que ...

   #                               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])

Sugerencias de golf bienvenidas! Veo que gmpycontiene una función next_prime, pero aún no puedo probarla :(

-2 bytes, gracias a @JonathanAllan !

-1 byte, gracias a @Aaron !

Casos de prueba

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)))

La salida es de 13 valores de verdad y 13 valores de falsey. scontiene los casos verdaderos y hlos falseys.

Python, con sympy, 60 bytes

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

Mi método anterior era 83 bytes sin sympy usando recursión, pero tomé verdadero / falso para decir distinguible y consistente, pero me han informado que es una interpretación incorrecta. Parece que no puedo salvarlo debido a la cola, pero lo dejaré aquí en caso de que alguien sepa cómo hacerlo:

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

Esto definitivamente se puede acortar.

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

‮

<                    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);

Pruébalo en línea!

MATL , 13 bytes

`tqZq0)-t2>}o

Pruébalo en línea! O verifique todos los casos de prueba a la vez .

Explicación

`        % 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

Gracias a Dennis por guardar 4 bytes.

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

Pruébalo en línea!

Explicación

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

Incluye +1 para -p

Ejecutar con entrada en STDIN

reach1.pl:

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

Utiliza la clásica regex de primalidad

.NET Regex, 38 bytes

Solo para mostrar que se puede verificar en una sola expresión regular.

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

Se supone que la entrada está en unario.

Explicación

Simplemente implementa el requisito de la palabra, eliminando repetidamente el primo más grande y verifica si el resto es 1.

• (?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: El grupo sin retroceso se asegura de que el mayor prime que encontramos no se anule, y +simplemente repite el proceso de igualar el mayor prime

  • (?<=(.*))..+(?<!^\1\2+(.+.)|$): Coincide con el primo más grande menos que el número restante

    • (?<=(.*)): Registre cuánto hemos restado para establecer un punto de "anclaje" para la afirmación.

    • ..+: Busque el mayor número ...

    • (?<!^\1\2+(.+.)|$): ... que es primo y menor que el número restante.
      • (?<!^\1\2+(.+.)): La rutina de prueba principal habitual, con ^\1tachuelas al frente para asegurarnos de que estamos verificando la cantidad igualada por..+
      • (?!<$): Afirmar menos que el 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}

Explicación:

# 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
}

Ejemplo:

# 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

Creé este lenguaje hace dos días, y las premisas básicas son que no hay bucles integrados, las únicas características son la aritmética básica y la toma de decisiones, y la evaluación del programa se basa en expresiones regulares.

Explicación

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

Esta parte convierte la entrada en unario. Resta repetidamente 1 de la entrada hasta que sea igual a 0, precediendo 1_cada vez. Luego elimina todos los _s. Si no hubiera olvidado un breaken mi código, podría escribirse así:

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

La siguiente parte quita repetidamente la mayor primo desde la entrada hasta que es igual a 1o 11, con 11ser reemplazado con 0.

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

Usé la expresión regular de la respuesta de Martin Ender .

Haskell, 79 bytes

No realmente corto pero sin puntos :)

(<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

Toma entrada $n. Entra en un whileciclo siempre y cuando $nsea 3o mayor. Cada iteración, resta un número de $n. El número es el resultado de la prueba de primalidad regex aplicada contra un rango a ($n-1)..2través del operador Where-Object( ?), luego el primero [0]de los resultados (dado que el rango está disminuyendo, esto da como resultado que se seleccione el más grande). Después de concluir el ciclo, $nva a ser 1o 2, por definición, por lo que decrementamos previamente $n(convirtiéndolo en uno 0o 1), y tomamos el booleano, no del !mismo. Eso queda en la tubería y la salida es implícita.

Ejemplos

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

Esto es MUY similar a la solución JS6 de ETHProductions , pero necesita que la variable esté en el espacio de trabajo.

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

¡Gracias @TuukkaX por -1 byte más!

Floroide , 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)))

Vaya, ese es un código largo. ¡El lenguaje más detallado ataca de nuevo!

Sin golf:

(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))))