Załóżmy, że zaczynamy od nieskończonej listy liczb pierwszych:

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

Następnie kilkakrotnie bierzemy bezwzględne różnice między każdą parą liczb:

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

Zauważ, że wiodącym numerem jest 1 za każdym razem. Domysł Gilbreath jest przewidywaniem, że tak będzie zawsze.

Jedynym sposobem, w jaki numer wiodący przestałby być 1, jest to, że następny numer po nim nie był ani 0, ani 2. Jedynym sposobem, w jaki druga liczba nie byłaby 0 lub 2, jest to, że liczba po nim nie była ani 0 ani 2. I tak dalej.

Indeks najwcześniejszej liczby, innej niż wiodąca 1, która nie jest ani 0, ani 2, nigdy nie może spaść o więcej niż 1 między kolejną parą sekwencji. Fakt ten został wykorzystany do ustalenia bardzo silnej dolnej granicy, gdy, jeśli w ogóle, sekwencja może nie mieć 1 jako pierwszego elementu.

W tym wyzwaniu otrzymasz indeks sekwencji i musisz wypisać indeks pierwszej liczby w tej sekwencji, która nie jest wiodącą 1 i nie jest 0 ani 2.

Na przykład w czwartej sekwencji różnic bezwzględnych powyżej:

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

Pierwszy wpis, który nie jest ani zerem, ani dwójką, inny niż pierwszy wpis, to 15. pozycja, indeksowana zerem 14. Więc jeśli wejście miałoby 4, wyprowadziłbyś 14.

Dla danych wejściowych od 1 do 30 dane wyjściowe powinny być:

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

To jest OEIS A000232 .

Zakłada się, że masz 1 indeksowane dane wejściowe i 0 indeksowane dane wyjściowe. Możesz indeksować swoje wejścia i wyjścia, zaczynając od dowolnej liczby całkowitej, o ile akceptujesz zakres danych wejściowych odpowiadający wszystkim sekwencjom.

Wymagania: Twoje rozwiązanie musi działać najwyżej 1 minutę przy wejściu do 30. Jeśli jest wystarczająco blisko, że zależy od specyfikacji komputera, jest dozwolone.

Najkrótszy kod wygrywa.

Galaretka , 17 bajtów

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

Wypróbuj online!

Dane wejściowe to 2-indeksowanie. Dane wyjściowe to indeksowanie 1.

W przypadku TIO wszystkie przypadki testowe trwają 22.309 s.

Mathematica, 66 bajtów

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

Czysta funkcja przyjmująca dodatnią liczbę całkowitą jako argument i zwracająca liczbę całkowitą zindeksowaną 1. Nest[Abs@*Differences,Array[Prime,z+#],#]oblicza listę #iterowanych różnic bezwzględnych z listy pierwszych z+#liczb pierwszych. For[z=1,Last@...<3,z++]zapętla to obliczenie, dopóki przynajmniej ostatni element wynikowej listy nie będzie 3, a następnie zwyprowadzony. (Zauważ, że poprawność algorytmu zakłada hipotezę Gilbreath!)

Pyth , 32 bajty

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

Wypróbuj online!

Używa 2-indeksowania.

MATL , 18 bajtów

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

Wejścia i wyjścia są oparte na 1. Zajmuje mniej niż 40 sekund w TIO dla każdego z przypadków testowych.

Wypróbuj online!

Wyjaśnienie

Powoduje to próbowanie dłuższych początkowych sekwencji liczb pierwszych, aż iterowane bezwzględne kolejne różnice dadzą co najmniej jedną wartość przekraczającą 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 bajtów

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

Nie golfowany:

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

Przy wejściu 30 funkcja działa na około czterech sekundach na moim skromnym laptopie.

... która staje się 1,4 sekundy po uaktualnieniu mojej siedmiomiesięcznej instalacji Perla 6 (co daje mi również skipmetodę, która pozwala mi zgolić kilka bajtów z mojego pierwszego rozwiązania). Wszystkie przypadki testowe od 1 do 30 zajmują około dziesięciu sekund.

Haskell , 94 bajty

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

Wypróbuj online! Ostatni wiersz jest funkcją anonimową. Powiązać np. gI zadzwonić jakg 4 . Wszystkie połączone przypadki testowe trwają krócej niż 2 sekundy w TIO.

Jak to działa

[n|n<-[2..],all((>0).mod n)[2..n-1]]generuje nieskończoną listę liczb pierwszych.
f(a:b:r)=abs(a-b):f(b:r)jest funkcją dającą bezwzględne różnice elementów nieskończonej listy. Biorąc pod uwagę liczbę n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)stosuje f nrazy na listę liczb pierwszych. length.fst.span(<3)oblicza długość prefiksu wynikowej listy, gdy elementy są mniejsze 3.

Aksjomat, 289 bajtów

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

rozkop go i przetestuj

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]

jeśli nie znajdziesz rozwiązania, rozwiń pierwszą listę 2 * x w pętli i ponownie oblicz wszystkie pozostałe listy. 3 sekundy na znalezienie g (30)