Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
No subject limitations
Search only in selected subjects
    Calculus or Analysis
    Number Theory
    Other subjects
  Select Difficulty  
Enter keywords 

  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
All rights reserved.

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!

How to Cite this Page:
Su, Francis E., et al. "Large Counterexample." Math Fun Facts. <>.

    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.
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!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

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