# Smallest prime of the form 41033333333…?

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

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 ...

• What evidence do you have that there is a such a prime? – Thomas Andrews May 26 '13 at 20:01
• Do you mean $41033333333\cdot 10^k<p<41033333334\cdot 10^k$ or $3p=1231\cdot 10^k-1$? – Hagen von Eitzen May 26 '13 at 20:14
• Why are you interested? What have you tried? – draks ... May 26 '13 at 20:19
• 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. – user17762 May 26 '13 at 20:57
• 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. – 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.
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.