Suponha que comecemos com a 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, ...

Então, tomamos as diferenças 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 o número inicial é 1 toda vez. A conjectura de Gilbreath é a previsão de que esse continua sendo o caso para sempre.

A única maneira de o número inicial deixar de ser um 1 é se o próximo número depois de não ter sido 0 ou 2. A única maneira de o segundo número não ser 0 ou 2 é se o número seguinte não for um 0 0 nem 2. E assim por diante.

O índice do número mais antigo, exceto o 1 inicial, que não é 0 nem 2, nunca pode diminuir em mais de 1 entre um par consecutivo de seqüências. Esse fato foi usado para colocar um limite inferior muito forte quando, se alguma vez, uma sequência pode não ter 1 como o primeiro elemento.

Nesse desafio, você receberá o índice de uma sequência e deverá gerar o índice do primeiro número nessa sequência que não é o 1 inicial e não é 0 ou 2.

Por exemplo, na quarta sequência de diferenças absolutas acima:

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

A primeira entrada que não é zero ou dois, exceto a primeira entrada, é a 15ª posição, 14 zero indexada. Portanto, se a entrada for 4, você produzirá 14.

Para entradas de 1 a 30, as saídas devem 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 é o OEIS A000232 .

Isso pressupõe que você tenha 1 entrada indexada e 0 saída indexada. Você pode indexar suas entradas e saídas a partir de qualquer número inteiro constante, desde que aceite o intervalo de entradas correspondente a todas as seqüências.

Requisitos: sua solução deve ser executada em no máximo 1 minuto em uma entrada de até 30. Se estiver perto o suficiente para depender das especificações do computador, é permitido.

O menor código vence.

Geléia , 17 bytes

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

Experimente online!

A entrada é de 2 indexações. A saída é de 1 indexação.

No TIO, todos os casos de teste totalizam 22,309 s.

Mathematica, 66 bytes

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

Função pura usando um número inteiro positivo como argumento e retornando um número inteiro indexado em 1. Nest[Abs@*Differences,Array[Prime,z+#],#]calcula a #lista de diferenças absolutas iteradas da lista dos primeiros z+#números primos. For[z=1,Last@...<3,z++]faz um loop desse cálculo até que o último elemento da lista resultante seja pelo menos 3e, em seguida, zé gerado. (Observe que a correção do algoritmo assume a conjectura de Gilbreath!)

Pitão , 32 bytes

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

Experimente online!

Usa indexação 2.

MATL , 18 bytes

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

Entrada e saída são baseadas em 1. Leva menos de 40 segundos no TIO para cada um dos casos de teste.

Experimente online!

Explicação

Isso continua tentando seqüências iniciais mais longas de números primos até que as diferenças consecutivas absolutas iteradas dêem pelo menos um valor excedente 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..*)}

Ungolfed:

{   # 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 .. *);
}

Com uma entrada de 30, a função é executada em cerca de quatro segundos no meu modesto laptop.

... que se torna 1,4 segundos após o upgrade da instalação do Perl 6, com sete meses de idade (que também fornece o skipmétodo que me permite cortar vários bytes da minha primeira solução). Todos os casos de teste de 1 a 30 levam cerca de dez 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]]!!)

Experimente online! A última linha é uma função anônima. gLigue para, por exemplo, e chame como g 4. Todos os casos de teste combinados levam menos de 2 segundos no TIO.

Como funciona

[n|n<-[2..],all((>0).mod n)[2..n-1]]gera uma lista infinita de números primos.
f(a:b:r)=abs(a-b):f(b:r)é uma função que produz as diferenças absolutas dos elementos de uma lista infinita. Dado um número n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)aplica-se f ntempos à lista de números primos. length.fst.span(<3)calcula o comprimento do prefixo da lista resultante em que os elementos são menores 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))

ungolf-lo e testar

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]

se não encontrar a solução, expanda a lista principal de 2 * x em um loop e recompute todas as listas restantes. 3 segundos para encontrar g (30)