Problems & Puzzles: Puzzles

Puzzle 905. Primes generated by a recursive formula? Dmitry Kamanetsky sent the following nice puzzle related to distinct primes generated by a recursive formula. Consider f(n)=3*f(n-1)-574   If f(0)=307 then f(n) generates 13 unique primes in a row:   307 347 467 827 1907 5147 14867 44027 131507 393947 1181267 3543227 10629107   Q. Can you discover a similar function that generates more unique primes in a row?    Note: a trivial solution is to use the current record for most primes in an arithmetic progression. For example g(n)=g(n-1)+44546738095860, g(0)=56211383760397   would generate 23 primes in a row. You cannot use such a solution.   More general, let P(x) be a polynomial of degree n: P(x) := P0+P1*x+P2*x^2+...+Pn*x^n Let f(m) := P(f(m-1)) and f(0)=k Find polynomials P and starting value k, such that f generates the most number of unique positive primes in a row, starting with f(0). P can be any polynomial of degree n provided that P1>1 when n=1. The special clause is to ensure that we don't use the trivial solution with primes in an arithmetic progression.

---

Contribution came from J. K. Andersen

***

Jens wrote on Dec 30, 2017:

In 2007 in puzzle 403 I found 1158174141556287 + 4^m is prime for m = 1..18.
Starting at k = 1158174141556291 this gives 18 primes for
f(n) = 4*f(n-1) - 3*1158174141556287.

In 2014 Raanan Chermoni and Jaroslaw Wroblewski found a Cunningham chain
of the second kind with length 19 starting at 42008163485623434922152331.
This gives 19 primes for f(n) = 2*f(n-1)-1.

If the degree is above 1 then values grow much faster and it becomes harder.
In puzzle 137 I found 2072005925466^(2^m)+1 is prime for m = 0..6.
Starting at k = 2072005925467 this gives 7 primes for f(n) = (f(n-1)-1)^2+1.
The 7th prime has 789 digits.

***

 

---