Open in Cloud | Download to Desktop via Attachments Below
The digit sum of a number is defined as the sum of the number's digits -- for example, the digit sum of 1753 is 1 + 7 + 5 + 3 = 16. Suppose we want to find a prime number with a specific digit sum, say 100. The first question we might ask is how large such a prime has to be.
Assume the prime has n digits, and that the digits are uniformly distributed across their possible values. The latter is not strictly true, but is a reasonable (and useful) approximation. The first digit ranges from 1 to 9, so its mean contribution to the digit sum is (1 + 2 + ... + 8 + 9) / 9 = 5. The last digit can only be 1, 3, 7 or 9, so its mean contribution is 5 as well. The n - 2 middle digits range from 0 to 9, so their mean contribution to the digit sum is 4.5. The expected number of digits in a prime with digit sum of 100 is then:
Solve[5 + 4.5 (n - 2) + 5 == 100.]
which Mathematica evaluates as
{{n -> 22.}}
The following statement generates a list of 22-digit primes with digital sum equal to 100:
Select[Total[IntegerDigits[#]] == 100 &] @
Table[RandomPrime[{10^21, 10^22 - 1}], 500]
This produced a list of 29 primes, each of them with digit sum 100:
{4521257098793752154293, 9017327967050768510809, 3543471831774385676233,
4951733709836020590667, 5026500359626929375097, 4830276814937101295983,
4011907639876429249513, 6171811939300897296109, 5866137711153653636863,
8677001882936009545831, 4982358962465604851221, 3423014619370074987967,
8922054209057943887341, 1531029595478281847173, 4171093644776292816481,
7954066375059510903583, 8139443827613312593459, 3619554293242633643893,
5380882911097144908157, 5584139552066825826217, 4205239726768073229169,
3152572162924535569891, 4121557920549990576217, 8927457552171433903933,
5108738173157780358607, 8037860073637146096259, 1259940420399148246387,
6208576318302772942981}
After many runs, it seems that about 4.3% of 22-digit primes have digital sums equal to 100. Since the number of 22-digit primes is approximately LogIntegral[10.22] - LogIntegral[10.21] = 1.8x1020, there are around 7.7x1018 22-digit primes with digital sum equal to 100. This is something like the age of the universe in seconds -- an enormous number.
Smallest Prime
Next we might ask, what is the smallest prime with digit sum 100? Obviously it will have more than 11 digits, since the maximum digit sum of an 11-digit number is 99. Suppose we prepend the digit 1 to a string of eleven 9s. If this is a prime we can go home early:
PrimeQ[199999999999]
Unfortunately, Mathematica evaluates this as False. But to minimize the number of digits, we do want the number to have as many 9s as possible. Consider numbers containing ten 9s and an additional two digits that add up to 10. Are there any primes among them? The following code generates all such numbers, select the primes, and sorts them from smallest to largest:
num = Table[9, 10];
pList2 = Sort@
Select[PrimeQ]@
DeleteDuplicates@
Flatten@Table[
FromDigits[Insert[Insert[num, i, j], 10 - i, k]], {i, 1, 5}, {j,
1, 11}, {k, 1, 12}]
The result is a list of 57 primes:
{298999999999, 299899999999, 299999989999, 299999999989, 399979999999,
399999979999, 499999999699, 694999999999, 699999999499, 799399999999,
799999399999, 899929999999, 899999999929, 929899999999, 929999899999,
929999989999, 937999999999, 939979999999, 939999979999, 939999997999,
949969999999, 979999399999, 989929999999, 989999299999, 991999999999,
992989999999, 992999989999, 993799999999, 993999999997, 995999999959,
996999994999, 997993999999, 998992999999, 998999999929, 999299989999,
999499699999, 999499969999, 999799993999, 999929998999, 999969499999,
999969999949, 999989299999, 999992989999, 999992998999, 999993999997,
999995999599, 999997993999, 999999599959, 999999699499, 999999799399,
999999939997, 999999949969, 999999969499, 999999982999, 999999991999,
999999997939, 999999999937}
The smallest is 298999999999. Call this number p1. Can there be any prime smaller than p1 with digital sum of 100? Suppose there is one. If it exists, it too must have 12 digits.
Since the hypothetical prime is less than p1 and has the same number of digits, then at least one of its digits must be smaller than the corresponding digit in p1. If at least one digit is smaller, then to maintain the digital sum of 100, at least one digit must be larger than the corresponding digit in p1. But the only digit that can be larger is the 8, and it can only be 9.
If the 8 is increased to 9, then to maintain the digital sum of 100 one of the other digits must be decreased by 1. We could decrease the 2 to get 199999999999, but we've already seen that that is not a prime. The only other possibility is to change the second digit to an 8, giving 289999999999. But if this were a prime, it would occur in pList2. Since it does not, 298999999999 is the least prime with a digital sum of 100.
Largest Prime
What is the largest prime with digital sum 100? For this problem to have an answer, we must restrict ourselves to nonzero digits only. The obvious first choice is a string of 100 1s:
PrimeQ[FromDigits[Table[1, 100]]]
But Mathematica evaluates this as False. However, to maximize the number of digits we do want as many 1s as possible. We next look at numbers containing all ones and one other non-unit digit. For example, 98 1s and a 2, or 97 1s and a 3, etc. The code below generates all such numbers, selects those that are prime, and sorts them from smallest to largest:
plist3 = Sort@
Select[PrimeQ][
FromDigits /@
Flatten[Table[
Insert[Table[1, 100 - i], i, j], {i, 2, 9}, {j, 101 - i}], 1]]
The result is a list of 11 primes:
{111119111111111111111111111111111111111111111111111111111111111111111\
11111111111111111111111,
1111111111111111111111111111111111111111111111111111111111111111111111\
11111111111111118111111,
1111111111111117111111111111111111111111111111111111111111111111111111\
111111111111111111111111,
1111111111171111111111111111111111111111111111111111111111111111111111\
111111111111111111111111,
1111111117111111111111111111111111111111111111111111111111111111111111\
111111111111111111111111,
1711111111111111111111111111111111111111111111111111111111111111111111\
111111111111111111111111,
1111111111111111111111111111111111111111111111111111111111111111111111\
1111161111111111111111111,
1111111111111111111111111111111111111111111111111111111111111111111111\
11111111111111111151111111,
1111111111111111111111111111111111111111111115111111111111111111111111\
11111111111111111111111111,
1111111111111111113111111111111111111111111111111111111111111111111111\
1111111111111111111111111111,
1111111111111111111111111111111111111111111111112111111111111111111111\
11111111111111111111111111111}
The largest is 111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111111. Let's call this number p2. An argument similar to the one given for the smallest prime shows that p2 is the largest prime with nonzero digits and a digit sum of 100. For if there is a larger prime, it too will have 99 digits, meaning at least one of the digits will be larger than the corresponding digit in p2, and at least one other digit will be smaller. But the only digit that can be smaller is the 2, which would become a one. That means one of the other ones has to become a 2. Therefore the hypothetical prime must also have 98 1s and a 2. But the algorithm above found all such primes, and p2 is the only one. Thus there is no larger prime.
Attachments:
