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