The classical proof of the infiniteness of prime numbers is to take the $k$ first prime numbers $p_1,\ldots,p_k$, then to form $$n_k:=1+p_1\cdots p_k.$$ Then $n_k$ has a prime factor, which is none of the $p_j$.

Notice that one could form instead the number $$n_{k,I}:=\prod_{i\in I}p_i+\prod_{j\not\in I}p_j$$ where $I$ is any subset of $[1,\ldots,k]$ (we have $n_k=n_{k,\emptyset}$), or even $$m_{k,I}:=\prod_{i\in I}p_i-\prod_{j\not\in I}p_j,$$ provided this number is not $\pm1$.

This suggests the following construction of prime numbers $q_k$ by induction. Start with $k=1$ and $q_1=2$. At step $k$, form the numbers $$M_{k,I}:=\left|\prod_{i\in I}q_i-\prod_{j\not\in I}q_j\right|.$$ Then $q_{k+1}$ is the least of the prime factors of all these numbers (that is, of their product as $I$ runs over the subsets of $[1,\ldots,k]$).

Is it true that $q_k=p_k$ for all $k$ ? If not, does the sequence covers all the prime numbers ? If not, how fast does this sequence increases as $k\rightarrow+\infty$ ?

One might enlarge the construction by taking in account the numbers $M_{k,I}$ and $$N_{k,I}:=\prod_{i\in I}q_i+\prod_{j\not\in I}q_j,$$ but they are way larger.

  • 1
    $\begingroup$ You should start with $k=2$ and $q_1=2$, $q_2=3$. With your construction, $q_2$ is not defined. $\endgroup$ Sep 15, 2010 at 9:33
  • $\begingroup$ Right. If you take in accound the $M$s and the $N$s, you may start from $k=1$. $\endgroup$ Sep 15, 2010 at 9:35
  • 11
    $\begingroup$ With the Ms only, if $q_k=p_k$ for all $k\leq n$, then for some $I\subset[1,n-1]$ we have $\prod_{i\in I}p_i\equiv\prod_{i\not\in I}p_i\pmod{p_n}$. In particular $\prod_{1\leq i\leq n-1}p_i$ is a square mod $p_n$. This is true for $n<8$ but not for $n=8$ ($p_n=19$). Hence $q_8\neq p_8$. $\endgroup$ Sep 15, 2010 at 12:00
  • 1
    $\begingroup$ we may construct $p_{n+1}$ as minimal prime divisor $(\prod_{i=1}^n p_i)^k-1$ for $k=1,2,\dots$ :) $\endgroup$ Oct 13, 2010 at 15:28
  • 2
    $\begingroup$ "The classic proof" is a modern proof. Euclid didn't consider the number that is 1 more than the product of the first $k$ primes. He considered the number that is 1 more than the product of an arbitrary finite set of primes, with no assumption that they were the smallest ones. $\endgroup$ Nov 12, 2010 at 3:44

3 Answers 3


You can obtain a complete heuristic picture of what is going, by supposing that quadratic residues (as suggested by Laurent) are the only likely obstruction to getting the next prime. More precisely, if you let $Q_n = \prod_{k \le n} q_k$ be the product of all of the primes discovered so far, then you can let $p_{n+1} = p$ be the first remaining prime such that $Q_n$ is a quadratic residue mod $p$, assuming Denis' first proposal. Or, assuming Denis' second proposal, you can let $p$ be the first remaining prime such that either $Q_n$ or $-Q_n$ is a quadratic residue mod $p$. (Thus it will simply be the next prime if that prime happens to be 3 mod 4.) Or, assuming that you only use the sum formula, you would only check $-Q_n$. Then experimentally, $q_{n+1} = p_{n+1}$ in all three cases.

This describes the sequence that Charles obtained, which I also obtained (at least the first half of it) with a Sage program.

qseq = [2]
for z in range(16):
    attain = set(); Q = prod(qseq)
    prediction = [p for p in list(primes(500)) if not p in qseq and
        (legendre_symbol(-1,p) == -1 or legendre_symbol(Q,p) == 1)][0]

    for S in Combinations(qseq):
        A = prod(S); attain.update([abs(A-Q/A),A+Q/A])

    best = 10000
    best = min([min(factor(m))[0] for m in attain])
    print prediction,':',qseq,'->',best

Assuming both the sum and the difference are used, the validity of this prediction reduces to the following: If $p$ is this next prime, then the question is whether $1$ appears in the set product of the subsets $\{q_k,1/q_k\}$ and $\{\pm 1\}$ in the multiplicative group $(\mathbb{Z}/p)^*$. This is a question in additive set theory if you take a formal logarithm and pass to the additive group $\mathbb{Z}/(p-1)$. A reasonable conjecture is that you are convolving a lot of subsets that don't come close to lying in a subgroup of $\mathbb{Z}/(p-1)$, so you can expect $0$ to appear in the sum. The heuristic has such a large margin that it may be possible with existing methods to prove that it is always so.

The other part of the question is how much you deviate from seeing the primes in order. Again, using a randomness heuristic in number theory, the "probability" that a prime $p$ will be skipped at a given stage is 1/2 (assuming that it is 1 mod 4 in the second case). So you expect the first skipped prime to eventually be included with a "half life" of one round. Thus you expect the sequence to only ever be barely ahead of the list of primes, and you expect $q_n$ to be the $n$th prime infinitely often.


For the variant allowing M and N, I get

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 29, 37, 43, 47, 41, 59, 61, 53, 67, 71, 79, 83, 73, 101, 89, 103, 107, 97, 109, 113, 127, 131, 139, 151, 149, ...

which is surprisingly far from containing the primes in order, as I might have expected (up to one or two exceptions, like A063884). Would someone check me on these calculations?

Possibly relevant:

R. K. Guy, C. B. Lacampagne and J. L. Selfridge, "Primes at a glance", Mathematics of Computation 48:177 (1987), pp. 183-202.

  • $\begingroup$ Amazingly, this sequence satisfies $(q_j|j\le k)=(p_j|j\le k)$ for many $k$'s:1 to 9, 12, 19, 20, 29 to 32. Could this coincidence occur infinitely many times? $\endgroup$ Jan 21, 2013 at 16:01
  • $\begingroup$ @Denis: I think so. $\endgroup$
    – Charles
    Jan 21, 2013 at 17:00

maybe you could take the primes on the products in any powers you want , it is a thought that i had before some years and it is also a natural question that one can make reading Euclid's proof since still the difference of the products is not divisible by any of these primes do you take in this way always the next prime?

  • 3
    $\begingroup$ If you allow arbitrary exponents (and if I understand well your suggestion) then it is indeed always possible to get the next prime, just because of Fermat's little theorem. More complicated explanation : $(\mathbf{Z}/p\mathbf{Z})^*$ is generated by the classes of the primes $<p$. $\endgroup$ Dec 14, 2010 at 22:35
  • $\begingroup$ FYI, a very similar question to what you're discussing was recently asked in MathStackExchange at Is there a counter-example to these number theoretic conjectures?. I've provided an answer there which links to this page & specifically mentions your response. $\endgroup$ Jan 27, 2019 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.