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


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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Mar 29 '18 at 12:28
  • 1
    $\begingroup$ The primes upto $13$ seem to be a "covering set" $\endgroup$ – Peter Mar 29 '18 at 12:34
  • $\begingroup$ @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. $\endgroup$ – samerivertwice Mar 29 '18 at 12:36
  • $\begingroup$ @Peter are you able to describe more precisely what you mean about the covering set? $\endgroup$ – samerivertwice Mar 29 '18 at 12:39
  • $\begingroup$ The set covers all cases (See also my answer) $\endgroup$ – 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.


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.