Misalkan kita mulai dengan daftar bilangan prima yang tak terbatas:

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

Kemudian, kami mengambil perbedaan absolut antara setiap pasangan angka, berulang kali:

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

Perhatikan bahwa angka yang memimpin adalah 1 setiap kali. Gilbreath's Conjecture adalah prediksi bahwa ini terus menjadi kasus selamanya.

Satu-satunya cara nomor utama berhenti menjadi 1 adalah jika nomor berikutnya setelah bukan 0 atau 2. Satu-satunya cara nomor kedua tidak menjadi 0 atau 2 adalah jika nomor setelah itu bukan merupakan 0 atau 2. Dan seterusnya.

Indeks nomor paling awal, selain dari angka 1 yang terkemuka, yang bukan 0 atau 2, tidak akan pernah bisa turun lebih dari 1 antara pasangan urutan yang berurutan. Fakta ini telah digunakan untuk menempatkan batas bawah yang sangat kuat ketika, jika pernah, suatu urutan mungkin tidak memiliki 1 sebagai elemen pertama.

Dalam tantangan ini, Anda akan diberi indeks urutan, dan Anda harus menampilkan indeks nomor pertama dalam urutan itu yang bukan yang pertama 1, dan bukan 0 atau 2.

Misalnya, dalam urutan perbedaan absolut ke-4 di atas:

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

Entri pertama yang bukan nol atau dua, selain entri pertama, adalah posisi 15, 14 nol diindeks. Jadi jika inputnya adalah 4, Anda akan menghasilkan 14.

Untuk input dari 1 hingga 30, output harus:

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

Ini adalah OEIS A000232 .

Ini dengan asumsi Anda memiliki 1 input terindeks dan 0 output terindeks. Anda dapat mengindeks input dan output Anda mulai dari setiap bilangan bulat konstan, selama Anda dapat menerima kisaran input yang sesuai dengan semua urutan.

Persyaratan: Solusi Anda harus berjalan paling lama 1 menit pada input hingga 30. Jika itu cukup dekat sehingga tergantung pada spesifikasi komputer, itu diperbolehkan.

Kode terpendek menang.

Jelly , 17 byte

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

Cobalah online!

Input adalah pengindeksan 2. Output adalah pengindeksan 1.

Pada TIO, semua testcas total mengambil 22,309 s.

Mathematica, 66 byte

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

Fungsi murni mengambil integer positif sebagai argumen dan mengembalikan integer 1-diindeks. Nest[Abs@*Differences,Array[Prime,z+#],#]menghitung #daftar perbedaan mutlak yang diulang dari daftar z+#bilangan prima pertama . For[z=1,Last@...<3,z++]loop perhitungan ini hingga elemen terakhir dari daftar yang dihasilkan setidaknya 3, dan kemudian zadalah output. (Perhatikan bahwa kebenaran dari algoritma mengasumsikan dugaan Gilbreath!)

Pyth , 32 byte

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

Cobalah online!

Menggunakan pengindeksan 2.

MATL , 18 byte

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

Input dan output berbasis 1. Diperlukan kurang dari 40 detik dalam TIO untuk masing-masing kasus uji.

Cobalah online!

Penjelasan

Ini terus mencoba urutan awal bilangan prima yang lebih lama sampai perbedaan yang berurutan absolut yang diulang memberikan setidaknya satu nilai melebihi 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 byte

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

Tidak Disatukan:

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

Dengan input 30, fungsi berjalan dalam waktu sekitar empat detik pada laptop sederhana saya.

... yang menjadi 1,4 detik setelah memutakhirkan instalasi Perl 6 saya yang berusia tujuh bulan (yang juga memberi saya skipmetode yang memungkinkan saya mengurangi beberapa byte dari solusi pertama saya). Semua uji kasus dari 1 hingga 30 membutuhkan waktu sekitar sepuluh detik.

Haskell , 94 byte

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

Cobalah online! Baris terakhir adalah fungsi anonim. Bind ke eg gdan panggil like g 4. Semua test case yang digabungkan membutuhkan waktu kurang dari 2 detik pada TIO.

Bagaimana itu bekerja

[n|n<-[2..],all((>0).mod n)[2..n-1]]menghasilkan daftar bilangan prima yang tak terbatas.
f(a:b:r)=abs(a-b):f(b:r)adalah fungsi yang menghasilkan perbedaan absolut dari elemen-elemen dari daftar tak terbatas. Diberi nomor n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)berlaku f nkali ke daftar bilangan prima. length.fst.span(<3)menghitung panjang awalan dari daftar yang dihasilkan di mana elemen lebih kecil 3.

Aksioma, 289 byte

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 itu dan uji

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]

jika tidak menemukan solusinya memperluas daftar utama 2 * x dalam satu lingkaran dan menghitung ulang semua daftar yang tersisa. 3 detik untuk menemukan g (30)