Puzzle 1008. Another curio by G.L. Honaker, Jr.

During the week 11-17 July, 2020 contributions came from Adam Stinchcombe, Jan van Delden, Oscar Volpatti, Ray Opao, Simon Cavegn

The prime p = 53137619 is the smallest one which gives rise to a sequence of length 3.

Next few such primes are 117770039, 167438669, and 762576209.

More generally, let F(k,x) be the number of primes p <= x which gives rise to a sequence of length at least k:

F(3,10^8) = 1;

F(3,10^9) = 4;

F(3,10^10) = 14;

F(3,10^11) = 54;

F(3,10^12) = 282;

F(3,10^13) = 1665.

But, unfortunately:

F(4,10^13) = 0.

I computed these values in the most straightforward way: sieve, detect twin primes, find the length of resulting sequences.

My laptop took about one day to check the 15834664872 candidates below 10^13 (but it didn't complain about working all Sunday).

Before searching further, I tried to guess the size of primes which give rise to sequences of lengths 4 and 5.

I computed the densities predicted by Bateman-Horn conjecture (https://en.wikipedia.org/wiki/Bateman-Horn_conjecture),

as all the terms of a sequence are polynomial functions of p:

{p, p + 2};

{p^3 + 3*p^2 + 2*p - 1, p^3 + 3*p^2 + 2*p + 1};

and so on.

Checking the conjecture against the known densities for k = 3:

C ~ 68.5

D = (1*3*9)^2 = 3^6 = 729

F(3,10^8) ~ 0.67

F(3,10^9) ~ 2.02

F(3,10^10) ~ 9.04

F(3,10^11) ~ 47.83

F(3,10^12) ~ 274.06

F(3,10^13) ~ 1653.52

Some predicted densities for k = 4:

C ~ 598.5

D = (1*3*9*27)^2 = 3^12 = 531441

F(4,10^14) ~ 0.14

F(4,10^15) ~ 0.74

F(4,10^16) ~ 4.29

F(4,10^17) ~ 25.92

F(4,10^18) ~ 161.52

Some predicted densities for k = 5:

C ~ 5042

D = (1*3*9*27*81)^2 = 3^20

F(5,10^22) ~ 0.16

F(5,10^23) ~ 1.03

F(5,10^24) ~ 6.68

F(5,10^25) ~ 44.01

F(5,10^26) ~ 294.78

In each case, I estimated the constant C by truncating the infinite product after the primes below 10^5.

These computations suggested a simple way to speed up the sieve for sequences of length k:

when considering a small prime q, cancel out not only its multiples d*q, but also all the numbers d*q+r such that q divides any of the 2*k needed terms of the sequence.

The forbidden residues r can be pre-computed; on average, there are about 2*k forbidden residues per prime.

For some small primes, the permitted residues are very few:

for k = 4, the number p+1 must be a multiple of 2, 3, 5 and 11;

for k = 5, the number p+1 must be a multiple of 19 too.

I was able to sieve up to 3*10^15, finding the first two primes which give rise to sequences of proven length 4:

p = 2856646544865959 and p = 2956667885147129.

However, if the conjecture is correct about k = 5 too, the range 10^23-10^24 is still out of reach for me.

Here are the eight primes for the first solution:

p(1,1) =

2856646544865959;

p(1,2) = p(1,1)+2

p(2,1) =

23311462685219261550082039408052585710091870039;

p(2,2) = P(2,1)+2

p(3,1) =

126680151174235283229280371041669407969469653616239486013299498187651021422364708316742261

68829193534274082124574587104336721837358884193959

p(3,2) = P(3,1)+2

p(4,1) =

203294541969252314760954741769789933712577230033797932367820621008468958032810353263429888

846175193033506536824575196260163142566227914807329624819819556141533862660650045024000529

221935070723727493473334462447296560609889022452916426542776267834293918727844231008186802

966007479574453733142033192072139827607272516732753924103524658224691344063851891202288217

3661284401808302610817510730001521461369887095112926942039;

p(4,2) = P(4,1)+2