Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\pi(n) = $ number of primes $ \leq n.$ Let $x_i <n,~~ i = 1,2,3,...$ such that $x_i^2+x_i \pm k $ is prime, in which $k \ll n$ is an odd integer. Let $\pi_k(n)$ be the number of such primes less than or equal to $n^2+n\pm k.$

Observation (sum of logs is over $i$ such that $x_i^2+x_i\pm k$ is prime):

$$(1) \hspace{5mm}\frac{\pi_k(n)}{\sum_{i}\log x_i} \approx \frac{\pi(n)}{n}$$

Example: $k= 3, n = 1000000, \pi(n) = 78498, \pi_3(n) = 40036, \sum_{i} \ln x_i \approx 509310.$

$$\frac{\pi_3}{\sum_{i}\log x_i}= 0.0786 \approx \frac{\pi(n)}{n} = 0.0785.$$

Can we justify (1) if only intuitively, conditioned on the existence of infinite primes of the form $x^2+x\pm k?$

share|cite|improve this question
something with congruences to make sense of the differing probabilities? – Cris Stringfellow Feb 16 '13 at 21:02
Please don't upvote--was just fixing a problem with notation. Thanks. – daniel Feb 6 '15 at 6:57
up vote 3 down vote accepted

Heuristically this could be seen as following from the Bateman-Horn conjecture.

For a given polynomial $F(x)$ we consider the set of positive integers $$ P(F,n) = \{ x | 1\le x \le n, F(x)~\mathrm{is~prime}\} $$ then define $$ \pi_F(n) = |P(F,n)| $$ and we are interested in the quantity $$ R(F,n) = \frac{\pi_F(n)}{\sum_{x\in P(F,n)}\log x} \\ \frac{1}{R(F,n)} = \frac{1}{|P(F,n)|}\sum_{x\in P(F,n)} \log x = E[\log x] $$ where strictly speaking $E[\cdot]$ here is the sample average, but we can think of it as the expectation with respect to the distribution of $x$ for which $F(x)$ is prime.

The Bateman-Horn conjecture says that for a single polynomial $$ \pi_F(n) \sim C_F\int_2^n\frac{1}{\log t} dt $$ where $C_F$ is a constant that depends on $F$. Assuming the approximation is good for all $n$, this says that the distribution of $x$ in $P(F,n)$ is the same for any choice of $F$, specifically $$ Pr[x<X|x\in P(F,n)] \sim \frac{C_F\int_2^X (\log t)^{-1} dt} {C_F\int_2^n (\log t)^{-1} dt} = \frac{\int_2^X (\log t)^{-1} dt} {\int_2^n (\log t)^{-1} dt} $$ independent of F. So it should apply more broadly to any single prime-generating polynomial, not only to the forms you've given. Here are some examples: $$ \begin{array}{c|c|c|c|c} F & n & \pi_F(n) & \sum_{x\in P}\log x & R(F,n) \\ \hline \\ n & 10^6 & 78498 & 998484. & 0.078617\cdots \\ n^2+n+3 & 10^6 & 40036 & 509309. & 0.078608\cdots \\ n^2+n-7 & 10^6 & 88768 & 1129088. & 0.078619\cdots \\ n^3-n^2+2x+7 & 10^6 & 27047 & 343676. & 0.078699\cdots \\ n^6+2n^3+3n+5 & 10^6 & 31468 & 400107. & 0.078648\cdots \\ n & 10^7 & 664579 & 9995179. & 0.066489\cdots \\ n^2+n+3 & 10^7 & 339824 & 5111493. & 0.066483\cdots \\ n^3-n^2+2x+7 & 10^7 & 229549 & 3452061. & 0.066496\cdots \end{array} $$ (For $n^2+n-7$ I don't include $1$ in $P$.)

All that remains to put in your form is to show that $\sum_{p\le n} \log p \sim n$. This is Chebyshev's $\vartheta(n)$, the asymptotic is correct and explicit bounds are available.

share|cite|improve this answer

I have a heuristic verification and possibly an explanation for you using the modulus $210 = 2 \cdot 3 \cdot 5 \cdot 7$

So any residue $r$, $\bmod{~210}$ that has $\gcd(r,210) > 1$ will not be prime.

To investigate your equations I formed three lists, and counted the number of relevant residues that had $\gcd(r,210) = 1$, which I will detail below :

  1. Form a list of residues of $x(x+1) + 1$
  2. Form a list of residues of $x(x+1) + 3$
  3. Form a list of residues of $x(x+1) - 15$

For example, to make the first list (in Python):

z = range(1,211)
zz1 = [(x*y+1)%210 for x in z for y in z if x-y == 1]
import fractions
zz1g = [fractions.gcd(210,x) for x in zz1]
print zz1g.count(1)

Yields: 99

In all cases the x were taken over the complete residue system $\bmod{~210}$, and the results were computed as the remainder when divided by $210$. The greatest common divisor with $210$ was then computed for each residue in each list and the occurrences of "1" were counted. The occurences are :

  1. List 1, residues of form $x(x+1) + 1$, number of $\gcd$ of 1 = 99
  2. List 2, residues of form $x(x+1) + 3$, number of $\gcd$ of 1 = 42
  3. List 2, residues of form $x(x+1) - 15$, number of $\gcd$ of 1 = 42

So heuristic verification for your equations is displayed. The number of "candidates" for primes in the first equation form are nearly double that of the other two forms, which are similar. This reflects the relative ratios you reported.

As to further explanation, if the $\gcd$ is not 1 then the number can certainly not be prime. Since there are more "not $1$" greatest common divisors in either of forms $2$ or $3$ than their are in $1$, it follows that, since primes behave as if they are randomly distributed amongst candidate residues, more primes will occur from the form where the residues more often land on those which have no divisor in common with $210$.

In fact in this case the counts under $210$ strongly support the data you obtained from a half a million points. $210$ is just a single case, but the congruence argument will approach more closely the distributions you obtained, the larger the smoothness bound on the modulus.

Which suggests that the sum of $k$ with the product of two adjacent integers more often falls on a prime when $k$, perhaps, has no prime factors at all.

Hope this helps.

share|cite|improve this answer
...when k, perhaps, has no prime factors at all. One is the only number that has no prime factors. – Fred Kline Feb 16 '13 at 21:54
Exactly my meaning! – Cris Stringfellow Feb 16 '13 at 22:01
So you want an explanation of why a scaled prime-counting function (for primes of a certain form between n and n(n+1) + k) is equal to log(n) times the number of primes in that region? [If you remove the denominator $n$ from your proportionality (with pi(n) approximation), then you get something like that]. The log function is additive for prime factors, maybe the sum of the log of the factors of n equals the average of the primes, but I don't know why. You use pi(n), and count a range of p_i, but you also slide n across the region less than 500k? Confused on Which n ou use to do your counts. – Cris Stringfellow Feb 17 '13 at 5:35
You are correct. And by that approximation to pi(n), you can cancel $n$ from your approximations to give LHS being the sum of the logarithms of such primes, and RHS being the product of the logarithm of $n$ and the count of such primes. – Cris Stringfellow Feb 17 '13 at 12:44
You seem to be talking about applying the PNT, which I did in the following line and which does not I think shed any light on the problem. – daniel Feb 17 '13 at 13:16

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.