Supposons que nous commençons par la liste infinie de nombres premiers:

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

Ensuite, nous prenons les différences absolues entre chaque paire de nombres, à plusieurs reprises:

[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, ...

Notez que le premier numéro est 1 à chaque fois. La conjecture de Gilbreath est la prédiction que cela continue d'être le cas pour toujours.

La seule façon dont le premier nombre cesserait d'être un 1 est si le nombre suivant après qu'il ne soit ni un 0 ni un 2. La seule façon que le deuxième nombre ne serait pas un 0 ou un 2 est si le nombre après cela n'était ni un 0 ni un 2. Et ainsi de suite.

L'indice du plus ancien nombre, autre que le premier 1, qui n'est ni un 0 ni un 2, ne peut jamais descendre de plus de 1 entre une paire de séquences consécutives. Ce fait a été utilisé pour mettre une borne inférieure très forte quand, si jamais, une séquence peut ne pas avoir un 1 comme premier élément.

Dans ce défi, vous recevrez l'index d'une séquence et vous devez sortir l'index du premier nombre de cette séquence qui n'est pas le premier 1 et qui n'est ni un 0 ni un 2.

Par exemple, dans la 4ème séquence de différence absolue ci-dessus:

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

La première entrée qui n'est ni un zéro ni un deux, autre que la première entrée, est la 15e position, indexée sur 14 zéros. Donc, si l'entrée était 4, vous produiriez 14.

Pour les entrées de 1 à 30, les sorties doivent être:

[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]

Il s'agit d' OEIS A000232 .

Cela suppose que vous avez 1 entrées indexées et 0 sorties indexées. Vous pouvez indexer vos entrées et sorties à partir de n'importe quel entier constant, tant que vous pouvez accepter la plage d'entrées correspondant à toutes les séquences.

Exigences: Votre solution doit fonctionner au maximum 1 minute sur une entrée pouvant aller jusqu'à 30. Si elle est suffisamment proche pour que cela dépende des spécifications de l'ordinateur, elle est autorisée.

Le code le plus court gagne.

Gelée , 17 octets

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

Essayez-le en ligne!

L'entrée est à 2 indexations. La sortie est à 1 indexation.

Sur TIO, tous les cas de test prennent au total 22.309 s.

Mathematica, 66 octets

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

Fonction pure prenant un entier positif comme argument et retournant un entier indexé sur 1. Nest[Abs@*Differences,Array[Prime,z+#],#]calcule la #e liste de différence absolue itérée de la liste des premiers z+#nombres premiers. For[z=1,Last@...<3,z++]boucle ce calcul jusqu'à ce que le dernier élément de la liste résultante soit au moins 3, puis zest sorti. (Notez que l'exactitude de l'algorithme suppose la conjecture de Gilbreath!)

Pyth , 32 octets

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

Essayez-le en ligne!

Utilise l'indexation 2.

MATL , 18 octets

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

L'entrée et la sortie sont basées sur 1. Il faut moins de 40 secondes en TIO pour chacun des cas de test.

Essayez-le en ligne!

Explication

Cela continue d'essayer des séquences initiales de nombres premiers plus longues jusqu'à ce que les différences absolues consécutives itérées donnent au moins une valeur dépassant 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 octets

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

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

Avec une entrée de 30, la fonction s'exécute en environ quatre secondes sur mon modeste ordinateur portable.

... qui devient 1,4 seconde après la mise à niveau de mon installation Perl 6 vieille de sept mois (ce qui me donne également la skipméthode qui me permet de raser plusieurs octets de ma première solution). Tous les cas de test de 1 à 30 prennent environ dix secondes.

Haskell , 94 octets

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

Essayez-le en ligne! La dernière ligne est une fonction anonyme. Lier par exemple get appeler comme g 4. Tous les cas de test combinés prennent moins de 2 secondes sur TIO.

Comment ça fonctionne

[n|n<-[2..],all((>0).mod n)[2..n-1]]génère une liste infinie de nombres premiers.
f(a:b:r)=abs(a-b):f(b:r)est une fonction donnant les différences absolues des éléments d'une liste infinie. Étant donné un nombre n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)applique des f ntemps à la liste des nombres premiers. length.fst.span(<3)calcule la longueur du préfixe de la liste résultante où les éléments sont plus petits 3.

Axiome, 289 octets

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

dé-golfer et tester

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]

s'il ne trouve pas la solution, développez la liste principale de 2 * x dans une boucle et recalculez toutes les listes restantes. 3 secondes pour trouver g (30)