Integers $j>0$ with no prime among $2^j-2^k-1$ for $0\le k<j$

number theoryprime numberssequences-and-series

Let $\mathcal S$ be the set of integers $j>0$ such that there exists no prime among the $j$ integers $2^j-2^k-1$ for $0\le k<j$.

The terms1 to $2^{12}$ are:

1 7 15 23 27 31 37 39 43 55 58 63 71 79 82 91 95 111 123 127 133 135 139 143 148 151 159 167 169 172 173 175 179 183 191 195 199 207 211 223 239 255 286 295 313 316 319 335 337 351 367 373 383 406 415 417 433 435 447 455 461 463 479 483 487 493 495 497 505 511 517 523 527 543 551 559 571 575 578 583 587 591 599 603 607 615 623 635 639 643 651 655 671 673 679 682 687 703 711 715 735 739 742 745 751 767 771 783 787 799 803 805 807 811 815 823 827 831 839 847 863 867 871 887 895 911 915 923 927 943 959 963 967 975 991 999 1006 1007 1011 1015 1023 1027 1033 1039 1043 1047 1051 1055 1063 1071 1087 1095 1097 1103 1111 1115 1119 1123 1127 1135 1141 1151 1157 1167 1183 1191 1193 1199 1203 1213 1219 1229 1243 1247 1251 1263 1267 1279 1285 1287 1295 1299 1303 1311 1319 1327 1339 1343 1347 1351 1357 1359 1375 1383 1387 1407 1415 1423 1431 1438 1439 1455 1459 1471 1486 1487 1491 1495 1503 1519 1535 1543 1551 1555 1567 1575 1577 1583 1587 1591 1599 1607 1611 1615 1630 1631 1647 1651 1663 1666 1667 1671 1675 1685 1687 1695 1699 1703 1711 1713 1719 1723 1727 1741 1743 1755 1767 1773 1775 1791 1795 1803 1807 1815 1823 1827 1831 1847 1855 1877 1887 1911 1919 1939 1947 1951 1967 1979 1990 1999 2003 2007 2015 2026 2031 2047 2063 2075 2079 2091 2095 2099 2111 2127 2137 2143 2153 2159 2165 2175 2188 2191 2211 2223 2231 2239 2257 2263 2271 2295 2303 2311 2314 2319 2323 2335 2343 2351 2367 2375 2379 2383 2399 2407 2415 2422 2429 2431 2447 2463 2479 2487 2495 2503 2519 2527 2535 2543 2554 2557 2559 2575 2591 2607 2619 2623 2631 2647 2659 2663 2671 2687 2699 2703 2711 2719 2735 2751 2755 2767 2775 2783 2787 2791 2803 2815 2831 2847 2855 2859 2863 2867 2871 2873 2879 2895 2911 2927 2935 2942 2951 2967 2971 2975 2991 2995 2999 3007 3015 3019 3039 3063 3067 3071 3079 3095 3103 3107 3111 3115 3130 3135 3139 3142 3147 3151 3159 3163 3167 3171 3175 3179 3183 3199 3207 3215 3219 3231 3246 3251 3263 3271 3279 3283 3295 3303 3311 3316 3327 3335 3343 3351 3359 3375 3387 3391 3403 3407 3411 3423 3427 3431 3435 3447 3455 3457 3467 3471 3479 3487 3495 3497 3499 3503 3506 3507 3509 3515 3517 3519 3527 3535 3544 3551 3555 3567 3579 3583 3599 3627 3631 3639 3647 3651 3663 3667 3671 3675 3679 3683 3687 3695 3699 3701 3703 3711 3735 3737 3739 3751 3759 3773 3775 3787 3791 3795 3807 3817 3823 3831 3835 3839 3847 3855 3867 3871 3875 3887 3895 3898 3903 3907 3911 3913 3917 3919 3927 3935 3939 3943 3949 3951 3959 3963 3967 3975 3982 3983 3987 3993 3999 4011 4015 4019 4023 4027 4031 4047 4059 4063 4067 4087 4095

Can we prove that $\mathcal S$ is infinite?

In the above first $532$ terms, only $30$ are even, only $6$ are multiple of $2^2$, only $1$ is multiple of $2^3$. With $j\le12000$, only $j=3544$, $6304$, $10520$, $11560$ are multiple of $2^3$, with only $j=6304$ multiple of $2^4$ (and $2^5$). Why do terms multiple of $2^i$ dry out so fast ?

More generally, can we explain the irregular distribution of $j\bmod2^i$ for $j\in\mathcal S$ ? Here it is for $i=3$ and the terms to $2^{12}$:
$$\begin{array}{l|rrrrrrr}
j\bmod2^3&0&1&2&3&4&5&6&7\\
\hline
\text{# with }j<2^{12}&1&24&11&121&5&27&13&330\\
\text{proportion}&0.002&0.045&0.021&0.227&0.009&0.051&0.024&0.620
\end{array}$$

Notes:

  1. For example, $7\in\mathcal S$ because $2^7-2^0-1=126\equiv0\pmod2$, $2^7-2^1-1=125\equiv0\pmod5$, $2^7-2^2-1=123\equiv0\pmod3$, $2^7-2^3-1=119\equiv0\pmod7$, $2^7-2^4-1=111\equiv0\pmod3$, $2^7-2^5-1=95\equiv0\pmod5$, $2^7-2^6-1=63\equiv0\pmod3$.
    And $8\not\in\mathcal S$ because $2^8-2^2-1=251$ is prime.
  2. Primes of the form $2^j-2^k-1$ are among the simplest Solinas primes, and are commonly used for Elliptic Curve Cryptograpy in prime fields, for they allow efficient modular reduction: e.g. M-221, Curve1174, Curve41417, Ed448-Goldilocks, E-521; see SafeCurves.
  3. The sequence is not in OEIS at time of writing, which suggests it has not been extensively studied.

Best Answer

Incomplete answer, work in progress ...

One very suspicious thing is that $\{7,15, 31, 63, 127, 255, 511, 1023, 2047, 4095\} \subset S$. It would indicate that $2^{n}-1 \in S, \forall n\geq3$ or $$2^{2^{n}-1}-2^k-1$$ is composite for $0\leq k<2^{n}-1$. If it is true, then cardinality of $S$ is not finite.

Proposition 1. If $k$ is even, then $3 \mid 2^{2^{n}-1}-2^k-1$

From $$2\equiv -1 \pmod{3}$$ we have $$2^{2^n-1}\equiv (-1)^{2^n-1} \equiv -1 \pmod{3}$$ $$2^{k}\equiv (-1)^{k} \equiv 1 \pmod{3}$$ Then $$2^{2^{n}-1}-2^k-1 \equiv -1-1-1 \equiv 0 \pmod{3}$$

Proposition 2. If $k=4q+1$, then $5 \mid 2^{2^{n}-1}-2^k-1$

From $$4\equiv -1 \pmod{5}\Rightarrow \\ 4^{2q}\equiv 2^{4q}\equiv (-1)^{2q}\equiv 1 \pmod{5}$$ then $$2^{4q+1}+1\equiv 3 \pmod{5}$$ $$2^{4q+3}\equiv 8 \equiv 3 \pmod{5} \tag{1}$$ or $$2^{2^{n}-1}-2^k-1 \equiv 2^{2^{n}-1} -3\equiv 3-3 \equiv 0 \pmod{5}$$ because $2^{2^{n}-1}$ is of the form $2^{4m+3}$, which is similar to $(1)$.

Let's look at the following case $k=4\color{red}{q}+3$ $$2^{2^{n}-1}-2^k-1= 2^{2^{n}-1}-2^{4q+3}-1=\\ 2\cdot4^{2^{n-1}-1}-8\cdot16^{q}-1=\\ 8\cdot16^{2^{n-2}-1}-8\cdot16^{q}-1 \tag{2}$$

Proposition 3. If $k=4\cdot\color{red}{2\cdot q_1}+3$, then $17 \mid 2^{2^{n}-1}-2^k-1$

From $$16\equiv -1 \pmod{17} $$ we have $$8\cdot16^{2^{n-2}-1} \equiv 8\cdot(-1)^{2^{n-2}-1} \equiv -8 \pmod{17}$$ $$8\cdot16^{q} \equiv 8\cdot16^{2q_1} \equiv 8\cdot(-1)^{2q_1}\equiv 8 \pmod{17}$$ from $(2)$ $$2^{2^{n}-1}-2^k-1 \equiv -8 -8-1 \equiv 0 \pmod{17}$$

What is left is $k=4\cdot(\color{red}{2\cdot q_1+1})+3$ ...

Related Question