Gilbreath's conjecture

In 1958, Norman O. Gilbreath was doodling on a napkin.  He started by writing down the first few primes:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Under these he put their differences:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, ...

Under these he put the unsigned difference of the differences.  And he continued this process of finding iterated differences:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, ...
1, 0, 2, 2, 2, 2, 2, 2, 4, ...
1, 2, 0, 0, 0, 0, 0, 2, ...
1, 2, 0, 0, 0, 0, 2, ...
1, 2, 0, 0, 0, 2, ...
1, 2, 0, 0, 2, ...
1, 2, 0, 2, ...
1, 2, 2, ...
1, 0, ...
1, ...

Gilbreath's Conjecture is that the numbers in the first column are all one (after the initial two).  Two of Gilbreath's students verified this conjecture for the first 64,419 rows.  Since then it has been checked to higher and higher limits, and continues to hold.  For example, by 1993 Andrew Odlyzko had checked this conjecture using the primes up to 10,000,000,000,000 (that is 346,065,536,839 rows)!

As if often the case, Gilbreath was not the first to look at the conjecture that bears his name.  Proth claimed to have proven this result in 1878, but his proof turned out to be faulty.

How do we check this conjecture?  Certainly Odlyzko did not check all iterated differences for all of the primes up to 1013 (this would require the computation of about 522 numbers)!  To understand what he did do, first notice that the first number in each row of differences must be odd (because 2 is the only even prime).  Also, if the row starts with a 1 and then n entries which are either 0 or 2, then the next n rows must start with a one.  So Odlyzko looked for a row that began with a 1 and enough 0's or 2's to complete his work.  For this he only needed to complete the first 635 rows.  (Check his article for other ways to speed this process up.)

Smallest k for which the first pi(x) (the number of primes less than or equal to x) entries in the kth row are 0, 1 or 2
xpi(x) k x pi(x)k
102255   10316815
1041,22935   1059,59265
10678,498 95   107664,579 135
1085,761,455 175   10950,847,534 248
1010455,052,511 329   10114,118,054,813 417
101237,607,912,018 481   1013346,065,536,839 635

Richard Guy suggests that there is nothing special about the sequence of primes, that it is just the fact the the primes grow slowly and are reasonably distributed.  Perhaps if we knew enough about the maximal gaps between primes, or about the distribution of these gaps, then we could complete the proof.

Related pages (outside of this work)

References:

Guy94
R. K. Guy, Unsolved problems in number theory, Springer-Verlag, 1994.  New York, NY, ISBN 0-387-94289-0. MR 96e:11002 [An excellent resource! Guy briefly describes many open questions, then provides numerous references. See his newer editions of this text.]
Odlyzko93
A. M. Odlyzko, "Iterated absolute values of differences of consecutive primes," Math. Comp., 61 (1993) 373-380.  MR 93k:11119 (Abstract available)
Proth1878
F. Proth, "Théorèmes sur les nombres premiers," C. R. Acad. Sci. Paris, 85 (1877) 329-331.
Printed from the PrimePages <t5k.org> © Reginald McLean.