10
$\begingroup$

I wonder whether the sequence defined by $$x_0=12$$ $$x_{n+1}=x_n^2+1$$ for all non-negative integers $n$ contains a prime number.

The following table shows from left to right : The index $n$ , the number of digits of $x_n$ and the smallest prime factor of $x_n$.For $n=17$, I did not find a prime factor so far.

? x=12;j=0;while(length(digits(x))<10^6,j=j+1;x=x^2+1;p=2;while(Mod(x,p)<>0,p=ne
xtprime(p+1));print(j,"   ",length(digits(x)),"   ",p))
1   3   5
2   5   2
3   9   13
4   18   2
5   35   733
6   70   2
7   139   5
8   277   2
9   554   1536673
10   1107   2
11   2214   13
12   4427   2
13   8854   5
14   17707   2
15   35413   13
16   70825   2

As we can see, a prime of the desired form must have more than $140\ 000$ digits. The smallest prime factor of $x_9$ is already large and the smallest prime factor of $x_{17}$ will be considerably larger (I currently search for a prime factor)

  • Is $x_{17}$ prime ?
  • Does the sequence contain a prime ?

UPDATE :

This is a somewhat modified program to determine the indices $n$ for which $x_n$ has no prime factor belo $10^7$

? for(k=1,50,p=1;gef=0;while((gef==0)*(p<10^7),p=nextprime(p+1);s=12;for(j=1,k,s
=lift(Mod(s^2+1,p)));if(s==0,gef=1));if(gef==0,print1(k," ")))
17 33
?

Since $x_{33}$ is already huge , the only hope is $x_{17}$, but if I did not make an error using the factordb-database, $x_{17}$ should be composite.

$\endgroup$
  • 1
    $\begingroup$ Just to be absolutely clear, by $x_n^2$ you mean $(x_n)^2$, right? $\endgroup$ – David R. Aug 31 '17 at 21:35
  • 2
    $\begingroup$ Where did this problem originate? $\endgroup$ – Carl Schildkraut Aug 31 '17 at 21:40
  • 3
    $\begingroup$ If the index is even, then the number is a multiple of $2$. If the index is $\equiv 1\pmod{3}$, then the number is a multiple of $5$. If the index is $\equiv 3\pmod{4}$, then the number is a multiple of $13$. If the index is $\equiv 4\pmod{7}$, then the number is a multiple of $41$. That narrows down the indices you have to check a bit more. $\endgroup$ – G Tony Jacobs Aug 31 '17 at 22:49
  • 3
    $\begingroup$ most of what we've been discussing are sieving indexes, you might also try the polynomial remainder theorem, which may let you use the even values you are getting every second term. it says that in a polynomial every value taken on by the polynomial divides infinitely many more terms further along. if you count it as a function f(x)=x^2+1 for example you get that all x values that all of a certain type get eliminated but then you have to map that onto your iterative function. $\endgroup$ – user451844 Aug 31 '17 at 23:33
  • 3
    $\begingroup$ $x_{17}$ is composite (tested using PFGW). $\endgroup$ – pietfermat Sep 1 '17 at 18:47

Your Answer

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

Browse other questions tagged or ask your own question.