2
$\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$ Mar 13, 2020 at 17:09
  • $\begingroup$ 49...9? What about good ol' 7X7 as an answer for 2? $\endgroup$
    – user756686
    Mar 13, 2020 at 17:11
  • $\begingroup$ @J.W.Tanner i think you misunderstood the question (although it's pretty clear). $\endgroup$ Mar 13, 2020 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, 2020 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, 2020 at 19:50

3 Answers 3

7
$\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, 2020 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$ Mar 18, 2020 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, 2020 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$ Mar 19, 2020 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, 2020 at 5:20
6
$\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$
    – L F
    Mar 13, 2020 at 17:22
  • $\begingroup$ @LuisFelipe I don't see an issue; could you explain what needs fixing. $\endgroup$
    – J.G.
    Mar 13, 2020 at 17:23
  • $\begingroup$ for a strange reason,mathjax didnt render the latex for me :O $\endgroup$
    – L F
    Mar 13, 2020 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, 2020 at 17:29
  • 1
    $\begingroup$ @sirous That question probably can't be easily answered with present day theory. $\endgroup$
    – J.G.
    Mar 13, 2020 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$ Mar 13, 2020 at 18:59
  • $\begingroup$ if n is multiple of 7 isn't prime $\endgroup$
    – danfxang
    Mar 13, 2020 at 19:03
  • $\begingroup$ That is what you meant, but reusing $n$ makes it $n \new 0$ $\endgroup$ Mar 13, 2020 at 19:05
  • $\begingroup$ yes,you are right $\endgroup$
    – danfxang
    Mar 13, 2020 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, 2020 at 20:36

You must log in to answer this question.

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