# How often is a sum of $k$ consecutive primes also prime?

Let's define a $k$-sum as a sum of $k$ consecutive primes. For example, $15=3+5+7$ is a $3$-sum. How many $k$-sums are themselves prime? Here's one way to formulate the question more precisely: What is a simple formula $f_k(x)$ such that the number of prime $k$-sums less than $x$ is $\sim f_k(x)$?

Here's some handwaving. The number of primes less than $x$ is $\pi(x)\sim\frac{x}{\ln x}$, so the number of $k$-sums less than $x$ is $$n_k(x)\sim\pi(x/k)\sim\frac{x/k}{\ln(x/k)}=\frac{x}{k\ln x - k\ln k}\sim\frac{x}{k\ln x}.$$

If the primes and $k$-sums are totally uncorrelated (?), then the number of prime $k$-sums should be something like $$\pi_k(x)\sim\frac{\pi(x)n_k(x)}{x}\sim\frac{x}{k(\ln x)^2}?$$

But that's not right, because all $k$-sums (except the first) have the same parity as $k$. So for $k$ even, $\pi_k(x)\sim 0$, whereas for $k$ odd, we should multiply the above guess by 2: $$\pi_k(x)\sim\frac{2x}{k(\ln x)^2}?$$

There are just naive heuristics, and I don't know how to go further. Do you?

Bonus questions: Roughly how large is the first prime $k$-sum, as a function of $k$? What are the statistics for primes that are $k$-sums for at least $n$ different values of $k>1$? For example, $863$ is a $k$-sum for $3$ values of $k$: $5$, $7$, and $15$.

(This is a followup question to "What does this music video teach us about 863?")

Edit: Note that Project Euler problem 50 also asks about large prime sums of consecutive primes. I haven't seen any link to theory, though.

-
I don't think $n_k(x) \sim \pi(x/k)$. Consider $k=2$. There is a 2-sum that starts with every prime, so $n_2(x)$ is equal to $\pi(x)-1$, isn't it? Every prime less than $x$ starts a 2-sum, except for the last prime less than $x$. I'm assuming you want all primes in your $k$-sum to be less than $x$ when counting them with $n_k(x)$. If not, then $n_k(x)=\pi(x)$. Have you tried any calculations to support your heuristic claims? – Matthew Conroy Dec 27 '13 at 18:31
@MatthewConroy I'm defining $n_2(x)$ to be the number of $2$-sums less than $x$, not the number of $2$-sums whose starting term is less than $x$. For example, $n_2(6)=1$ because there is only one $2$-sum less than $6$, namely $5=2+3$. By contrast, $\pi(6)=3$. I haven't calculated my own statistics, but the formula is in the ballpark with Lucian's value for $n_{15}(10^5)=168$ in the linked question. – Chris Culter Dec 27 '13 at 18:38
Thanks for helping me see your question correctly. Why not calculate your own statistics? $10^5$ is awfully small. Cheers! – Matthew Conroy Dec 27 '13 at 18:41
@MatthewConroy I've no excuse. :) Anyway, whether or not the statistics confirm my guesses, I wouldn't know where to go from there. – Chris Culter Dec 27 '13 at 18:56
Have you tried a literature search? There are many papers related to sums of prime. One in particular: R. C. Vaughn, On the number of partitions into primes, Ramanujan Journal, 15 (2008) no. 1, 109-121. Also, see mathoverflow.net/questions/69680/… These may not deal with general sums, or with consecutive primes, but they are some excellent technical results. – Matthew Conroy Dec 27 '13 at 19:13

Heuristics suggest the asymptotics are $2C \pi(\pi(x/k)) \sim \frac{2Cx}{k (\ln x)^2}$ where $C$ is a constant correction factor to account for the bias in distribution of $k$-sums. The fraction of $k$-sums that are nonzero mod $p$ is slightly larger than in the uniform distribution if $k$ is odd, and slightly smaller if $k$ is even (which would cause similar correction factors in questions like when is half the sum of $4$ consecutive primes equal to a prime).

The bias is due to correlation between nearby partial sums of the sequence of primes, mod $p$. Except when adding $p$, adjacent sums must be different, and the increased chance of leaving in one step means a larger chance of returning in two steps. The same alternating pattern for even/odd number of steps disturbs the uniform $1/p$ odds of returning to the same place after $k$ steps (which is the same event as a $k$-sum of $0$).

Fix an odd number $k$, and an odd prime $p$.

If, for purposes of this problem,

the sequence of primes, reduced modulo an odd prime $p$, behaves like an i.i.d sequence of uniformly distributed nonzero residues mod $p$.

then the sequence of $k$-tuples in the $k$-sums mod $p$ is a uniform random walk on the directed graph $G$ whose vertices are the subset of $(\mathbb{Z}/p)^k$ that excludes all the planes $x_i = x_{i+1}$, and edges join $(x_1,\dots,x_k) \to (x_2,\dots,x_k, y)$ with $y \neq x_k$. The graph is strongly connected and the walk is aperiodic, so there is a unique stationary distribution, to which the walk converges exponentially fast. For making the analysis more precise it could be important to know whether this convergence rate is uniform in $p$, but I will ignore that complication. The stationary distribution is the uniform distribution, since the indegree = outdegree = $(p-1)$ for all vertices. Hence,

the distribution mod $p$ of the probabilistic $k$-sums is the same as that of of $k$-sum on vertices of $G$ (in the uniform distribution on $G$)

and we are reduced to a problem of counting solutions to $x_1 + x_2 + \dots x_k = a$ with $x_i \neq 0$ mod $p$. By inclusion-exclusion the number of solutions is a polynomial $P_a(t)$ evaluated at $t=p$. The polynomial is monic of degree $k-1$, does not depend on $p$, and the dependence on $a$ is only in whether $a=0$ or not. Hence there are, for every $k$, two polynomials counting the number of $k$-sums with $a=0$ and $a \neq 0 \mod p$, which will be denoted $P_k(t)$ and $Q_k(t)$, subject to the recursions

$Q_k(t) = P_{k-1}(t) + (t-2)Q_{k-1}(t)$ and $P_k(t) = (t-1)Q_{k-1}(t)$, with initial conditions $P_1(t)=0$ and $Q_1(t)=1$

Of course $P_k + (t-1)Q_k = (t-1)^k$, and the recursion shows $P_k - Q_k= -(P_{k-1}-Q_{k-1})$ alternates sign, so that $(P_k(t),Q_k(t))=(\frac{(t-1)^k + (-1)^{k}(t-1)}{t},\frac{(t-1)^k + (-1)^{k-1}}{t})$. As a check on the calculations, these counts are nearly equal, in fact the bias is the smallest possible given that all nonzero residue classes must receive the same deviation from the uniform distribution. Setting $t=p$ and dividing by $(p-1)^k$ gives the asymptotic proportion of zero and nonzero $k$-sums mod $p$ as

$p_0 = \frac{1}{p} + (-1)^k \frac{1}{p(p-1)^{k-1}}$ and $p_{\neq 0} = (1 - \frac{1}{p}) + (-1)^{k-1} \frac{1}{p(p-1)^{k-1}}$

so that in the optimistic assumption of rapid convergence (of the actual prime sums) to that asymptotics, the density of $k$-sums that are nonzero mod $p$ can be written as $p_{\neq 0} = (1 - \frac{1}{p})c_p$ with $c_p= 1 + \frac{(-1)^{k-1}}{(p-1)^k}$ the local correction term.

The infinite product $C = \displaystyle \prod_p c_p$ converges to the presumed correction factor. For $k=2$ it is the twin prime constant, and there is no closed-form evaluation for any $k > 1$.

-
Thanks!! I'm a bit unclear on this part: "adjacent k-sums that share (k−1) of their summands cannot have the same value mod p, except cases when p is one of the primes in the sum". For the minimal counterexample, let p = 3 and k = 3; we have 17 = 29 mod 3, so 17+19+23 and 19+23+29 are adjacent k-sums with the same residue mod p. For p = 3 and k = 5, we get another counterexample from 11 = 29 mod 3. – Chris Culter Jan 22 '14 at 19:12
Towards the end, since $k$ is odd, we should be able to simplify $(-1)^{k-1}=1$, which leads to $c_p=1+(p-1)^k$, unless I'm missing something. Since that's so simple, I wonder if that leads to a nice expression for $C$ as an Euler product? – Chris Culter Jan 22 '14 at 19:53
I meant, $c_p=1+(p-1)^{-k}$ – Chris Culter Jan 22 '14 at 20:53
Thanks for the careful reading. The edit should address all the comments. – zyx Jan 23 '14 at 18:31
By the way, the appearance of the twin prime constant for $k=2$ is a prediction that asymptotically the number of twin primes up to $n$ is double the number of $i<n$ such that $p_i+p_{i+1}$ has exactly one odd prime factor. That would be interesting to check numerically. – zyx Jan 23 '14 at 18:58

For fixed $k$, the n-th $k$-sum is about $kn\log n$ and so $n_k(x)\approx x/(k\log x).$ For any prime $p$ you can find the chance that a $k$-sum is divisible by $p$ as the coefficient of $x^0$ in $$(x+x^2+\cdots+x^{p-1})^k=\left(\frac{x^p-1}{x-1}\right)^k\pmod{x^p}$$ divided by $p^k$, call it $c_k(p)$.

Then the heuristic probability that a $k$-sum is prime needs to be modified by $$C_k=\prod_{p\text{ prime}}\frac{p-pc_k(p)}{p-1}$$ to get $$\frac{C_kx}{\log^kx}.$$

-
Should the first displayed equation start with $1+x+x^2+\cdots$ instead of $x+x^2+\cdots$? I'm not sure where it came from, or the $\log^k x$ at the end. Thankfully, the form of $C_k$ makes perfect sense. Perhaps you'd like to explain the rest for the benefit of... my friend... who never studied number theory? ;) (Or just point me to a textbook that would build up to this point.) – Chris Culter Jan 6 '14 at 7:28
No, the $x^0$ should be absent since no primes (other than p) are 0 mod p. The $\log^k$ comes from needing $k$ terms to be prime, any one happening with probability $1/\log x$. – Charles Jan 6 '14 at 15:39
Well, the first equation doesn't seem to be correct. For example, if $p=3$, then the left side is $(x+x^2)^k$ and the right side is $(1+x+x^2)^k$. I also don't understand taking the coefficient of $x^0$, which seems to be always $0$ on the left side and always $1$ on the right side. Modding out $x^p$ doesn't seem to change anything. – Chris Culter Jan 13 '14 at 19:32
The analysis in the other answer shows that the calculation with $c_k(p)$ gives the right correction factor, but I do not see how to justify that without the Markov model and an examination of its limiting distribution. Neighboring sums correlate, which can and does affect the answer, and it is good luck that the Markov chain has a uniform limiting distribution (that is what allows the computation equivalent to $c(p)$, basically decoupling the neighbors as far as the asymptotic frequency is concerned) but there is no obvious reason why it had to be that way. – zyx Jan 23 '14 at 18:51