3
$\begingroup$

Does every sequence $4^nx_0+\dfrac{4^n-1}{3}$ contain a prime?

Fix some odd positive integer $x_0$ and define the sequence $x_0,x_1,x_2,\ldots$ as follows:

$x_n=4^nx_0+\frac{4^n-1}{3}$

So for example choosing $x_0=1$ gives the sequence:

$1,5,21,85,\ldots$

And choosing $x_0=3$ gives the sequence:

$3,13,53,214,\ldots$

Does every such sequence contain a prime number?

Dirichlet's Theorem states that there are infinitely many primes in every arithmetic progression:

$a, a+d, a+2d,\ldots$

where $a,d$ are coprime. But I'm unaware of similar results for other progressions. I found this paper (which is beyond me) but my rudimentary understanding suggests this is saying the result is unknown for geometric progressions.

The progressions I'm asking about are exponential in nature. These are in fact the canonical set of linear combinations of the Lucas Sequences $U_1(5,4)$ and $V_1(5,4)$ over the odd integers.

Every successor $x_n:n\geq0$ is of course $\equiv 5\mod 8$ while every sequence for which $x_0\not\equiv\{1,3,7\}\mod 8$ is a subsequence of a longer sequence (with a smaller starting number), which does start with $x_0\equiv\{1,3,7\}\mod 8$.

So the set of all odd integers can be canonically indexed according to membership of the sequences starting with $x_0\equiv\{1,3,7\}\mod 8$.

I suspect these sequences have a close relationship with the kernel of the 2-adic logarithm, although I don't know a lot about that.

EDIT So far we have found that $5$ is the only prime in $1,5,21,85,...$ so not every sequence has infinitely many primes.

UPDATE Peter posted this related question for a candidate for a sequence with no primes and Paolo Leonetti has elegantly verified it has no primes, plus provided a class of such sequences which contain no primes; those for which $3x_0+1$ is a square number.

$\endgroup$
15
  • 1
    $\begingroup$ Look up Dirichlet's theorem $\endgroup$
    – Steven Alexis Gregory
    Commented Mar 23, 2018 at 23:12
  • 1
    $\begingroup$ Does Dirichlet's theorem have a case that covers exponentially distributed sequences? $\endgroup$
    – Valborg
    Commented Mar 23, 2018 at 23:16
  • $\begingroup$ @stevengregory thanks. I was aware of that... And can see it's related. But does it decide this? These sequences are neither arithmetic not geometric progressions. $\endgroup$
    – Robert Frost
    Commented Mar 23, 2018 at 23:16
  • $\begingroup$ @Valborg precisely $\endgroup$
    – Robert Frost
    Commented Mar 23, 2018 at 23:17
  • 1
    $\begingroup$ $4^{72}\cdot 8+\frac{4^{72}-1}{3}$ is a Fermat-pseudoprime to bases $3$ and $5$ , but composite. $x_0=8$ is a hard case as well. $\endgroup$
    – Peter
    Commented Mar 24, 2018 at 21:10

1 Answer 1

Reset to default
2
$\begingroup$

Aside of the nice solution provided in the other thread, which uses the algebraic factorization of the original formula when $3 x_0+1$ is a square, I have found a list of further solutions for $x_0$ such that the associated sequence contains no primes/only composites.
The sequences from $$x_0 \in \{371,495,775,1671,2171,3211,3955,4215,4655,4711,... \} \\ \text{have as well no prime entries.} \hspace{160pt} $$

This can easily be proved by looking at the small primefactors $p \in \{3,5,7,13\}$ : their cyclical occurences in the respective iteration sequence $S(x_0)$ have lengthes $\text{cyclen}(x_0,p) \in \{2,3,6\}$ and cover completely the $6$ leading entries of their sequence. Due to cyclicity each entry of the sequences $ \gt 13$ cannot be prime.

Example for $x_0=371$:

 N     primefact's x_N   Covering periodically
                          6 of 6 residueclasses
- - - - - - - - - - - - - - - - - - 
[ 0           "7.53"]       __7_        == 371
[ 1       "3^3.5.11"]       35__        == 4*371+1
[ 2         "13.457"]       ___1        == 4*(4*371+1)+1 
[ 3       "5.7^2.97"]       _57_  
[ 4        "3.31687"]       3___
[ 5      "5.113.673"]       _5__
- - - - - - - - - - - 
[ 6     "7.11.19753"]       __7_
[ 7    "3.5^2.81119"]       35__
[ 8    "13.293.6389"]       ___1
[ 9  "5.7.1427.1949"]       _57_
[10 "3^2.1423.30403"]       3___
[11  "5.11.28317907"]       _5__
- - - - - - - - - - - - 
 ... ... ... ...  ...

Unfortunately I didn't find any further algebraical expression of this phenomenon, like the style of the one that has already been given with the $3x_0+1 \text{ -is-square}$ class of solutions.

Moreover there might be some further characteristics in/by the following list of $x_0$. The list has been created by checking the computing time up to $1000$ iterates, where the ones with $0$ msecs have been the suspect ones, and which gave the examples of the above mentioned covering-primefactors-solutions: $$ \quad \text{covering } \; \mid \; \text{ heuristics} \phantom{sequence beginning at $35$ has a prime (see update at bottom)} \\ \small \begin{array} {rrr||rrr} x_0 & \# & \text{msecs}& x_0 & \# & \text{msecs}\\ \hline 371 & 0 & 0 & 35 & 0 & 125 & \text{sequence beginning at $35$ has a prime (see update at bottom)}\\ 495 & 0 & 0 & 603 & 0 & 171 \\ 775 & 0 & 0 & 1195 & 0 & 282 \\ 1671 & 0 & 0 & 1335 & 0 & 218 \\ 2171 & 0 & 0 & 1379 & 0 & 266 \\ 3211 & 0 & 0 & 1611 & 0 & 31 \\ 3955 & 0 & 0 & 1751 & 0 & 141 \\ 4215 & 0 & 0 & 2755 & 0 & 172 \\ 4655 & 0 & 0 & 2775 & 0 & 234 \\ 4711 & 0 & 0 & 2791 & 0 & 156 \\ 4971 & 0 & 15 & 3179 & 0 & 250 \\ 5195 & 0 & 0 & 3379 & 0 & 140 \\ 5831 & 0 & 16 & 4011 & 0 & 204 \\ 5955 & 0 & 0 & 4235 & 0 & 94 \\ 6235 & 0 & 0 & 5395 & 0 & 141 \\ 7131 & 0 & 0 & 5495 & 0 & 47 \\ 7631 & 0 & 0 & 5751 & 0 & 93 \\ 8671 & 0 & 0 & 5975 & 0 & 125 \\ 9415 & 0 & 0 & 6215 & 0 & 93 \\ 9675 & 0 & 0 & 6571 & 0 & 141 \\ 10115 & 0 & 0 & 6671 & 0 & 140 \\ 10171 & 0 & 0 & 6875 & 0 & 126 \\ 10431 & 0 & 0 & 7551 & 0 & 171 \\ 10655 & 0 & 0 & 7775 & 0 & 203 \\ ... & ... & ... & ... & ... & ... \end{array}$$ where "#" denotes the number of primes found up to tested iterations.

The timings were measured for up to $N=1000$ iterations (using primecertifying isprime() in Pari/GP vers. 2.14, 64 bit.

updated table:The column headed with "covering" contains that cases of $x_0$ for which the covering by the small primes occurs, so this gives proven non-prime sequences, the column headed with "heuristics" contains the cases, where the primecertification showed all iterates being composite but only up to $N=1000$ (for up to $N=8000$ iterations I used the ispseudoprime() test).

For instance, $x_0=35$ needs further work to discern whether the iterations sequence has primes or not; there have been a couple of prime-canditates by a fast (pseudo)prime-test for $N>1000$ but which were certificated to be composite with the more intense isprime()-function. The time to do this increases excessively and unpredictable, so I stopped testing of $x_N$ at $N=2000$.

update 3.feb.2022 The sequence beginning at $x_0=35$ seems to contain a prime at $(106 \cdot 4^{4553}-1)/3$ as certified by the prime-tester of Dario Alpern. The number $x_{4553}$ has $2743$ digits and leading and trailing digits $5 337343 165620 \ldots 969933 010261$

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .