# Are the prime-free sequences $x_{n+1}=4x_n+1$ of odd numbers in bijection with the square numbers greater than $16$?

Are the prime-free sequences $x_{n+1}=4x_n+1$ of odd numbers in bijection with the even square numbers greater than $16$?

Specifically:

Consider only sequences of odd, positive integers, plus zero.

$x_{n+1}=4x_n+1$ is prime free if $3x_0+1$ is square.

But is it prime-free only if $3x_0+1$ is square?

We have the trivial exceptions $0,1,5$ which give squares $1,4,16$; but above that?

A little background / what I know so far... and this is vague and possibly not that helpful :(

1. These sequences are linear combinations of the Lucas sequences:

$a\cdot U_n(5,4)+b\cdot V_n(5,4)$

where $a,b$ take the form:

$a=\frac{3x_0+2}{2}, b=\frac{x_0}{2}$

1. The sequences can be canonically indexed by $x_0\equiv\{1,3,7\}\mod 8$

i.e. every sequence satisfying $x_0\equiv 5\mod 8$ is a subsequence of one of these.

1. I think it's relevant that $3x_0+1$ is always even, and all even squares are of course equivalent mod $4$.

A huge wealth of important results exists into primitive primes in sequences such as these

1. The Collatz conjecture says the orbits of the Collatz function $(3x+1)\lvert3x+1\rvert_2$ totally order these sequences.

2. I keep suspecting a relationship between the Collatz graph and the kernel of the 2-adic logarithm. Not sure if there's anything in that.

• For $x_0=306$ , there always seems to be a small factor. The generating function is $$\frac{919\cdot 4^n-1}{3}$$ in this case. – Peter Mar 29 '18 at 12:28
• The primes upto $13$ seem to be a "covering set" – Peter Mar 29 '18 at 12:34
• @Peter that's interesting again because that sequence starts $x_0=1225$ (in the odd numbers) which is $7^2\times5^2$. Also $13$ is potentially of slight interest because $12^2$ is the sole exception to Carmichael's theorem which is important in this field. – samerivertwice Mar 29 '18 at 12:36
• @Peter are you able to describe more precisely what you mean about the covering set? – samerivertwice Mar 29 '18 at 12:39
• The set covers all cases (See also my answer) – Peter Mar 29 '18 at 12:42

The sequence $$\frac{919\cdot 4^n-1}{3}$$ is primefree because the number $919\cdot 4^n-1$
• is divisble by $9$ if $n=3k$
• is divisble by $5$ if $n=2k+1$
• is diviyble by $7$ if $n=3k+1$
• is divisble by $13$ if $n=6k+2$
Hence, beginning with $x_0=306$ , we have another prime-free sequence.