A positive integer is said to be of even type
if its factorization into primes
has an even number of primes.
Otherwise it is said to be of odd type.
Examples: 4=2*2 is even type, 18=2*3*3 is odd type.
(We say 1 has 0 primes and is therefore of even type.)
Let E(n)= the number of positive integers <= of even type.
Let O(n)= the number of positive integers <= n of odd type.
What can be said about the relative size of E(n) and O(n)?
Are there more of one than the other?
Perhaps O(n) >= E(n) for all n>=2? After all, products of
primes come "before" products of two primes...
This statement is known as Polya's conjecture,
and dates back from 1919. After it was checked for all
n <= a million, many people believed it had to be true.
But a belief is not a proof... and in fact the conjecture
In 1962, Lehman found a counterexample:
at n=906180359, it is the case that O(n)=E(n)-1.
Students may be able to come up with a conjecture
if you start with some examples. You may wish to make
the conjecture more plausible with some other "heuristic"
The Math Behind the Fact:
This example drives home the point that "obvious"
facts, checked for many cases, to not constitute
a proof for all integers!
How to Cite this Page:
Su, Francis E., et al. "Large Counterexample."
Math Fun Facts.