What is the smallest prime of the form $410333333333...$ ? It should have more than $10,000$ digits.

[added from answer posted 2013 May 26 at 20:52 by Peter]

I thought it would be clear, but it seems not to be. Of course, after $410$, only $3$'s should follow. Otherwise, it would be very easy to find primes. I checked the numbers up to about $10,000$ digits, but of course, I would be glad if someone checks this, too.

I do not understand the question, WHY this number is interesting for me. Mersenne primes are not so much more interesting, but recently a prize of $100,000\$ $was payed for a community finding a $17$-million-digit mersenne prime. I would have better ideas what to do with all this money ...

  • 9
    $\begingroup$ What evidence do you have that there is a such a prime? $\endgroup$ – Thomas Andrews May 26 '13 at 20:01
  • 4
    $\begingroup$ Do you mean $41033333333\cdot 10^k<p<41033333334\cdot 10^k$ or $3p=1231\cdot 10^k-1$? $\endgroup$ – Hagen von Eitzen May 26 '13 at 20:14
  • 6
    $\begingroup$ Why are you interested? What have you tried? $\endgroup$ – draks ... May 26 '13 at 20:19
  • 3
    $\begingroup$ I assume the number you are interested in is of the form $$41 \cdot 10^{n+1} + \dfrac{10^n-1}3$$ If so, note that for odd $n$, $11$ divides the number. Hence, $n$ has to be even, for the number to be a prime. $\endgroup$ – user17762 May 26 '13 at 20:57
  • 5
    $\begingroup$ Also @user17762, since $37\mid41033$, $13\mid4103333$ and $13\cdot37\mid333333$ it follows that $n$ has to be a multiple of $6$, for the number to be prime. $\endgroup$ – P.. May 26 '13 at 21:12

I guess $(1231\times 10^{6\times 6233}-1)/3$, that is with 37,398 threes. (PFGW calls it a probable prime to base 2,3,5,7.)

Let $a(n)=(1231\times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then $$ 10^n \equiv 1231^{-1} \pmod{p} \\ 10^{n+k\cdot\mathrm{ord}_p10} \equiv 1231^{-1} \pmod{p} \\ p \mid a(n+k\cdot \mathrm{ord}_p10) $$ where $\mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^i\equiv 1\pmod{p}$. So for example $$ 11 \mid a(2k+1) \\ 41 \mid a(5k) \\ 35 \mid a(3k+2) \\ 47 \mid a(46k+10) $$ and so forth.

If $n_2$ satisfies one or more of these for a prime $p$ with $k>1$, then there must be a smaller $n_1$ with $k=0$ with $p \mid \gcd(a(n_2),a(n_1))$. Since GCD can be computed quickly, for $n>10368$ and divisible by 6 I identified candidates where $\gcd(a(n),a(i))=1$ for several choices of $i<n$. This eliminated about 95% of cases, I made a list of the rest and tested about 1000 before finding one that reported as a probable prime.


41033333333323 = 41033333333300 + 23 is prime. So is 4103333333333333333333000159.

Set $x= 4103333333333333333333...$ ($k$ times a 3). Then $\log x \approx 6 + 2.3 \cdot k$. By the Prime Number Theorem, you'll find a prime of the form $10^nx + r, \, r < 10^n$ with high probability (let's say 0.999999) if $10^n > 100 + 30k$ or so. That is, $n \ge 3 + \log_{10} k$ should be enough.

  • 6
    $\begingroup$ Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise. $\endgroup$ – Hagen von Eitzen May 26 '13 at 20:23

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.