Large Counterexample

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



What can be said about the relative size of E(n) and O(n)? Are there more of one than the ?

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

In 1962, Lehman found a counterexample: at n=906180359, it is the case that O(n)=E(n)-1.

Presentation Suggestions:
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” arguments.

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. <https://www.math.hmc.edu/funfacts>.

References:
H. Stark, An Introduction to , MIT Press, 1987.

Fun Fact suggested by:
Lesley Ward

Did you like this Fun Fact?

Click to rate it.

Average rating 4.5 / 5. Vote count: 8

No votes so far! Be the first to rate this Fun Fact

Share: