# Finding a counterexample to a Prime Factorization Conjecture

Let $\mathbb{Z}_{\geq 2}$ be the set of natural numbers starting at 2:

$$\mathbb{Z}_{\geq 2}= \{2, 3, 4, 5,\ldots\}.$$

An natural number's prime factorization is odd if the total number of primes in its factorization is odd. It is even if the total number of primes in its factorization is even.

Let $N(k) = \{j \mid j\in \mathbb{Z}_{\geq 2}, j\leq k\text{, the prime factorization for$j$is odd}\}$.
Let $n(k) = |N(k)|$
Let $A(k) = \{j \mid j\in \mathbb{Z}_{\geq 2}, j\leq k\text{, the prime factorization for$j$is even}\}$.
Let $a(k) = |A(k)|$

Conjecture: $n(k) \geq a(k)$ for all prime numbers $k$ in $\mathbb{Z}_{\geq 2}$.

-
my bad! $a(2)< n(2)$ and $a(3)< n(2)$ :) – fidbc Feb 24 '13 at 20:50

This is a slightly modified version of Polya's Conjecture; you are asking for a prime witness to its falsehood. I suspect there is one, but it is probably hard to find. Polya's conjecture is true for most numbers, and the first counterexample is 906,150,257, which is not prime. But there may well be a prime counterexample soon after.

-

The number $906,150,293$ is a counterexample to your conjecture.

Starting from the fact that $m=906,150,257$ is a counterexample to Polya's conjecture, we know that there are more abnormal numbers less than it than there are normal numbers less than it. If we take a number $n$ that is larger than $m$ and there are more abnormal numbers between $m$ and $n$ than there are normal numbers between $m$ and $n$, then we can conclude that there are more abnormal numbers less than $n$ than there are normal numbers less than $n$.

In Mathematica, running

NormalFactorization[n_] := Module[{factorlist}, factorlist = FactorInteger[n];
OddQ[Sum[factorlist[[i]][[2]], {i, 1, Length[factorlist]}]]]

CountNormalLessThan[n_] := Length[Select[normal, # <= n &]]

CountAbnormalLessThan[n_] := Length[Select[abnormal, # <= n &]]

start = 906150257

normal = {}; abnormal = {}; counterexamples = {}; For[n = start, n < start + 100,
n++, If[NormalFactorization[n], AppendTo[normal, n], AppendTo[abnormal, n]]];
For[n = start, n < start + 100, n++, If[CountNormalLessThan[n] <
CountAbnormalLessThan[n] && PrimeQ[n], AppendTo[counterexamples, n]]];
counterexamples


produces

{906150293, 906150341}


Here is a screenshot:

-
What if we didn't know about Polya's conjecture? Could you make the program run from n=2 to n=906150257 without it taking a massive amount of time? – user63813 Feb 24 '13 at 23:38
Unfortunately, no; I tried doing that first, and it was already taking about a minute when going from 1 to 10,000. – Zev Chonoles Feb 25 '13 at 18:39