Pólya's conjecture states that for any , at least half the numbers up to have an odd number of prime factors, which are counted with multiplicity. Put another way, defining Liouville's summatory function , then holds for all , where is the number of prime factors function. (See A002819 for ).
For example, up to 10, five integers have an odd number of prime factors (2, 3, 5, 7, 8). Going up to 100, there are 51 numbers with an odd number of prime factors, and 507 going up to 1000 (see A212819). Study of small numbers would seem to support the conjecture, as there are no counterexamples below 108.
George Pólya posed the conjecture in 1919. It was refuted in 1958, and the first actual counterexample was found in 1960.
See also: Liouville lambda function.