Krdytkyu

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

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

Let $a(n)=(1231times 10^n-1)/3$. Then if a prime $p$ divides $a(n)$, then
$$
10^n equiv 1231^{-1} pmod{p} \
10^{n+kcdotmathrm{ord}_p10} equiv 1231^{-1} pmod{p} \
p mid a(n+kcdot mathrm{ord}_p10)
$$
where $mathrm{ord}_p10$ is the smallest exponent $i$ for which $10^iequiv 1pmod{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.