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

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.



Records   |  Conjectures  |  Problems  |  Puzzles