# Gilbreath's Conjecture

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

• Can I 2-index my input? – Leaky Nun May 14 '17 at 4:32
• @LeakyNun Sure. – isaacg May 14 '17 at 4:56
• Can output use input-based indexing? – Luis Mendo May 14 '17 at 10:23
• @LuisMendo Correct, fixed. No, the indexing must be a constant. – isaacg May 14 '17 at 10:47

# 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.

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

# Pyth, 32 bytes

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


Try it online!

Uses 2-indexing.

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


# 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.

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.

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