2
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user63813 Feb 24 '13 at 23:38
  • $\begingroup$ Unfortunately, no; I tried doing that first, and it was already taking about a minute when going from 1 to 10,000. $\endgroup$ – Zev Chonoles Feb 25 '13 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.