Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
my bad! $a(2)< n(2)$ and $a(3)< n(2)$ :) –  fidbc Feb 24 '13 at 20:50

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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