Supongamos que comenzamos con la lista infinita de números primos:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, ...

Luego, tomamos las diferencias absolutas entre cada par de números, repetidamente:

[1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, ...
[1, 0, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 0, 4, 4, 2, ...
[1, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 4, 0, 2, ...
[1, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2, 4, 2, ...

Observe que el número inicial es 1 cada vez. La conjetura de Gilbreath es la predicción de que este seguirá siendo el caso para siempre.

La única forma en que el número inicial dejaría de ser un 1 es si el siguiente número después de que no fuera ni un 0 ni un 2. La única forma en que el segundo número no sería un 0 o un 2 es si el número después de eso no era ni un 0 ni un 2. Y así sucesivamente.

El índice del primer número, que no sea el 1 inicial, que no es ni un 0 ni un 2, nunca puede bajar más de 1 entre un par de secuencias consecutivas. Este hecho se ha utilizado para poner un límite inferior muy fuerte cuando, si alguna vez, una secuencia puede no tener un 1 como primer elemento.

En este desafío, se le dará el índice de una secuencia, y debe generar el índice del primer número en esa secuencia que no es el 1 inicial, y no es un 0 o un 2.

Por ejemplo, en la cuarta secuencia de diferencia absoluta anterior:

[1, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2, 4, 2, ...

La primera entrada que no es un cero o un dos, que no sea la primera entrada, es la posición 15, 14 cero indexado. Entonces, si la entrada era 4, saldría 14.

Para entradas del 1 al 30, las salidas deben ser:

[3, 8, 14, 14, 25, 24, 23, 22, 25, 59, 98, 97, 98, 97, 174, 176, 176, 176, 176, 291, 290, 289, 740, 874, 873, 872, 873, 872, 871, 870]

Este es OEIS A000232 .

Esto supone que tiene 1 entradas indexadas y 0 salidas indexadas. Puede indexar sus entradas y salidas comenzando en cualquier número entero constante, siempre que pueda aceptar el rango de entradas correspondiente a todas las secuencias.

Requisitos: su solución debe ejecutarse como máximo 1 minuto con una entrada de hasta 30. Si está lo suficientemente cerca como para depender de las especificaciones de la computadora, está permitido.

El código más corto gana.

Jalea , 17 bytes

ÆNạ2\Ḋ¿Ḣ’Ị
R‘ÇпL

Pruébalo en línea!

La entrada es de 2 índices. La salida es 1 indexación.

En TIO, todos los casos de prueba en total toman 22.309 s.

Mathematica, 66 bytes

(For[z=1,Last@Nest[Abs@*Differences,Array[Prime,z+#],#]<3,z++];z)&

Función pura que toma un entero positivo como argumento y devuelve un entero indexado 1. Nest[Abs@*Differences,Array[Prime,z+#],#]calcula la #lista de diferencia absoluta iterada de la lista de los primeros z+#números primos. For[z=1,Last@...<3,z++]realiza un bucle de este cálculo hasta que el último elemento de la lista resultante es al menos 3, y luego zsale. (¡Tenga en cuenta que la corrección del algoritmo supone la conjetura de Gilbreath!)

Pyth , 32 bytes

-l.W>3h.WtHaVZtZ>QH+ZfP_TheZ.fP_

Pruébalo en línea!

Utiliza 2-indexación.

MATL , 18 bytes

`@:YqG:"d|]3<A}@G-

La entrada y la salida están basadas en 1. Se tarda menos de 40 segundos en TIO para cada uno de los casos de prueba.

Pruébalo en línea!

Explicación

Esto sigue probando secuencias iniciales más largas de primos hasta que las diferencias consecutivas absolutas iteradas den al menos un valor superior 2.

`        % Do... while loop
  @:Yq   %   Array of first k primes, where k is iteration index
  G:"    %   Do this as many times as the input
    d|   %     Absolute value of consecutive differences
  ]      %   End
  3<A    %   Are they all less than 3? This is the loop condition
}        % Finally (execute before exiting loop)
  @G-    %   Push last iteration index minus input. This is the output
         % End (implicit). Continue with next iteration if top of stack is true
         % Display (implicit)

Perl 6 , 136 120 bytes

{->\i,\n{i??&?BLOCK(i-1,lazy
n.rotor(2=>-1).map: {abs .[1]-.[0]})!!1+n.skip.first:
:k,none 0,2}($_,grep &is-prime,2..*)}

Sin golf:

{   # Anonymous function with argument in $_
    sub f(\i, \n) {  # Recursive helper function
        if i != 0 {  # If we're not done,
            # Recurse on the absolute differences between adjacent entries:
            f(i - 1, lazy n.rotor(2 => -1).map: { abs .[1] - .[0] });
        } else {
            # Otherwise, return the first index after 0
            # where the value is neither 0 nor 2.
            1 + n.skip.first: :k, none 0, 2;
        }
    }
    # Call the helper function with the argument passed to the top-level
    # anonymous function (the recursion depth), and with the prime numbers
    # as the initial (infinite, lazy) list:
    f($_, grep &is-prime, 2 .. *);
}

Con una entrada de 30, la función se ejecuta en aproximadamente cuatro segundos en mi modesta computadora portátil.

... que se convierte en 1,4 segundos después de actualizar mi instalación de Perl 6 de siete meses (que también me da el skipmétodo que me permite eliminar varios bytes de mi primera solución). Todos los casos de prueba del 1 al 30 tardan unos diez segundos.

Haskell , 94 bytes

f(a:b:r)=abs(a-b):f(b:r)
length.fst.span(<3).(iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)

Pruébalo en línea! La última línea es una función anónima. Ate a eg gy llame como g 4. Todos los casos de prueba combinados toman menos de 2 segundos con TIO.

Cómo funciona

[n|n<-[2..],all((>0).mod n)[2..n-1]]genera una lista infinita de primos.
f(a:b:r)=abs(a-b):f(b:r)es una función que produce las diferencias absolutas de los elementos de una lista infinita. Dado un número n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)aplica f ntiempos a la lista de primos. length.fst.span(<3)calcula la longitud del prefijo de la lista resultante donde los elementos son más pequeños 3.

Axioma, 289 bytes

g(n:PI):PI==(k:=n*10;c:List NNI:=[i for i in 1..(k quo 2)|prime?(i)];repeat(a:=concat(c,[i for i in (k quo 2+1)..k|prime?(i)]);j:=0;c:=a;repeat(j=n=>break;j:=j+1;b:=a;a:=[abs(b.(i+1)-b.i)for i in 1..(#b-1)]);j:=2;repeat(j>#a=>break;a.j~=2 and a.j~=1 and a.j~=0=>return j-1;j:=j+1);k:=k*2))

deshazte de él y prueba

f(n:PI):PI==
  k:=n*10
  c:List NNI:=[i for i in 1..(k quo 2)|prime?(i)]
  repeat
    a:=concat(c,[i for i in (k quo 2+1)..k|prime?(i)])
    j:=0;c:=a
    repeat
       j=n=>break
       j:=j+1
       b:=a
       a:=[abs(b.(i+1)-b.i)  for i in 1..(#b-1)]
    j:=2
    repeat
       j>#a=>break
       a.j~=2 and a.j~=1 and a.j~=0 => return j-1
       j:=j+1
    k:=k*2

(4) -> [g(i)  for i in 1..30]
   (4)
   [3, 8, 14, 14, 25, 24, 23, 22, 25, 59, 98, 97, 98, 97, 174, 176, 176, 176,
    176, 291, 290, 289, 740, 874, 873, 872, 873, 872, 871, 870]

si no encuentra la solución, expanda la lista principal de 2 * x en un bucle y vuelva a calcular todas las listas restantes. 3 segundos para encontrar g (30)