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.
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