Does the sequence $x_0=8$ , $x_{n+1}=4x_n+1$ contain a prime?

Question

Inspired by this question : Does every sequence $4^nx_0+\frac{4^n-1}{3}$ contain a prime?

If $x_0=21$, the sequence $x_{n+1}=4x_n+1$ produces no prime as shown in OEIS. What about the case $x_0=8$ ?

Is $4^n\cdot 8+\frac{4^n-1}{3}$ prime for any nonnegative integer $n$ ? Or equivalent : does the sequence $x_0=8$ , $x_{n+1}=4x_n+1$ produce a prime ?

I did not find a prime for $n\le 50\ 000$

For the casual lurker: Just provided an answer to the more general question to which you refer: https://math.stackexchange.com/a/4351868/1714 It contains a list of additional cases $x_0$, where the sequences are proven to be primefree, using another argument than in PaoloLeonetti's answer. — Gottfried Helms, Jan 08 '22 at 20:06

score 14 · Accepted Answer · answered Mar 25 '18 at 11:14

14

No: $$ 4^n\cdot 8+\frac{4^n-1}{3}=\frac{(5\cdot 2^n+1)(5\cdot 2^n-1)}{3}. $$ (both factors at the numerator are $>3$).

answered Mar 25 '18 at 11:14

Paolo Leonetti

15,423
3
24
57

Well done! (+1 and accept as soon as possible) – Peter Mar 25 '18 at 11:15
@Peter I didn't realise you had posted this until now. – it's a hire car baby Mar 25 '18 at 18:35
3

..which can be extended to all $x_0$ for which $3x_0+1$ is a square – Paolo Leonetti Mar 25 '18 at 18:40
Am I right in thinking "both factors are $>1$" is sufficient to prove it compound? – it's a hire car baby Mar 25 '18 at 19:23
Not exactly: you need that the numerator, divided by $3$, has to be composite (so both factors have to be $>1$, and the one divisible by $3$ has to be $>3$..) – Paolo Leonetti Mar 25 '18 at 19:45
Ah yes of course. Thanks – it's a hire car baby Mar 25 '18 at 19:54
@PaoloLeonetti your answer extends to prove that these "prime-free" sequences start where $3x_0+1$ is square and $\lvert3x_0+1\rvert_2=1$; and every successor in the sequence satisfies $\lvert3x_n+1\rvert_2=\dfrac{1}{2^{2n}}$. Do you think by applying Dirichlets theorem to the sequence $3x_n+1$ you can prove these sequences are primefree $\iff$ $3x_0=1$ is square? – it's a hire car baby Mar 25 '18 at 19:57
i.e. the set of all prime-free sequences is in bijection with the odd square numbers – it's a hire car baby Mar 25 '18 at 19:58
1

I do not think so: the question is of the type whether $a\cdot 2^n+b$ with $a,b$ coprime odd integers is prime (or not). As particular instances, there are two of the major open problems in number theory: establish whether Mersenne primes $2^n-1$ and Fermat primes $2^n+1$ are finite or not; however, they seem to be out or reach at the moment.. – Paolo Leonetti Mar 25 '18 at 20:10
Paolo don't automatically give up because it's a major open problem. – it's a hire car baby Mar 29 '18 at 10:48

Does the sequence $x_0=8$ , $x_{n+1}=4x_n+1$ contain a prime?

1 Answers1

Linked