Finding a counterexample to a Prime Factorization Conjecture

Question

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}$.

Answer 1

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.

Answer 2

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: