Given a number n, how many number of primes are there such that each of them is equal to $$\sum_{k=0}^z p_k $$ where z is some natural number and $p_k$ is nth prime number i.e, $p_0=2$?

For example, if n=20 , there are 2 primes 5,17 , they satisfy the above rules as follows:

5 = 2+ 3

17 = 2 + 3 + 5 + 7

So , is there any formula or any efficient method to identify how many such primes are there below a huge number n?

  • $\begingroup$ How large is $n$? $\endgroup$ – Marcus Andrews Jul 29 '16 at 15:36
  • 1
    $\begingroup$ oeis.org/A013918 should be of interest. $\endgroup$ – Barry Cipra Jul 29 '16 at 15:44
  • $\begingroup$ I'm confused about your use of $n$ and $k$. Assuming $p_k$ is the $k$'th prime, your first sentence contains an $n$ that plays no role... (Though I think you mean to use $n$ as an upper bound.) $\endgroup$ – Daan Michiels Jul 29 '16 at 15:46
  • $\begingroup$ @Marcus Stuhr upto 12billion $\endgroup$ – Pruthvi Raj Jul 29 '16 at 15:47
  • 2
    $\begingroup$ @PruthviRaj, for the number you cite, $12$ billion, the answer can be found in the table linked to at the OEIS entry I mentioned: There are $2182$ primes less than $12$ billion that are the sum of the first $k$ primes for some $k$. Note, however, that the OEIS entry counts $2$ among them, whereas you seem not to. (You point to $5=2+3$ and $17=2+2+5+7$ as the only primes less than $20$ that are the sum of consecutive primes.) If you don't count $2$, then the answer to your question with $12$ billion as the upper bound is $2181$. $\endgroup$ – Barry Cipra Jul 29 '16 at 15:57

A heuristic approach: OEIS A007504 lists the sums of the first primes and says the $k^{\text{th}}$ entry is about $\frac 12k^2\log k$ The maximum $k$ that you allow comes from $\frac 12k^2\log k=n$. We can do one step of fixed point iteration to say $\log k \approx \log \sqrt {2n}, k \approx \sqrt{\frac {2n}{\log \sqrt {2n}}}$. Now if we say the chance of a number $q$ being prime is $\frac 1{\log q}$ we get an approximation up to $n$ that is $$\sum_{i=2}^{\sqrt{\frac {2n}{\log \sqrt {2n}}}}\frac 1{\log( \frac 12i^2\log i)}$$ where I started at $2$ because it blows up at $1$

  • $\begingroup$ unfortunately we will probably never be able to prove it ? I always wondered if there is any chance to prove that a wide class of sequence really have an asymptotic density $\frac{1}{\ln a_n}$ for the primality of its elements $\endgroup$ – reuns Jul 29 '16 at 16:14
  • $\begingroup$ @Ross Millikan , wow thanks , is there anyway to improve it's accuracy?, currently it gives $2168$ for $12billion$ whereas the actual answer should be $2182$ $\endgroup$ – Pruthvi Raj Jul 29 '16 at 16:33
  • $\begingroup$ There are some more terms listed in the OEIS entry and you can do some more iteration to get a better upper limit. If you actually solve $\frac 12k^2 \log k=12E9$ you get an upper limit of 47222 while my approximation gives 44813. That may solve your problem. Using the additional terms gives an upper limit of 45490 per Wolfram Alpha $\endgroup$ – Ross Millikan Jul 29 '16 at 17:36
  • $\begingroup$ Using $45490$ as the upper limit in the above sum gives $2197.61$ per Alpha The approach to asymptotics of prime number things often seems to be rather slow. $\endgroup$ – Ross Millikan Jul 29 '16 at 20:09

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.