A # Pólya's conjecture

Pólya's conjecture is a hypothesis put forward by the Hungarian mathematician George Pólya (1887–1985) in 1919. A positive integer is said to be of even type if it factorizes into an even number of prime numbers; otherwise it is said to be of odd type. For example, 4, = 2 × 2, is of even type, whereas 18, = 2 × 3 × 3, is of odd type. Let O(n) be the number of odd type and E(n) be the number of even type integers in the first n integers. Pólya's conjecture says that O(n) > E(n) for all n > 2. After the conjecture had been checked for all values of n up to one million, many mathematicians assumed it was probably true. However, in 1942 English mathematician Albert Ingham came up with an ingenious method to show how a counterexample could be constructed, even though there wasn't enough computing power around at the time to do the necessary calculations.

In 1958, English mathematician Brian Haselgrove used Ingham's method to proved beyond doubt that Pólya's conjecture wasn't true, although he couldn't give any specific value that demonstrated this. The first explicit counterexample – n = 906,180,359 – was announced by American mathematician Sherman Lehman in 1960. Twenty years later, the smallest counterexample, just a tad less than Lehman's number at 906,150,257, was found by Japanese mathematician Minoru Tanaka, and, in fact, it's now known that Pólya's conjecture fails for the majority of numbers between 906,150,257 and 906,488,079.