Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $X$ denote the largest subset of odd integers with the property that every exponent in the prime factorization of any $x \in X$ belongs to $X$.

The conjecture states that the density of $X$ among the integers is $1-\frac{1}{\sqrt{3}}$.

Is this conjecture correct ?

share|improve this question
Do you have any evidence, or a citation, for this conjecture? At first glance, it seems very unlikely to me that this density would have a simple formula, but that's just a first glance. –  David Speyer Feb 13 '12 at 19:34
I have only experimental evidence for the conjecture. I wrote up a sage program to verify the conjecture for integers up to 20 billon and recovered the probability up to 7 digit of precision. –  Edinah Feb 13 '12 at 20:48
I updated my original response. The new response shows that any $X$ has density at most 0.4226496 which is smaller than $1-1/\sqrt{3}$. –  GH from MO Feb 13 '12 at 21:20
@Edinah: I responded to your criticism below (as a comment to my response). –  GH from MO Mar 24 '12 at 7:59
add comment

2 Answers

up vote 13 down vote accepted

This is an update of my original response which was incorrect.

The conjecture is false. I will show that any $X$ in the conjecture has density at most

$$ 0.4226496 < 1-\frac{1}{\sqrt{3}}= 0.4226497...$$

Let $Y$ be the set of odd numbers whose prime exponents are odd and different from $9$. Clearly, any $X$ in the conjecture is a subset of $Y$. Yet, the density of $Y$ equals

$$ \frac{1}{2}\prod_{p>2}\left(1-\frac{1}{p}\right)\left(1+\frac{1}{p-p^{-1}}-\frac{1}{p^9}\right) $$

which is less than

$$ 0.42264954363092750400907132916 $$

by the SAGE command

(1/2)*prod([RealField(100)(1-1/p)*(1+1/(p-1/p)-1/p^9) for p in prime_range(3,1000000)])
share|improve this answer
Dear GH, Thank you very much for your comment. It took me while to get back to you because I wanted to carefully check everything, I beg to differ. I ran the sage code w can be found at the link www.cs.rutgers.edu/~gnang/sage_code/ The output of the computation can be found in output.txt file and got the density estimate to be for number in the range (1,2^28) to be equal to (1-0.577350318431854)=0.422649681568146 > 0.42264954363092750400907132916 (your estimated upper-bound). I think the issue lies in the fact the estimate fails to account for the recursive nature of the set X. Best, –  Edinah Mar 24 '12 at 1:51
@Edinah: To contradict me you also need to prove that by extending your range $(1,2^{28})$ to all positive integers, your density stays above my claimed upper bound. You cannot prove this simply because my proof is correct. You see, I constructed a set $Y$ which provably contains any $X$, and whose density is provably less than your conjectured $1-1/\sqrt 3$. The density of $Y$ is given by an infinite product over primes with factors in $(0,1)$, so an upper bound for it is given by any finite subproduct. SAGE can calculate the finite product with great precision and falsifies your conjecture. –  GH from MO Mar 24 '12 at 7:56
@GH, I am currently working with Edinah to write a paper on this problem. I was not aware of the fact that this question was posted on this site, and I have independently come to the same conclusions as you have (albeit with a slightly different formula). The conclusions of the paper were all found independently from yours, but we wouldn't want to publish something without first asking if you would like us to acknowledge your disproof (i.e., this post). If you would like to be acknowledged, how so? –  Pat Devlin May 9 '12 at 18:07
@Pat: Thank you. I would like to respond by email. What is your address? –  GH from MO May 10 '12 at 13:00
@Pat: Mail sent. –  GH from MO May 10 '12 at 16:38
add comment

Let $A$ be any set of positive integers such that $1\in A$, and let $B$ be the set of integers such that every exponent in the prime factorization of any $x\in B$ belongs to $A$. Then the density of $B$ exists and equals $$ \prod_{\text{primes }p} \bigg( 1-\frac1p \bigg) \bigg( 1 + \sum_{a\in A} \frac1{p^a} \bigg). $$ In this case, $A=B=X$ (which is kind of cool).

share|improve this answer
add comment

Your Answer


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.