9
$\begingroup$

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

$\endgroup$
7
  • 10
    $\begingroup$ What evidence do you have that there is a such a prime? $\endgroup$ May 26, 2013 at 20:01
  • 5
    $\begingroup$ Do you mean $41033333333\cdot 10^k<p<41033333334\cdot 10^k$ or $3p=1231\cdot 10^k-1$? $\endgroup$ May 26, 2013 at 20:14
  • 6
    $\begingroup$ Why are you interested? What have you tried? $\endgroup$
    – draks ...
    May 26, 2013 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, 2013 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, 2013 at 21:12

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ Yes, with the "weak" interopretation of the ellipsis, the existence of small examples is no surprise. $\endgroup$ May 26, 2013 at 20:23
0
$\begingroup$

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.

$\endgroup$

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.