{"id":483,"date":"2019-06-29T21:59:24","date_gmt":"2019-06-29T21:59:24","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=483"},"modified":"2019-12-03T19:27:23","modified_gmt":"2019-12-03T19:27:23","slug":"large-counterexample","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/large-counterexample\/","title":{"rendered":"Large Counterexample"},"content":{"rendered":"\n

A positive integer is said to be of\u00a0even type<\/em>\u00a0if its factorization into\u00a0primes\u00a0has an even number of primes. Otherwise it is said to be of\u00a0odd type<\/em>. 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.)<\/p>\n\n\n\n

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?<\/p>\n\n\n\n

Perhaps O(n) >= E(n) for all n>=2? After all, products of primes come “before” products of two primes…<\/p>\n\n\n\n

This statement is known as Polya’s conjecture<\/em>, 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!<\/p>\n\n\n\n

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

Presentation\u00a0Suggestions:<\/strong>
Students may be able to come up with a\u00a0conjecture\u00a0if you start with some examples. You may wish to make the conjecture more plausible with some other “heuristic” arguments.<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
This example drives home the point that “obvious” facts, checked for many cases, to not constitute a proof for all integers!<\/p>\n\n\n\n

How to Cite this Page:<\/strong> 
Su, Francis E., et al. “Large Counterexample.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
H. Stark, An Introduction to Number Theory, MIT Press, 1987.<\/p>\n\n\n\n

Fun Fact suggested by: <\/strong>
Lesley Ward <\/p>\n","protected":false},"excerpt":{"rendered":"

A positive integer is said to be of\u00a0even type\u00a0if its factorization into\u00a0primes\u00a0has an even number of primes. Otherwise it is...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[4,10,12],"class_list":["post-483","page","type-page","status-publish","hentry","tag-medium","tag-numtheory","tag-other"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/483","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=483"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/483\/revisions"}],"predecessor-version":[{"id":1507,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/483\/revisions\/1507"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=483"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=483"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}