Sequence A000607 in the Online Encyclopedia of Integer Sequences is the number of partitions of $n$ into prime parts. For example, there are $5$ partitions of $10$ into prime parts: $10 = 2 + 2 + 2 + 2 + 2 = 2 + 2 + 3 + 3 = 2 + 3 + 5 = 3 + 7 = 5 + 5.$ The OEIS gives an asymptotic expression

$$A000607(n) \sim \exp\left(2 \pi \sqrt{\frac{n}{3 \log n}}\right). $$

Numerically, this seems to be wrong even if you take the logarithm of both sides. My conjecture is that

$$\lim_{n \to \infty} \log\left(A000607(n)\right) \bigg/ \left( 2 \pi \sqrt{\frac{n}{3 \log n}} \right) \ne 1.$$

See the following graph:

graph of logarithm of ratio

How might one prove or disprove this conjecture?

For more references please see http://oeis.org/A000607.


1 Answer 1


Your data is compatible with the more refined estimates proved by Vaughan in Ramanujan J. 15 (2008), 109–121. His Theorems 1 and 2 (together with his (1.9)) reveal that $$\log(A000607(n)) = 2 \pi \sqrt{\frac{n}{3 \log n}}\left(1+\frac{\log\log n}{\log n}+O\left(\frac{1}{\log n}\right)\right). $$ For $n=50000$, we have $$\log(A000607(n)) \approx 252.663 $$ $$ 2 \pi \sqrt{\frac{n}{3 \log n}} \approx 246.601$$ $$ 2 \pi \sqrt{\frac{n}{3 \log n}}\left(1+\frac{\log\log n}{\log n}\right)\approx 300.877$$ So if you use the secondary term that is present in Vaughan's formula, the approximation (without the error term) is not below but above the actual value. We also see that in this particular instance the error is $\approx 48.214$, which is very compatible with the fact that the error term above is $O(1)$ times $$ 2 \pi \sqrt{\frac{n}{3 \log n}}\cdot\frac{1}{\log n}\approx 22.792.$$

In short, your conjecture is probably false, while Vaughan is right. The numeric anomaly is caused by a secondary term that is rather large for the $n$'s you considered.

  • 1
    $\begingroup$ Thank you very much, I accept that my conjecture is false and minor asymptotic term is important. $\endgroup$ Sep 15, 2014 at 8:39
  • 1
    $\begingroup$ I didn't check this paper carefully, so I can't say for sure, but arxiv.org/pdf/1609.06497.pdf claims that there is an error in Vaughan's second order term, and that it is $-\frac 12 \frac{\log \log n}{\log n}$, and the constant over $\log n$ term is identified there. At least, the physics paper's answer fits numerics better. $\endgroup$
    – Lucia
    May 24, 2017 at 3:03
  • $\begingroup$ @Lucia: I think the physicists are right! It seems to me that Vaughan has made a simple calculational error in the second display of page 118. The coefficient of $\log\log x$ there should be $+1/2$ instead of $-1$. Hence all the coefficients of $\log\log x/\log x$ in the subsequent displays on this page should be multiplied by $-1/2$, and this corrects Theorem 1 in harmony with the physicists' result. Can you confirm this? If you agree, then I would update my response above and send a message to all authors (mentioning you as well). $\endgroup$
    – GH from MO
    May 24, 2017 at 16:32
  • $\begingroup$ Hi GH: I don't have access to Vaughan's paper at present, and will take a look in a couple of days. I'm sure you're right and it's some simple calculation error. $\endgroup$
    – Lucia
    May 25, 2017 at 1:52
  • $\begingroup$ @Lucia: I can send the paper by email if it helps. Basically, Vaughan is looking at a function $X(x)$ such that $X(x)^2/\log X(x)$ is asymptotically $(6/\pi^2)x$. Then, he deduces that $\log X(x)$ equals $\frac{1}{2}\log x-\log\log x+O(1)$ instead of $\frac{1}{2}\log x+\frac{1}{2}\log\log x+O(1)$. $\endgroup$
    – GH from MO
    May 25, 2017 at 2:19

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.