2
$\begingroup$

Can the number of terms of sequence $p_1$, $2p_1+1$, $2(2p_1+1)+1$, . . . be more than 3? Where all terms are prime.

For primes $p_1\equiv 1 mod 3$ we have:

$2p_1+1\equiv (2+1) mod 3 \equiv 0 mod 3$

So eligible primes to produce new primes must be of the form $3k-1$ such that:

$p_1\equiv -1 mod 3$$p_2=2p_1+1 \equiv (-2+1=-1) mod 3$

$p_3=2(2p_2)+1\equiv -1 mod 3$

And it will give numbers $p_n\equiv -1 mod 3$ if we continue.

So we expect number of terms being prime not limited.But I could not find number of terms more than 3. here are some examples:

$p_1=11$$p_2=2\times 11+1=23$$p_3=2\times 23+1=47$ $p_4=2\times 47=95$

$p_1=41$$p_2=2\times 41+1=83$$2\times 83+1=167$$2\times 167+1=235$

My conjecture is that the number of terms of such sequence can not be more than 3, Can some one gives a counter example?

$\endgroup$
2
  • 7
    $\begingroup$ $5, 11, 23, 47$? They are related to Sophie-Germain/Safe Primes and Cunningham Chains. $\endgroup$
    – player3236
    Oct 26, 2020 at 16:23
  • $\begingroup$ Please do not edit your question in such a way that invalidates answers after they have been provided. Instead, if you have another question, use the "Ask Question" button to ask that question. $\endgroup$
    – Xander Henderson
    Oct 26, 2020 at 21:47

2 Answers 2

5
$\begingroup$

Define sequence $\{p_n\}_{n\in\mathbb{N}}$ as follows: $p_1=q$ where $q$ is some prime number and $p_{n+1}=2p_n+1$ for $n\geq 1$. The question is whether there is a prime $q$ such that all $p_n$ are prime numbers (for all $n\in\mathbb{N}$). We claim that there is no such $q$.

Suppose the contrary. Firstly, we will obtain explicit formula for $p_n$. Indeed, note that $p_{n+1}+1=2(p_n+1)$ for $n\geq 1$, so $$ p_{n+1}+1=2(p_n+1)=2^2(p_{n-1}+1)=\ldots=2^n(p_1+1)=(q+1)\cdot 2^n. $$ Hence, $p_{n}=(q+1)\cdot 2^{n-1}-1$ for $n\geq 1$.

Now if $q>2$, we will consider $p_{q}$. Note that $$ p_{q}=(q+1)\cdot 2^{q-1}-1\equiv 2^{q-1}-1\equiv 0\pmod q $$ due to Fermat's Little Theorem. However, $p_q$ is prime, so $p_q=q$ but this impossible because $q>1$.

It remains to consider case $q=2$. In this case, $p_n=3\cdot 2^{n-1}-1$, so $p_6=3\cdot 32-1=95=5\cdot 19$ is not prime.

Thus, there is no such $q$ and such a sequence cannot be infinite.

$\endgroup$
2
  • 1
    $\begingroup$ Minor error: the sequence for $q = 2$ goes $2, 5, 11, 23, 47, 95, \dots$; there's no 25. $\endgroup$ Oct 26, 2020 at 18:35
  • $\begingroup$ Thanks, edited. $\endgroup$
    – richrow
    Oct 26, 2020 at 21:00
3
$\begingroup$

The previous question was can the number of terms in the sequence be more than $3$:

The comment has answered the question by giving an example.

Out of curiosity, I have written a simple code to print out some of such sequences:

import math
def checkprime(num):
    if num > 1:
       for i in range(2,int(math.sqrt(num))+1):
           if (num % i) == 0:
               return False
               break
       else:
          return True
        

print([2, 5, 11, 23, 47])
print([5, 11, 23, 47])
for i in range(29, 10000,30):
    tmp = []
    j = i
    while checkprime(j):
        tmp.append(j)
        j = 2*j + 1
    if len(tmp) > 3:
        print(tmp)

Here are some of the prime sequences satisfying the condition:

[2, 5, 11, 23, 47]
[5, 11, 23, 47]
[89, 179, 359, 719, 1439, 2879]
[179, 359, 719, 1439, 2879]
[359, 719, 1439, 2879]
[509, 1019, 2039, 4079]
[1229, 2459, 4919, 9839]
[1409, 2819, 5639, 11279]
[2699, 5399, 10799, 21599]
[3539, 7079, 14159, 28319]
[6449, 12899, 25799, 51599]
$\endgroup$
2
  • 1
    $\begingroup$ Note that primes ending in the digits $1,3,7$ necessarily start a chain that yields a number ending in $5$, which is not prime and terminates the chain. Longer chains are possible only for primes ending in the digit $9$. $\endgroup$ Oct 26, 2020 at 17:15
  • $\begingroup$ thanks for the input, from the chinese remainder theorem, besides the chain starting from $2$ and $5$, the rest must begins with $29 \pmod{30}$ then. $\endgroup$ Oct 26, 2020 at 17:31

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.