2
$\begingroup$

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?

$\endgroup$
  • $\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*(x-1)/2 $\endgroup$ – Dattier Aug 9 at 14:54
  • 6
    $\begingroup$ Say, if $P(x)=x^2-x+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)=(x-1)^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
7
$\begingroup$

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 Green-Tao theorem.
An example for $M=23$: $x_0=56211383760397$, $a_{23}=44546738095860$.

| cite | improve this answer | |
$\endgroup$
  • $\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 High-Powered 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$ I think Gerhard talk about finite sequence. $\endgroup$ – Dattier Aug 9 at 15:00
  • $\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
2
$\begingroup$

An answer for the case $P(x)=x^2-x+1=x(x-1)+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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ? this gives the sequence $2, 3, 7, 43, 1807,\ldots$, but 1807 is not prime... $\endgroup$ – Carlo Beenakker Aug 9 at 16:27
  • $\begingroup$ Yes, it's not a solution. $\endgroup$ – Dattier Aug 9 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.