# Is the product of primes + 1 always eventually composite and, if so, how long does it take?

I was thinking about Euclid's proof of the infinitude of primes the other day and started thinking about what would happen for different initial sets of primes than the usual first $N$ primes. Is there a finite subset of the primes which never actually hits a composite number when generating numbers as in Euclid's proof?

Consider the following algorithm:

Take a set $A_{k}=\left\{q_{1},\ldots,q_{k}\right\}$ of primes and let $n = q_{1}\cdots q_{k}+1$. If $n$ is prime, start over with $A_{k+1} = A_{k}\cup\left\{n\right\}$. If $n$ is composite, terminate.

Written in a C-like pseudocode:

function euclid(array primes[])
{
n = 1;
steps = 1;
for(i = 0; i < primes.size(); i++)
{
n *= primes[i];
}
n++;

while(isPrime(n))
{
steps++;
primes.append(n);
n = n*(n-1) + 1;
}
return steps;
}


My question is: Does this always terminate for any initial set of primes? If so, how can we express the number of steps in terms of the initial set of primes? Is the number of steps taken unbounded if we vary the initial set of primes?

The only thing I've been able to determine on my own, so far, is that this obviously terminates after the first step whenever 2 isn't included.

Here are some examples (all include 2):

$\{2\}\to\{2,3\}\to\{2,3,7\}\to\{2,3,7,43\}\to\{2,3,7,43,1807\}\to$ Terminate: $13\mid1807$. 4 steps.

$\{2,5\}\to\{2,5,11\}\to\{2,5,11,111\}\to$ Terminate: $3\mid111$. 2 steps.

$\{2,7\}\to\{2,7,15\}\to$ Terminate: $3\mid15$. 1 step.

$\{2,3,5\}\to\{2,3,5,31\}\to\{2,3,5,31,931\}\to$ Terminate: $7\mid931$. 2 steps.

Since $q_{\ell+1} = q_{\ell}\left(q_{\ell}-1\right)+1$ for all $\ell>k$, it seems that looking at the polynomial $x^{2}-x+1$ may provide some insight.

If anyone can link to references for this or similar problems, I'd really appreciate it.

• Checking the values of $x^2-x+1\pmod{7}$ shows that if the first product is not congruent to $0$ or $1$ mod $7$, then the process terminates in at most $4$ steps. Jan 31, 2017 at 1:03
• Related question on mathoverflow: recommended because of Pete L. Clark's answer and the problem he links to. Problem 6)f) is this problem, listed as open. Jan 31, 2017 at 3:40
• Intuition is that yes, it will always hit a composite number. Very interesting question. Jan 31, 2017 at 5:54

I found some chains of length 5. I am using the probable prime command from GMP, my impression is that it is guaranteed correct up to much larger numbers. However, if this is more than curiosity, checking would be a good idea. I read the documentation and bumped up the number of repetitions (50 of Miller-Rabin) to the maximum recommended. Slowed it down, but got the same half dozen up to $10^8.$

Mon Jan 30 19:25:50 PST 2017
13115173   172007749704757   29586665958494159812918724293   875370802539517140393632331212098638022167320345629625557   766274041938678308049319803711051212986259395320990707203549752995233768068251390160273049235842065222326397934693
23272621   541614864937021   293346661920746958223431417421   86052264060045013489275157603303175774028761968533710873821   7404992149859714708930737706369339944615210649341690766424129198306152332487064738593882427023567001814322241672266221
43796593   1918141514611057   3679266870074397876472472046193   13537004701227056184212572777137962994585421608693327853747057   183250496281043420667204993845631634549777423549644826314801936966317119658847689648539960945358606795775203767987482414193
64693357   4185230375236093   17516153293798843629675114668557   306815626211860078798689815788249593808206393118777152849793693   94135828487775841446943380610380023116334939583097326111040294547737602950518680763144469059375179058255558887576839812784557
72387043   5239883921896807   27456383514952658161000834898443   753852995720164083849269319663386535220519708325540409288925807   568294339156265728521041918046170074189415178100247125572427897938945308853001216856867572395396326046090335520807838661675443
74448109   5542520859227773   30719537474974965545765035311757   943689982676391281914926286332303062191089120887819365147115293   890550783403767677768012591611033133058156175355170445099083019318797635091721580565901937527616358694962036159921434287360557
Mon Jan 30 19:39:19 PST 2017


Here are some chains of length 4, where each $p$ is succeeded by $p^2 - p + 1$

55441   3073649041   9447318424166570641   89251825407597135537814006922276580241
202987   41203519183   1697729993022645468307   2882287129208671830499464750943820695977943
275059   75657178423   5724008646853999588507   32764274989259355373312611751567271326900543
287491   82650787591   6831152689329948795691   46664647064939791926935807581286611311371791
381991   145916742091   21291695622305494310191   453336302472902950617751284445540769432146291
393583   154907184307   23996235749767959885943   575819330158441883939292524503281817609113307
520717   271145673373   73519976188626455523757   5405186898776201001723230343143689030735871293
703123   494381250007   244412820357989456250043   59737626755346825192835475875901093166281251807
761377   579694174753   336045336241982008436257   112926468009986746720388592656212511936423733793
916189   839401367533   704594655815431145138557   496453629003665878435240241092992595903582903693
996367   992746202323   985545022225746104394007   971298990833946382893772169070355680806593122043


Here are the primes $p < 10000$ such that $q = p^2 - p + 1$ is also prime. Note that, for $p > 3,$ it is necessary to have $p \equiv 1 \pmod 3,$ as $2^2 - 2 + 1 = 3 \equiv 0 \pmod 3.$ At the same time, be aware that there is no proof that there are infinitely many prime values of $x^2 - x + 1$ for integer $x.$ There are infinitely many primes $r = x^2 - xy+ y^2,$ indeed all primes $r \equiv 1 \pmod 3;$ that does not seem to help you, though.

I see what kinds of restrictions do show up... we already said that $p,$ being the first of your prime sequence for which the next entry is $p^2 - p + 1.$

If $p > 3,$ we must have $p \neq 2 \pmod 3.$

If $p > 7,$ we must have $p \neq 3,5 \pmod 7.$ This is where $31$ failed, as $31 \equiv 3 \pmod 7.$

If $p > 13,$ we must have $p \neq 4,10 \pmod {13}.$ This is where $43$ failed, as $43 \equiv 4 \pmod {13}.$

Given a prime $s \equiv 1 \pmod 3,$ there are two square roots of $-3 \pmod s.$

$$\mbox{If} \; \; p > s, \; \; \color{red}{ p \neq \frac{1 \pm \sqrt{-3}}{2} \pmod s}.$$

3   7
7   43
13   157
67   4423
79   6163
139   19183
151   22651
163   26407
193   37057
337   113233
349   121453
379   143263
457   208393
541   292141
613   375157
643   412807
727   527803
769   590593
919   843643
991   981091
1021   1041421
1093   1193557
1117   1246573
1201   1441201
1231   1514131
1381   1905781
1423   2023507
1549   2397853
1567   2453923
1597   2548813
1621   2626021
1693   2864557
1747   3050263
1789   3198733
1801   3241801
1933   3734557
1987   3946183
2011   4042111
2017   4066273
2113   4462657
2137   4564633
2143   4590307
2239   5010883
2281   5200681
2557   6535693
2647   7003963
2659   7067623
2683   7195807
2689   7228033
2731   7455631
3049   9293353
3271   10696171
3331   11092231
3511   12323611
3541   12535141
3607   13006843
3733   13931557
3847   14795563
3889   15120433
3919   15354643
4003   16020007
4057   16455193
4111   16896211
4159   17293123
4327   18718603
4447   19771363
4507   20308543
4561   20798161
4813   23160157
5011   25105111
5179   26816863
5209   27128473
5527   30542203
5641   31815241
5749   33045253
5779   33391063
5839   34088083
6007   36078043
6043   36511807
6091   37094191
6217   38644873
6379   40685263
6397   40915213
6421   41222821
6427   41299903
6451   41608951
6553   42935257
6577   43250353
6637   44043133
6703   44923507
6883   47368807
7027   49371703
7393   54649057
7573   57342757
7753   60101257
7933   62924557
7951   63210451
8017   64264273
8089   65423833
8269   68368093
8563   73316407
8647   74761963
8689   75490033
8719   76012243
8731   76221631
8761   76746361
8803   77484007
8887   78969883
8929   79718113
9001   81009001
9043   81766807
9127   83293003
9157   83841493
9181   84281581
9199   84612403
9241   85386841
9319   86834443
9463   89538907
9601   92169601
9613   92400157
9661   93325261
9769   95423593
9781   95658181
9829   96599413
9883   97663807
9967   99331123


================================

These are the primes $p < 100,000$ for which a chain of at least three primes shows up.

3   7   43
379   143263   20524143907
1789   3198733   10231889606557
2143   4590307   21070913763943
3889   15120433   228627478987057
6553   42935257   1843436250720793
8929   79718113   6354977460562657
9661   93325261   8709604247392861
11467   131480623   17287154092987507
12853   165186757   27286664522990293
15439   238347283   56809427075134807
17497   306127513   93714053909437657
19531   381440431   145496802020025331
25999   675922003   456870553463610007
27409   751225873   564340311513386257
31123   968610007   938205344691930043
32869   1080338293   1167130826241815557
33601   1128993601   1274626549969953601
45697   2088170113   4360454418738262657
49627   2462789503   6065332133624197507
52837   2791695733   7793565062858711557
54541   2974666141   8848638647437165741
55441   3073649041   9447318424166570641
56431   3184401331   10140411833690170231
58657   3440584993   11837625090616225057
60943   3713988307   13793709140818737943
62773   3940386757   15526647790800590293
62983   3966795307   15735465003670428943
63361   4014552961   16116635472659314561
64849   4205327953   17684783188077842257
65167   4246672723   18034229212025562007
67033   4493356057   20190248650485231193
70393   4955104057   24553056210742755193
71947   5176298863   26794069913918793907
83227   6926650303   47978484413123341507
87049   7577441353   57417617450577029257
87511   7658087611   58646305850093599711
89611   8030041711   64481569872369765811
95803   9178119007   84237868497476547043
97213   9450270157   89307606030834534493

• Thanks for the work, it seems that this is an open question as shown by Jonas Meyer's comment to my post. Jan 31, 2017 at 4:06
• Since this is the closest I can reasonably expect to an answer for this problem, I'm accepting it as the answer. Jan 31, 2017 at 23:00
• I think someone should figure out the probability that a number identified as a probable prime is composite (a) because you stopped after 50 tests only or (b) because some bit flipped due to cosmic rays. Aug 22, 2022 at 19:50
• @gnasher729 from wikipedia "As a consequence, if n is composite then running k iterations of the Miller–Rabin test will declare n probably prime with a probability at most $4^{−k}. \; \; \;$" Aug 22, 2022 at 19:59

I have a partial answer to this problem that is so bizarrely simple that I must have made a mistake somewhere - so please correct me if you see any mistakes:

Not allowing the inclusion of $$3$$, we can obviously write any starting list of primes (even allowing repetitions!) as $$\{2,\ldots, 2,3k_1+1,\ldots,3k_m+1,3k_1+2,\ldots,3k_n+2\}$$. Examining the first iteration step modulo 3 we arrive at $$p := 2^l\cdot\prod_{i = 1}^{m}(3k_i+1)\cdot \prod_{j = 1}^{n}(3k_j+2) + 1 \equiv (-1)^l \cdot (1)^{m} \cdot (-1)^{n} \equiv (-1)^{l+n}+1$$

This means that we either have $$p \equiv 0 \mod 3$$ or $$p \equiv 2 \mod 3$$. In the first case, we are trivially done after the first step with $$3 \mid p$$ (excluding the case where $$p = 3$$, in which case we must have had $$\{2\}$$ as the starting list). In the second case, we can now apply the polynomial recursion formula given by Brian $$p^2 - p + 1 \equiv 2^2 - 2 + 1 \equiv 0 \mod 3$$ and see that the algorithm terminates after $$2$$ steps.

The same argument works with $$7$$, since in this case every residue class except $$0$$ and $$1$$ will eventually end up divisible by $$7$$ (as in the case of $$3$$, the longest path needing $$4$$ residues). So as a partial analysis we can conclude that if $$3$$ and/or $$7$$ is absent in the starting list, the algorithm must always terminate in at most $$4$$ steps (as shown in the question we need 4 steps if we start with $$\{2\}$$). This is not a contradiction to Will Jagy's answer: Subtracting one from the first numbers in each row and using divisibility rules, we can see that all of them are of the form $$3k+1$$ for some very large $$k$$.

This argument sadly breaks if you include a single $$3$$ in the list, because then $$p \equiv 1 \mod 3$$ and we cannot conclude anything further $$\mod 3$$ since $$1$$ is a fixed point of $$x^2-x+1$$.

We can further eliminate parametric families in the following way: Our starting point is to have the algorithm terminate in the first step by being divisible by a prime $$p$$. To make our lives easier, we assume that our list has the form $$\{2,3,7,pk+c\}$$ with $$c \in \{0,\ldots,p-1\}$$ to be determined. To terminate in the first step, we need to have $$42(pk+c)+1 \equiv 42c + 1 \stackrel{!}{\equiv} 0 \mod p \iff c \equiv -42^{-1} \mod p$$ where $$r := 42^{-1}$$ is understood as the unique modular inverse of $$42$$ modulo $$p$$.

We conclude: If we can represent a prime in the form $$pk-r$$, we can guarantee termination after the first step. We can spin this method further by just calculating more terms of the list, but as this post is already very long, I will leave it as an exercise to the reader.

Jumping off this observation, the post that is linked in the sidebar gives a pretty hefty conclusion for a large class of startings lists: Like shown above, when the first step lands in a certain residue class $$c \mod p$$, we can simply figure out if we will land at $$0 \mod p$$ after finitely many steps. This means we can create a "ranking" that tells us how (asymptotically) likely it is for a prime to be representable as $$kp+\ldots$$ and hence terminating the algorithm if it is. For $$p = 3,7,13,73,139,181,(\ldots),6469$$ we have more than half of the residues covered, where the last one even clocks in at $$\frac{6413}{6469} \approx 99.13\%$$ coverage! Combining all of these statistics together, I am positive that we can probably speed up the long-chain search by employing the CRT and checking corresponding classes (e.g. excluding $$181$$, we have only $$(3-2)(7-6)(13-7)(73-45)(139-100)(6469-6413) = 366912$$ out of a $$q := (3)(7)(13)(73)(139)(6469) = 17919977439$$ possibilities; setting the chances to $$\frac{366912}{17919977439} \approx 0.0020475\%$$ with the first non-zero modulus $$\mod q$$ being $$113988$$)!

This especially means we computationally proved the conjecture up to all primes smaller than $$113988$$ in any starting list, since they can trivially represented as themselves $$\mod q$$.