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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .