1
$\begingroup$

Is $4\underbrace{999 . . . 9}_{224 ({\rm times})}$ prime?

I wanted to find smallest prime its sum of digits is $2020$. I started with small primes; the smallest three digits prime its sum of digits is 22 is $499$; four digits is $4999$ with sum of digits 31, five digit is $49999$ with sum of 40.For the sum $2020$ we have:

$2020=224\times 9+4$ and desired number can be of the form $4\underbrace{999 . . . 9}_{224 ({\rm times})}$ . So this number has at least 225 digits. If it is not prime we have to search for numbers with number of digits more than 225 which of course have digits less than 9 and first digit probably less than 4. I could not check it with my computer. I have these questions:

1- is $4\underbrace{999 . . . 9}_{224 ({\rm times})}$ primes?

2- are numbers of the form $499 . . . 99$ always primes? If so what is theoretical reason? If not what is conditions for it to be prime?

Update: the closed form of these numbers is $N=5\times 10^n-1=5(10^n-1)+ 4$, $n ≥ 2$ if n is even we have:

$10^{2k}-1=(10^k-1)(10^k+1)$

Since $[10^n-1, 5, 4]=1$ N can be a prime, but brute force gives a counter result. If n is odd N can be composite.

$\endgroup$
8
  • 1
    $\begingroup$ $49$ is not prime $\endgroup$ – J. W. Tanner Mar 13 '20 at 17:09
  • $\begingroup$ 49...9? What about good ol' 7X7 as an answer for 2? $\endgroup$ – user756686 Mar 13 '20 at 17:11
  • $\begingroup$ @J.W.Tanner i think you misunderstood the question (although it's pretty clear). $\endgroup$ – Quang Hoang Mar 13 '20 at 17:13
  • $\begingroup$ To answer question #2, where the number of 9s is arbitrarily large, I don't see why there would be a known answer to that--isn't generating arbitrarily large primes an open question? $\endgroup$ – Mike Mar 13 '20 at 18:02
  • $\begingroup$ The sequence $a(n)=\text{A067180}$ is available in OEIS and collects smallest primes whose digit sum is $n$. Sadly, it goes up to $n=175$ only, so such smallest prime for $n=2020$ is not available there (at the moment). However, if you instead would satisfy yourself with the smallest prime whose sum of digits in binary is equal to $2020$, then the solution would be the prime number $2^{2021}-2^{1359}-1$, having $609$ (decimal) digits, according to sequence $b(n)=\text{A061712}$ which is available in OEIS. $\endgroup$ – Vepir Mar 13 '20 at 19:50
5
$\begingroup$

Answering the implicit question: what is the smallest prime with digit sum $2020$?

$\color{blue}{5}999999999999999999999999$
$9999999999999999999999999$
$999999999\color{blue}{8}999999999999999$
$9999999999999999999999999$
$9999999999999999999999999$
$9999999999999999999999999$
$9999999999999999999999999$
$9999999999999999999999999$
$9999999999999999999999999$ is prime.

Alternative form: $10^{225}-4\cdot10^{224}-10^{165}-1$

This is a single decimal number of $225$ digits written across $9$ lines of $25$ digits each. All digits are $9$ except for the initial $5$ and a single $8$ in the third line, so its digit sum is: $$225\cdot9-5=2020.$$

This is the highest placement of the $8$ that yields a prime number, so this is the smallest prime number with digit sum $2020$.

Edit: to explain the methodology in response to comments.

$224\cdot9<2020$ so we know that we need at least $225$ digits. We can start from $10^{225}-1$, which is $225$ nines, and we need to reduce the total digit sum by exactly $5$, reducing leading digits in preference to later digits and checking whether each number is prime.

The first number to check is $\color{blue}{4}999999\dots\;$ but we know this is not prime.

Next, check
$\color{blue}{58}99999\dots$
$\color{blue}{5}9\color{blue}{8}9999\dots$
$\color{blue}{5}99\color{blue}{8}999\dots$
$\color{blue}{5}999\color{blue}{8}99\dots$

and so on. Then, if needed, check
$\color{blue}{67}99999\dots$
$\color{blue}{688}9999\dots$
$\color{blue}{68}9\color{blue}{8}999\dots$
$\color{blue}{68}99\color{blue}{8}99\dots$

It turns out that the first prime found is the number given above. The number is equivalent to reducing the digit representing $10^{224}$ by $4$ and the digit representing $10^{165}$ by $1$. This gives us the alternative form of the number.

$\endgroup$
5
  • $\begingroup$ @nikgard, great job, how did you find the formula? Did you first find it by brute force and then formulated it? $\endgroup$ – sirous Mar 15 '20 at 17:12
  • $\begingroup$ How do you know whether $10^{225}-4\cdot10^{224}-10^k-1$ is a prime for $k=165$ and not a prime for $165 < k \leq 224$)? $\endgroup$ – Wolfgang Kais Mar 18 '20 at 11:52
  • $\begingroup$ @WolfgangKais All of those numbers were checked and found to be composite. I've added an edit to explain the methodology. $\endgroup$ – nickgard Mar 18 '20 at 15:37
  • $\begingroup$ @nickgard Thanks, but that explains the sequence of numbers chosen for testing, which I already understood, I believe, that when these numbers are composite, that someone might have found a divisor already, but how about the case $k=165$? Who proved that the resulting number is a prime (and HOW)? $\endgroup$ – Wolfgang Kais Mar 19 '20 at 1:14
  • $\begingroup$ @WolfgangKais There are plenty of mathematics packages available that can test primality. It's not necessary to find a divisor. I mostly use Sagemath (which in turn uses PARI/GP prime testing). Other possibilities are Maple, Mathematica, PFGW (which is specifically written for prime testing) and the GMP library for C programming. $\endgroup$ – nickgard Mar 19 '20 at 5:20
5
$\begingroup$

A computer search finds $4259\mid 5\times10^{224}-1$. I know of no elegant proof of this, just brute force.

$\endgroup$
7
  • $\begingroup$ could you fix your latex? $\endgroup$ – Luis Felipe Mar 13 '20 at 17:22
  • $\begingroup$ @LuisFelipe I don't see an issue; could you explain what needs fixing. $\endgroup$ – J.G. Mar 13 '20 at 17:23
  • $\begingroup$ for a strange reason,mathjax didnt render the latex for me :O $\endgroup$ – Luis Felipe Mar 13 '20 at 17:25
  • 1
    $\begingroup$ @LuisFelipe Ah. That happened to me on another SE page once, so I had to switch from my phone to my laptop to read it. $\endgroup$ – J.G. Mar 13 '20 at 17:29
  • 1
    $\begingroup$ @sirous That question probably can't be easily answered with present day theory. $\endgroup$ – J.G. Mar 13 '20 at 17:53
-1
$\begingroup$

is prime the form $N=5 \times 10^n-1$ is not prime if $n \neq1,7,13,19,25,...,n-1 \neq 6b$

$\endgroup$
10
  • $\begingroup$ $n \neq 7n$ doesn’t say what you want. $\endgroup$ – Ross Millikan Mar 13 '20 at 18:59
  • $\begingroup$ if n is multiple of 7 isn't prime $\endgroup$ – danfxang Mar 13 '20 at 19:03
  • $\begingroup$ That is what you meant, but reusing $n$ makes it $n \new 0$ $\endgroup$ – Ross Millikan Mar 13 '20 at 19:05
  • $\begingroup$ yes,you are right $\endgroup$ – danfxang Mar 13 '20 at 19:10
  • 2
    $\begingroup$ Divisible by 17 when n = 9 + 17b, by 19 if n =16+19b, by 23 if n = 7+23b, or by 29 if n = 10+29b. $\endgroup$ – gnasher729 Mar 13 '20 at 20:36

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.