Gilbreath's Conjecture

Question

Suppose we start with the infinite list of prime numbers:

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

Then, we take the absolute differences between each pair of numbers, repeatedly:

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

Notice that the leading number is 1 every time. Gilbreath's Conjecture is the prediction that this continues to be the case forever.

The only way the leading number would stop being a 1 is if the next number after it was neither a 0 nor a 2. The only way the second number wouldn't be a 0 or a 2 is if the number after that was neither a 0 nor a 2. And so on.

The index of the earliest number, other than the leading 1, which is neither a 0 nor a 2, can never go down by more than 1 between a consecutive pair of sequences. This fact has been used to put a very strong lower bound on when, if ever, a sequence might not have a 1 as the first element.

In this challenge, you will be given the index of a sequence, and you must output the index of the first number in that sequence which is not the leading 1, and is not a 0 or a 2.

For instance, in the 4th absolute difference sequence above:

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

The first entry that's neither a zero or a two, other than the first entry, is the 15th position, 14 zero indexed. So if the input was 4, you would output 14.

For inputs from 1 to 30, the outputs should be:

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

This is OEIS A000232.

This is assuming you have 1 indexed inputs and 0 indexed outputs. You may index your inputs and outputs starting at any constant integers, as long as you can accept the range of inputs corresponding to all sequences.

Requirements: Your solution must run in at most 1 minute on a input of up to 30. If it's close enough that it depends on the computer specs, it's allowed.

Shortest code wins.

Answer 1

Mathematica, 66 bytes

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

Pure function taking a positive integer as argument and returning a 1-indexed integer. Nest[Abs@*Differences,Array[Prime,z+#],#] computes the #th iterated absolute difference list of the list of the first z+# primes. For[z=1,Last@...<3,z++] loops this computation until the last element of the resulting list is at least 3, and then z is output. (Note that the correctness of the algorithm assumes Gilbreath's conjecture!)

Answer 2

Pyth, 32 bytes

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

Try it online!

Uses 2-indexing.

Answer 3

MATL, 18 bytes

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

Input and output are 1-based. It takes less than 40 seconds in TIO for each of the test cases.

Try it online!

Explanation

This keeps trying longer initial sequences of primes until the iterated absolute consecutive differences give at least one value exceeding 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)

Answer 4

Jelly, 17 bytes

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

Try it online!

Input is 2-indexing. Output is 1-indexing.

On TIO all testcases in total take 22.309 s.

Answer 5

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

With an input of 30, the function runs in about four seconds on my modest laptop.

...which becomes 1.4 seconds after upgrading my seven-month-old Perl 6 installation (which also gives me the skip method that lets me shave off several bytes from my first solution). All test cases from 1 to 30 take about ten seconds.

Answer 6

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

Try it online! The last line is an anonymous function. Bind to e.g. g and call like g 4. All test cases combined take less than 2 seconds on TIO.

How it works

[n|n<-[2..],all((>0).mod n)[2..n-1]] generates an infinite list of primes.
f(a:b:r)=abs(a-b):f(b:r) is a function yielding the absolute differences of the elements of an infinite list. Given a number n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!) applies f n times to the list of primes. length.fst.span(<3) computes the length of the prefix of the resulting list where the elements are smaller 3.

Answer 7

Axiom, 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 it and test

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]

it if not find the solution expand the prime list of 2*x in a loop and recompute all the remain lists. 3 seconds for find g(30)