hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Medium level:

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

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 is false!

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!

Su, Francis E., et al. "Large Counterexample." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

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

Keywords:    number theory
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Lesley Ward
Suggestions? Use this form.
3.74
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!