In this question on MSE, Enzo Creti asks for a prime number formed by concatenating the Mersenne numbers $2^n-1$ and $2^{n-1}-1$, for example, 40952047. For all residues modulo 7, he found primes except for the residue 6. This is somewhat surprising because the residue 1 occurs only with half frequency.

Is there any hidden structure forcing a non-trivial factor in the case of residue 6, or was it just "bad luck" that no prime was found despite an enormous search range?

I invite everyone to join in the search for a prime. I posted the necessary details on github.

The following vector contains all numbers n<=366800 leading to a prime

[2, 3, 4, 7, 8, 12, 19, 22, 36, 46, 51, 67, 79, 215, 359, 394, 451, 1323, 2131, 3336, 3371, 6231, 19179, 39699, 51456, 56238, 69660, 75894, 79798, 92020, 174968, 176006, 181015, 285019, 331259, 360787, 366770]

Exponent $541456$ leads to another probable prime with residue 5 mod 7 and 325990 digits, but it need not be the next in increasing order. More details can be found on the github-site. Heuristically, for every k>=3 , the range [10^k..10^(k+1)] should contain 5.4 numbers leading to a prime, so the range [10^4..10^5] with 8 primes is "above average", whereas the range [10^3..10^4] is within the expectation. The sequences of exponents and associated primes are here: A301806 and here: A298613. I noticed these things: let's call ec(n)=$2^n-1$||$2^{n-1}-1$ where || denotes the concatenation in base 10.

ec(43*5) is prime. 5 (odd) is congruent to -8 mod 13. ec(43*1620) is prime. 1620 (even) is congruent to 8 mod 13. ec(43*2140) is prime. 2140 (even) is congruent to 8 mod 13. ec(43*12592) is prime. 12592 (even) is congruent to 8 mod 13. Moreover 43*5=41*5+10, 43*1620=41*1699+1, 43*2140=41*2244+16, 43*12592=41*13206+10. This implies that $\frac{43*5}{41}$, $\frac{43*1620}{41}$, $\frac{43*2140}{41}$, $\frac{43*12592}{41}$ will have a repeating term $\overline{02439}$ or in other words that they are of the form $41s+r$, where r is an integer in the set $(1,10,16,18,37)$

  • 1
    $\begingroup$ Note: a long comment thread has been moved to chat: chat.stackexchange.com/rooms/82777/… $\endgroup$ – Ben Webster Sep 5 '18 at 13:29
  • $\begingroup$ It is curious that $181015=(4*43*6^3-1)*4+32411$ and $366770=(4*43*6^3-1)*9+32411$, where $32411$ is a prime! $\endgroup$ – Enzo Creti Sep 15 '18 at 14:21
  • $\begingroup$ If an exponent leading to a prime is divisible by $139$, then it is also divisible by $6$. Examples are: $3336$ and $75894$. $\endgroup$ – Enzo Creti Sep 22 '18 at 17:44
  • $\begingroup$ @Aaron Meyerowitz note also that $3336$ and $75894$ $\equiv 1 \mod 29$ $\endgroup$ – Enzo Creti Sep 22 '18 at 18:38
  • $\begingroup$ If an exponent leading to a prime is divisible by $41$, then it is $\equiv 1 \mod 6$. Examples are $451$ and $181015$. Infact $451$ and $181015$ are divisible by $41$ and both are $\equiv 1 \mod 6$. $\endgroup$ – Enzo Creti Sep 23 '18 at 13:39

Hidden structure can be interesting. In this case it seems unlikely because the it involves $m$, the number of decimal digits of $2^k-1$ which is not random but also not structured. And the relevant statistic is (perhaps) $10^m \mod 7.$ From what you say there are few enough primes found so far that the lack of any $6 \bmod 5$ is not all that suspicious. One might suspect that there are infinitely many primes and $1/9$ of them are $6 \bmod 5$ in the long run. But also that the gaps between them grow exponentially so one might not see only a couple of new primes in a lifetime.

Here is a slightly more general setting which might give perspective: A repunit in base $b$ is a number $r_b(k)=\frac{b^k-1}{b-1}$ I.e. one with all $k$ base $b$ digits one. They are prime only if $k$ is prime. Their factorization (for small $b$) is an active project since 1925 with some pretty nice mathematics involved. There is a top priority list of most wanted factorizations as well as next highest more wanted.

So one might write the base $b$ repunits $r_b(k+1)$ and $r_b(k)$, in that order, in base $c$, concatenate, and ask about primality. You ask about the case $b=2,c=10$ , but why those two bases and ,also, why not the other order? Why not a zero in the middle?

I was going to say that questions based on a particular base are less interesting mathematically. I guess it is hard to generalize:

Palindromatic primes , particularly in base 10 (and even more so ones like 3,313 built from the decimal digits of $\pi$ ) might strike me as pretty recreational, but you can see from the link that they have gotten a certain measure of attention.

I was going to offer that concatenation for the case $b=c$ would feel more mathematical. I quickly realized that it certainly is mathematical but not new!

I took a quick look at these for $2\leq k \leq 1441$ where we might expect to get $0,1 \bmod 7$ 80 times each, $2,4,5,6$ $160$ times each and $3 \bmod 7$ $640$ times. That happens except it is $79,641$ for $1,3.$

The primes occur for $k=2,3,4,7,8,12,19,22,36,46,51,67,79,215,359,394,451$ and $1323.$

Ignoring the last one which is $3 \bmod 7$, We might expect to get $\bmod 7$ counts of around $1,2,8,2,2,2$ for the first $17. $ It comes out $2,4,7,2,2,0$

That seems well within what might happen by chance and one would expect primes to be increasingly sparse going forward.

Do you have further data? Out of the next $N$ prime values we might expect $2N/17$ to be $6 \bmod 7.$ Do you have enough that the lack of primes of this sort is remarkable? Given how far your search has gone, how much further would you expect to have to go to have a fair chance of finding one?

  • 1
    $\begingroup$ Thanks for your answer. r.e.s (who checked the range upto 10^5) found some further primes, unfortunately, the list has been deleted. It is true that the number of primes found is not significant, and I also think that it is pure coincidence. I just asked this question to see whether I have overlooked something. $\endgroup$ – Peter Mar 7 '18 at 10:56
  • $\begingroup$ @EnzoCreti Maybe try other mixes of bases. If I have it right then the probability that none of these first $35$ would be $6 \bmod 7$ is less than getting $6$ heads in a row from a fair coin but more than that of getting $7$ in a row. $\endgroup$ – Aaron Meyerowitz Jul 17 '18 at 13:16
  • $\begingroup$ distribution of residues (mod 7) up to k=366800: [3,6,17,3,8,0] $\endgroup$ – Enzo Creti Aug 27 '18 at 9:31
  • $\begingroup$ Passed 428k no prime 6 mod 7 found $\endgroup$ – Enzo Creti Sep 3 '18 at 11:44
  • 1
    $\begingroup$ @Robert Frost@Aaron Meyerowitz the first four primes of this form are also emirp: infact $31,73,157,12763$ reversed are $13,37,751,36721$ which are all primes. $\endgroup$ – Enzo Creti Nov 5 '18 at 13:49

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.