Timeline for 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$?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5 at 16:37 | comment | added | GH from MO | @GerryMyerson I agree that Erdős introduced covering systems in his 1950 paper. I was misled by the corresponding Wikipedia page quoted above which says "The notion of covering system was introduced by Paul Erdős in the early 1930s", and the fact that the problem solved by Erdős in 1950 was originally asked from him by Romanoff in 1934. | |
| Jul 5 at 15:50 | comment | added | GH from MO | @GerryMyerson Erdős proved that there exists an arithmetic progression $r+q\mathbb{Z}\subset 1+2\mathbb{Z}$ and a finite set $P$ of primes such that $\forall m\in r+q\mathbb{Z}:\forall n\in\mathbb{N}:\exists p\in P:p\mid m-2^n$. Writing $\ell:=-m$, we get that $\forall \ell\in -r+q\mathbb{Z}:\forall n\in\mathbb{N}:\exists p\in P:p\mid \ell+2^n$. | |
| Jul 5 at 5:08 | comment | added | Gerry Myerson | @GHf, your statement is that there exists (an infinite arithmetic progression of odd) $m$ such that $2^n+m$ is never prime. Erdös proved there exists (an infinite etc.) $m$ such that $m-2^n$ is never prime. I don't see how a little algebra can show that these two statements are equivalent. As for the history, Romanov's paper is from 1934, Erdös' from 1950 (in connection, as you say, with Romanov's work from 1934). To the best of my knowledge, the 1950 paper was the first time Erdös, or anyone, used covering systems. I would like to see a citation of Erdös using covering systems in the 1930s. | |
| Jul 4 at 23:15 | comment | added | GH from MO | @GerryMyerson If you look into Erdős's paper, you will see that his argument really gives what I wrote in my previous comment above, and it uses covering systems of congruences. Note that the equation $2^n+p=-m$ is equivalent to $2^n+m=-p$. With the same method, you can prove Riesel's theorem. The method (covering systems of congruences) was introduced by Erdős in the 1930s (in connection with Romanov's theorem I believe). So David E Speyer rediscovered or remembered an old method of Erdős. I haven't seen Riesel's paper, but chances are that Riesel was guided by Erdős's earlier work. | |
| Jul 4 at 22:48 | comment | added | Gerry Myerson | (continued) without using covering systems to find an arithmetic progression of them, I think. | |
| Jul 4 at 22:46 | comment | added | Gerry Myerson | @GHf, in that paper, Erdös proved there exists an arithmetic progression consisting only of odd numbers, no term of which is of the form $2^n+p$. I believe that's different from the statement you give. Also, odd numbers not of the form $2^n+p$ are not hard to find – $127$ is such a number – they are tabulated at oeis.org/A006285. Erdös, as you say, deployed covering systems to show there are arithmetic progressions of such numbers. By contrast, there is no easy way to find any Riesel numbers (or Sierpinski numbers, related to $k\times2^n+1$) (continued) | |
| Jul 3 at 16:20 | comment | added | GH from MO | 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 | |
| Jul 3 at 13:12 | comment | added | David E Speyer | 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}$. | |
| Jul 3 at 13:10 | comment | added | David E Speyer | 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$. | |
| Jul 3 at 12:56 | comment | added | Gro-Tsen | 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.) | |
| Jul 3 at 12:43 | comment | added | Claude Chaunier | Great insight. This yields $x = 5870726654493916467$. | |
| Jul 3 at 11:00 | history | answered | David E Speyer | CC BY-SA 4.0 |