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 10¹³ (this would require the computation of about 5²² 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

x	pi(x)	k		x	pi(x)	k
102	25	5		103	168	15
104	1,229	35		105	9,592	65
106	78,498	95		107	664,579	135
108	5,761,455	175		109	50,847,534	248
1010	455,052,511	329		1011	4,118,054,813	417
1012	37,607,912,018	481		1013	346,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)

• The gaps between primes

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.