Let a primeven be a positive integer that is the product of an even number of primes. Let a primeodd be a positive integer that is the product of an odd number of primes. Then, 1 is a primeven because it is the product of 0 primes. 2 is a primeodd because it is the product of 1 prime. 3 is a primeodd because it is the product of 1 prime. 4 is a primeven because it is the product of 2 primes. Here are the first 10 positive integers.

Number:   Factorization:      Number of primes:   Type:
1                             0                   primeven
2         2                   1                   primeodd
3         3                   1                   primeodd
4         2*2                 2                   primeven
5         5                   1                   primeodd
6         2*3                 2                   primeven
7         7                   1                   primeodd
8         2*2*2               3                   primeodd
9         3*3                 2                   primeven
10        2*5                 2                   primeven

Suppose the primevens and primeodds had a race. First, the primevens would be ahead because 1 is a primeven. Then, there would be a tie because 2 is a primeodd. Then, the primeodds would be ahead because 3 is a primeodd. Then, there would be a tie because 4 is a primeven. Here are the winners from 1 to 10.

Number:   Type:          Primevens:     Primeodds:     Winner:
1         primeven       1              0              primevens
2         primeodd       1              1              tie
3         primeodd       1              2              primeodds
4         primeven       2              2              tie
5         primeodd       2              3              primeodds
6         primeven       3              3              tie
7         primeodd       3              4              primeodds
8         primeodd       3              5              primeodds
9         primeven       4              5              primeodds
10        primeven       5              5              tie

The primevens were ahead at the start, but have not been ahead since then. Do the primevens ever become the winner again?

OEIS A008836: 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, ...
"Liouville's function lambda(n) = (-1)^k, where k is number of primes dividing n (counted with multiplicity)."

Basically, 1 = n is primeeven and -1 = n is primeodd.

OEIS A02819: 0, 1, 0, -1, 0, -1, 0, -1, -2, -1, 0, ...
"Liouville's function L(n) = partial sums of A008836."

This is positive when primeevens are in the lead, negative when primeodds are in the lead, and 0 when tied.

In the comments:
"George Polya conjectured in 1919 that L(n) <= 0 for all n >= 2. .... In 1980, M. Tanaka discovered that the smallest counterexample of the Polya conjecture occurs when n = 906150257."

Charlie successfully verified this result.  Congratulations.

Posted by Brian Smith on 2016-01-12 11:23:22