Does there exist a prime integer $q$ and $P$ a polynomial, such that the sequence $x_{n + 1} = P (x_n)$ and $x_0 = q$ that is to say a sequence of distincts primes integers?

$\begingroup$ Is $P$ meant to have integer coefficients? $\endgroup$ – user158636 Aug 9 at 14:48

$\begingroup$ No, P have rational coefficients. Example P(x) =1+x*(x1)/2 $\endgroup$ – Dattier Aug 9 at 14:54

6$\begingroup$ Say, if $P(x)=x^2x+1$ (that guarantees that all terms of this sequence are mutually coprime), can they all be prime? Most probably this was asked before. It is definitely open whether there are infinitely many Fermat composite numbers. If there are only finitely many, then the sequence given by $q=2^{2^k}+1$, $P(x)=(x1)^2+1$ produces an infinite sequence of primes if $k$ is large enough. But nobody believes this, I think. Heuristically your question also has negative answer. $\endgroup$ – Fedor Petrov Aug 9 at 14:56

2$\begingroup$ When $P$ has integer coefficients, there is infinitely many positive integers $n$ such that $P(n)$ is composite. Here, if P(x)=y$, then $y\mid P(x+ky)$. Not sure how to do this for rational coefficients though. $\endgroup$ – Zachary Hunter Aug 9 at 15:38

$\begingroup$ "That is, there is no known polynomial of degree >1 which takes infinitely many prime values." from math.stackexchange.com/questions/2019744/… Your polynomial would be one taking infinitely many prime values. $\endgroup$ – Eric Towers Aug 9 at 22:20
If you allow the sequence to be finite, producing $M$ distinct primes, then such a polynomial exists for any $M$, no matter how large; the polyomial is simply $P_M(x)=x+a_M$. This is the GreenTao theorem.
An example for $M=23$: $x_0=56211383760397$, $a_{23}=44546738095860$.

$\begingroup$ The objectif of this question, is to build very big prime number. $\endgroup$ – Dattier Aug 9 at 14:22

2$\begingroup$ More generally, choose the finite sequence (of distinct primes) in advance, and then build the polynomial using Lagrange interpolation. Gerhard "No HighPowered Number Theory Needed" Paseman, 2020.08.09. $\endgroup$ – Gerhard Paseman Aug 9 at 14:50

1$\begingroup$ @GerhardPaseman but OP is iterating, how does Lagrange apply? $\endgroup$ – user158636 Aug 9 at 14:55


$\begingroup$ For $(x,y)$ use $(q_k,q_{k+1})$. Gerhard "See How Easy It Is?" Paseman, 2020.08.09. $\endgroup$ – Gerhard Paseman Aug 9 at 15:01
An answer for the case $P(x)=x^2x+1=x(x1)+1$
In this case $x_{n+1}=x_n\times ...\times x_0+1$ for $n>2$
Suppose $x_i$ is prime number, with $x_{i+1}>x_{i}$ so $x_0=2$
But we can see $x_0=2$ is not solution.

$\begingroup$ ? this gives the sequence $2, 3, 7, 43, 1807,\ldots$, but 1807 is not prime... $\endgroup$ – Carlo Beenakker Aug 9 at 16:27
