Problems & Puzzles: Puzzles

Puzzle 1091 Another stair of primes... JM Bergot sent the following nice puzzle: 11+6=17 17+12=29 29+18=47 47+24=71 71+30=101 101+36=137 137+42=179 179+48=227 227+54=281 281+60=341=FAIL For some x and n, p(x)+6*n=p(x+1)                              p(x+1)+6*n+1)=p(x+2)                              p(x+2)+6*(n+2)=p(x+3) and so on for increasing n. Q. How large can n be?

---

During the week from 17-24 July, 2022 contributions came from Alain Rochelli, Gennady Gusev, Paul Cleary and Giorgos Kalogeropoulos

***

Alain wrote:

Consider the polynomials of the form A*X^2-A*X+q, where q is a prime and A is equal to 1, 2 or 3.
We have to find the values of q such that A*X^2-A*X+q assumes prime values for X=1,2,....,q-1.

Puzzle 1091's example corresponds to A=3 and q=11.
With q=5 and q=11, an another solution is obtained for q=23 (cf. OEIS A007637) :
23, 29, 41, 59, 83, 113, 149, 191, 239, 293, 353, 419, 491, 569, 653, 743, 839, 941, 1049, 1163, 1283, 1409.
Most likely there is no other satisfactory solution for 3*X^2-3*X+q.

If A=1, we get the famous example of Euler with the largest value q=41 (cf. A005846) :
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

If A=2, the only polynomials f(X)=2*X^2-2*X+q such that f(X) is prime for X=1,2,....,q-1, are those for which q=3, 7 and 19 (cf. A007639) :
19, 23, 31, 43, 59, 79, 103, 131, 163, 199, 239, 283, 331, 383, 439, 499, 563, 631

The preceding considerations come from pages 110 and 111 of Paulo Ribenboim's book “The little book of big primes”.

 

***

Gennady wrote:

Finding the stair of primes is equivalent to finding a sequence of primes of the form p+3*n*(n+1). Note that the maximum length is n=p-2 because the next number for n=p-1 giving p+3*(p-1)*p is divisible by p. A sequence (maximum) of 21 stairs starting from 23 has been found. There are no better other results for the first million primes.

23 -> 29, 41, 59, 83, 113, 149, 191, 239, 293, 353, 419, 491, 569, 653, 743, 839, 941, 1049, 1163, 1283, 1409

23+6=29,

29*12=41,

41+18=59 and so on.

...

The prime is giving length >=8 for the first million primes:

p, length

11, 9

23, 21

6211, 9

9461, 8

35401, 12

799993, 8

958333, 8

2222593, 8

10975493, 9

14628793, 9

15420043, 8

 

***

Paul wrote:

Best I could find for the largest n value.

 

With 21 terms before a fail. I searched up to the starting prime 83852665181

 

23 + 6 = 29

29 + 12 = 41

41 + 18 = 59

59 + 24 = 83

83 + 30 = 113

113 + 36 = 149

149 + 42 = 191

191 + 48 = 239

239 + 54 = 293

293 + 60 = 353

353 + 66 = 419

419 + 72 = 491

491 + 78 = 569

569 + 84 = 653

653 + 90 = 743

743 + 96 = 839

839 + 102 = 941

941 + 108 = 1049

1049 + 114 = 1163

1163 + 120 = 1283

1283 + 126 = 1409

1409 + 132 = 1541 FAIL.

 

I also looked to see if there were any with more terms not necessarily starting with 6, this was the largest I found with 28 terms.

 

 

31 + 12 = 43

43 + 24 = 67

67 + 36 = 103

103 + 48 = 151

151 + 60 = 211

211 + 72 = 283

283 + 84 = 367

367 + 96 = 463

463 + 108 = 571

571 + 120 = 691

691 + 132 = 823

823 + 144 = 967

967 + 156 = 1123

1123 + 168 = 1291

1291 + 180 = 1471

1471 + 192 = 1663

1663 + 204 = 1867

1867 + 216 = 2083

2083 + 228 = 2311

2311 + 240 = 2551

2551 + 252 = 2803

2803 + 264 = 3067

3067 + 276 = 3343

3343 + 288 = 3631

3631 + 300 = 3931

3931 + 312 = 4243

4243 + 324 = 4567

4567 + 336 = 4903

4903 + 348 = 5251 FAIL.

 

***

Giorgios wrote:

This is a variation of the famous Prime-Generating polynomial by Euler.

If instead of 6*n (in this puzzle) we choose 2*n then we get Euler's polynomial x^2 - x + p.

Euler's "lucky numbers" were those p such that x^2 - x + p is a prime for x = 0,... ,p − 1.

Theorem. The only lucky numbers p that make f(x) = x^2 - x + p to be prime for x ∈ [0, p − 1] are 2, 3, 5, 11, 17, and 41.
 

 

In this puzzle, the prime-generating polynomial is 3x^2 + 3x + p 

The "lucky numbers" of this polynomial are 5,11 (Bergot's example) and 23 which produce stairs of length 5,11,and 23 for x ∈ [0, p − 1].

 

Now, if I understand correctly, Bergot asks for the largest n such that 3x^2 + 3x + p is prime for any x ∈ [0, n − 1] for any prime p.

This is equivalent to  p(1)+6*1=p(2),  p(2)+6*2=p(3), ... ,  p(n)+6*n=p(n+1)  for primes p(!), p(2), .... p(n)

23 produces the following stair of length 23:

 {23, 29, 41, 59, 83, 113, 149, 191, 239, 293, 353, 419, 491, 569, 653, 743, 839, 941, 1049, 1163, 1283, 1409}

It is very difficult to beat this record and find a prime p that produces a stair of length 24.

My estimation is that such a prime would be >10^20

In any case, I believe that we can find stairs of any length..

Working modulo 5, 7, 11, 13, 17, 19, 23 and 29 we can make a sieve and exclude non-primes for the first 24 values of x..
 

The above sieve only checks 2*10^6 numbers for every 10^9 numbers.

Here are some results which produce stairs of length 13, 14 and 15

 

Length of stair -> Starting prime p

          13         ->         35401
 

          14         -> 10445256498283
 

          15         -> 1945187598443

So, in the last case we have the following stair

1945187598443 + 6 = 1945187598449
 

1945187598449 + 12 = 1945187598461
 

1945187598461 + 18 = 1945187598479
 

. . . 

1945187598989 + 84 = 1945187599073
 

1945187599073 + 90 = 1945187599163 FAIL (15 steps)
 

 

On the other hand, if the puzzle asks for a large n such that 

p1 + 6n = p2,  p2 + 6(n+1) = p3,   p3 + 6(n+2) = p4 and so on,

Then we have 3 variables to maximize: the prime p1, n and the length of the stair.

Here is an example for p1=15038463318324545459, n=2238933029 with length of 10 steps

 

15038463318324545459 + 6*2238933029  = 15038463331758143633
 

15038463331758143633 + 6*(2238933029 + 1) = 15038463345191741813
 

15038463345191741813 + 6*(2238933029 + 2) = 15038463358625339999
 

15038463358625339999 + 6*(2238933029 + 3) = 15038463372058938191
 

15038463372058938191 + 6*(2238933029 + 4) = 15038463385492536389
 

15038463385492536389 + 6*(2238933029 + 5) = 15038463398926134593
 

15038463398926134593 + 6*(2238933029 + 6) = 15038463412359732803
 

15038463412359732803 + 6*(2238933029 + 7) = 15038463425793331019
 

15038463425793331019 + 6*(2238933029 + 8) = 15038463439226929241
 

15038463439226929241 + 6*(2238933029 + 9) = 15038463452660527469 FAIL

 

***