Smallest prime of the form 41033333333...? 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 ...
 A: 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. 
A: 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.
A: The smallest prime of the form 410333…333 is 410(3^37398), i.e. 410333…333 with 37398 3’s, this prime is only probable prime, i.e. not proven prime, the formula of the form 410333…333 is (1231*10^n-1)/3, which is the generalized Riesel problem base 10 with k=1231, see this page, this page shows that for all k<3340, all k not having covering set except k=2452 have known primes or probable primes of the form (k*10^n-1)/gcd(k-1,10-1) with n>=1, and this prime is equal to (1231*10^37398-1)/3.
