8
$\begingroup$

  • Using my computer, I found that the most of positive integer number $x$ such that $a_1=x$ and $a_n=2a_{n-1}+1$ is prime number after a few iterations. But exist some positive integer numbers, my computer can not checked this propety. For example, let $x=490$ then $a_1$, $a_2$, $\cdots$, $a_{60}$ are not prime number.

  • Can exist a positive integer number $x$ such that $a_1=x$ and $a_n=2a_{n-1}+1$ are not prime for all $n \ge 1$?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Note that $a_n = (x+1)*2^{n-1} - 1$. $\endgroup$
    – Dieter Kadelka
    Commented Jul 3 at 10:26
  • 1
    $\begingroup$ In the OP example $x=490$, it is true that $a_n$ is not prime for $n\le 46$, however $a_{47} = 34551053391233023$ is prime, according to GP/PARI isprime function. $\endgroup$
    – Claude Chaunier
    Commented Jul 3 at 11:57
  • 1
    $\begingroup$ @ClaudeChaunier Thanks you very much. Maybe my program fail or not accuracy. $\endgroup$
    – Đào Thanh Oai
    Commented Jul 3 at 12:10
  • 5
    $\begingroup$ Per Dieter's comment, these are precisely $x$ such that $x+1$ is a Riesel number. $\endgroup$
    – Wojowu
    Commented Jul 3 at 12:51
  • 1
    $\begingroup$ According to the link in Wojowu's comment it still seems open to determine the smallest Riesel number. $\endgroup$
    – Dieter Kadelka
    Commented Jul 3 at 12:59

2 Answers 2

Reset to default
18
$\begingroup$

There are values of $x$ for which $a_n$ is never prime. Specifically, I will show that we can choose $x$ such that $a_n$ is always divisible by one of the primes $3$, $5$, $17$, $257$, $65537$, $641$ or $6700417$. These are the prime factors of $2^{64}-1$.

Note that, for $p$ one of these primes, the values of $2^j \bmod p$ repeat modulo $2$, $4$, $8$, $16$, $32$, $64$ and $64$ respectively. If we use the Chinese Remainder Theorem to choose $x$ appropriately modulo these primes, then we can arrange that $$a_n \equiv 0 \bmod \begin{cases} 3 & \text{if}\ n \equiv 1 \bmod 2 \\ 5 & \text{if}\ n \equiv 2 \bmod 4 \\ 17 & \text{if}\ n \equiv 4 \bmod 8 \\ 257 & \text{if}\ n \equiv 8 \bmod 16 \\ 65537 & \text{if}\ n \equiv 16 \bmod 32 \\ 641 & \text{if}\ n \equiv 32 \bmod 64 \\ 6700417 & \text{if}\ n \equiv 0 \bmod 64 \\ \end{cases}.$$

This covers all residue classes modulo $64$, so $a_n$ will never be prime.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Great insight. This yields $x = 5870726654493916467$. $\endgroup$
    – Claude Chaunier
    Commented Jul 3 at 12:43
  • 1
    $\begingroup$ I understand the proof, but I'm confused as to what “makes it work”. How difficult is it to find $n$ such that we can cover the residue classes mod $n$ by arithmetic sequences with difference $r_i$ where $r_i$ is the multiplicative order of $2$ mod $p_i$ where $p_i$ are the prime factors of $2^n-1$ (if I correctly summarized what property of $n=64$ is being used here)? Do you have additional insight to share? (Maybe this should be a separate question.) $\endgroup$
    – Gro-Tsen
    Commented Jul 3 at 12:56
  • 1
    $\begingroup$ My first heuristic was that I needed to find primes $p_i$ with $\text{ord}_2(p_i) = r_i$ and $\sum \tfrac{1}{r_i} >1$, since then residue classes modulo $r_i$ would be "enough" to cover. So I tried $p_i=3,5,7,13$, with $r_i = 2,4,3,6$. But I found that the resulting residue classes modulo $12$ overlapped too much. I saw that this would be better if, for each $r_i$ and $r_j$, either $r_i | r_j$ or vice versa. This suggested taking the $r_i$ to be powers of $2$, so that suggested factoring $2^{2^k}-1$. Then I remembered that $2^{32}+1$ isn't prime, so I tried $2^{64}-1$. $\endgroup$
    – David E Speyer
    Commented Jul 3 at 13:10
  • $\begingroup$ In general, given positive integers $\{ r_1, r_2, \ldots, r_k \}$, I don't know when we should expect to be able to find residue classes $b_i$ such that the arithmetic progressions $b_i + r_i \mathbb{Z}$ cover $\mathbb{Z}$. $\endgroup$
    – David E Speyer
    Commented Jul 3 at 13:12
  • 4
    $\begingroup$ This argument goes back to the work of Erdős (renyi.hu/~p_erdos/1950-07.pdf) where he proved that if $m$ is an odd integer lying in a certain arithmetic progression, then $2^n+m$ is never prime. Also, a considerable research effort goes into studying covering systems of congruences, and this line of research was also initiated by Erdős. See en.wikipedia.org/wiki/Covering_system $\endgroup$
    – GH from MO
    Commented Jul 3 at 16:20
9
$\begingroup$

From https://en.wikipedia.org/wiki/Riesel_number "a Riesel number is an odd natural number $k$ for which ${\displaystyle k\times 2^{n}-1}$ is composite for all natural numbers $n$."

"In 1956, Hans Riesel showed that there are an infinite number of integers $k$ such that ${\displaystyle k\times 2^{n}-1}$ is not prime for any integer $n$. He showed that the number $509203$ has this property, as does $509203$ plus any positive integer multiple of $11184810$."

Riesel numbers are generally found by producing covering sets, as in David Speyer's answer.

According to https://oeis.org/A040081/b040081.txt the smallest $n$ for which $491\times2^n-1$ is prime is $46$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I can repeat my comment below David E Speyer's post. All this is essentially due to Erdős. $\endgroup$
    – GH from MO
    Commented Jul 4 at 16:02

You must log in to answer this question.

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