Primeval NumbersIntegers containing many embedded primes

Mike Keith, July 1998

IntroductionA well-known word recreation involves taking a word or phrase, such as INTEGER, and asking for all the words that can be made using its letters (such as ENTIRE, GREEN, TREE, etc.). In this paper we consider this same process applied to the digits of an integer, and we seek integers in which many prime numbers can be formed using subsets of its digits. For example, in the rather small integer 1379 we can find as many as thirty-one primes:

3 7 13 17 19 31 37 71 73 79 97 137

139 173 179 193 197 317 379 397 719 739 937 971

1973 3719 3917 7193 9137 9173 9371

(Note that, just like in the word game, we can only use as many of each digit as are present in the original number. Also, the numbers 0 and 1 are not considered primes.)

Which integers are the most

primeval- i.e., contain the largest number of prime numbers? What’s the smallest integer containing all two-digit primes? It is this type of question we consider in this paper.

Primeval NumbersWe used a computer program to examine all integers up to 100000 and count how many primes each contains. As we proceed through the integers (1, 2, 3, ...), an integer that sets a new record for the number of primes contained is called a

primeval number. Here is a table of the primeval numbers less than 100000, with the number of primes contained in each:

Primeval Integer

No. Primes Contained2

1

13

3

37

4

107

5

113

7

137

11

1013

14

1037

19

1079

21

1237

26

1367

29

1379

31

10079

33

10123

35

10136

41

10139

53

10237

55

10279

60

10367

64

10379

89

12379

96

13679

106

Table 1.All primeval numbers less than 100,000.

Another interesting sequence is, for each

N, to ask forthe smallest N-digit integer that contains the maximum number of primes possible for that N. From the above table we can see that this sequence begins2, 37, 137, 1379, 13679, ...

while the maximum number of primes contained in an

N-digit integer is1, 4, 11, 31, 106, ...

Note that the theoretical maximum possible number of primes contained in an

N-digit integer is the sum fork= 1 toNofP(N,k), the number of permutations ofNthings takenkat a time, corresponding to the case when every permutation of every substring of the integer is a prime. This sequence is1, 4, 15, 64, 325, ...

from which we see that, apparently, only for

N=1 and 2 is the theoretical maximum achieved. In fact, we have a stronger theorem:

Theorem.73 is the largest integer with the property that all permutations of all of its substrings are primes.

Proof:By enumeration, there are only two such two-digit integers (37 and 73), and there are none with three digits. We now prove that there cannot be such an integer with four or more digits.The key is the well-known property that a number is divisible by 3 if and only if the sum of its digits is divisible by three. Suppose we have a four (or more) digit number with all substrings being prime. At most one of its digits can be equal to 0 mod 3, because if there were two (say

aandb) then the two-digit pairabwould be divisible by 3, and hence not all substrings would be prime. Suppose the digita= 0 mod 3, and consider three other digitsb,c,d(none of which can equal 0 mod 3). There are four cases, depending on how many (0, 1, 2, or 3) of these are equal to 1 mod 3 (the rest must equal 2). If none of them equal 1 mod 3, thena+b+c= 6 = 0 mod 3, soabcis composite. Ifa= 1 mod 3, thena+b= 3 = 0 mod 3, soabis composite. Similar arguments work for the other two cases. Therefore, no ³ 4-digit number can have all its substrings be primes, and the proof is complete.

We can also seek the smallest integer containing

exactlykprimes, for eachk ³1. Here are the first 30 values of this function (fork= 1, 2, 3, etc.):2 25 13 37 107 127 113 167 1027 179

137 1036 1127 1013 1137 1235 1136 1123 1037 1139

1079 10124 10126 1349 1279 11237 3479 10699 1367 10179

For every value of

kso far (we have checked up tok=66) we have found at least one integer that contains that many primes, which leads to the following:

Conjecture:There is an integer containing exactlykprimes for every value ofk.We can go back to Table 1 and see which of the numbers in the left column are themselves prime; this gives the sequence of

primeval primes:2, 13, 37, 107, 113, 137, 1013, 1237, 1367, 10079, 10139, 12379, 13679, ...

The majority, but not all, of the Table 1 numbers are primes. Challenge for the reader: is there a formula for the asymptotic value of (number of primeval primes)/(number of primeval numbers)? Is this the same or different from the asymptotic density of primes among all integers?

k-Primeval NumbersAs we proceed through the primeval numbers, finding integers that contain more and more primes, we expect that eventually we will find an integer containing

allthe one-digit primes, all the two-digit primes, etc. We can eschew the property of containing many primes and just look for integers that contains allk-digit primes. We call such an integer ak-primeval number, and if it is itself prime we call it ak-primeval prime.One basic question is: what’s the smallestk-primeval number andk-primeval prime, for eachk?Finding the smallest

k-primeval number is fairly trivial. We merely need to count up how many of each decimal digit is required in order to be able to form anyk-digit prime with those digits. For each digitd, the number ofd’s we need is the largest number ofd’s that occurs in anyk-digit prime. Here is a table of the number of each digit required for the first few values ofk:Digit: 0 1 2 3 4 5 6 7 8 9k=1 0 0 1 1 0 1 0 1 0 02 0 2 1 1 1 1 1 1 1 13 1 2 2 2 2 2 2 2 2 2 **4 2 3 3 3 3 3 3 3 3 3 **5 3 4 4 4 4 3 3 4 4 46 4 5 4 5 5 5 5 5 5 5from which the sequence of

minimal k-primeval numbersfollows:2357, 1123456789, 1012233445566778899, 10011222333444555666777888999, ...

Much more interesting are the minimal

k-primeval primes. Determining these requires finding the permutation of the corresponding minimalk-primeval number, with smallest value, that yields a prime - if there is one. In the two cases marked with an asterisk in the table above, there is no such permutation because the sum of the digits in the minimalk-primeval number is a multiple of 3, which means all of its permutations are composite. In these two cases we were able to find a prime by adjoining a single "1" digit (the minimum possible) to thek-primeval number, and then finding a prime permutation. The first fourminimal k-primeval primes(fork= 1,2,3,4), which I computed in July 1998, are:2357

1123465789

10112233445566788997

100111222333444555666777998889Since these numbers grow rapidly, let's use a shorthand notation to represent them more compactly. The 4-primeval prime at the bottom of the list above would be written in this notation as (1) 2 3 3 3 3 3 3 3 0 998889. The (1) represents the leading 1 digit (which will always be present). The next number says how many consecutive 0's follow the leading 1, and the next says how many consecutive 1's follow that, and so on up to the number of consecutive 8's. The final grouping explicitly shows how the last group of 8's and 9's are arranged.

In early 2002 Jerome Storti wrote a much more powerful program for this problem and computed the minimal

k-primeval primes up ton=31. Here they are, in the compact notation:kMinimalk-primeval prime5 (1) 3 3 4 4 4 3 3 4 0 98889899 6 (1) 4 4 4 5 5 5 5 5 4 999989 7 (1) 5 5 5 6 5 5 5 6 3 98899999 8 (1) 5 6 7 7 6 7 7 7 6 98999999 9 (1) 7 7 8 8 8 7 8 8 6 9999989899 10 (1) 8 8 8 9 9 9 9 9 7 9999899999 11 (1) 8 9 10 10 10 9 10 10 6 9889989999999 12 (1) 10 10 10 11 11 11 10 11 9 9998999999899 13 (1) 10 11 11 12 11 12 11 12 9 99899999999899 14 (1) 11 13 13 13 12 12 12 13 11 989999989999999 15 (1) 12 13 14 14 13 14 13 14 12 9999999988999999 16 (1) 13 14 14 15 14 14 14 15 12 99999999999999889 17 (1) 14 15 15 16 15 15 15 16 14 998999999999998999 18 (1) 16 17 17 17 16 17 17 17 14 9989999999999899999 19 (1) 17 18 17 18 17 17 17 18 15 988999999899999999999 20 (1) 17 19 18 19 19 18 19 19 16 999999998999999999989 21 (1) 18 19 19 20 19 19 20 20 17 9899999999999999998999 22 (1) 18 20 20 21 20 21 21 21 18 99998999999999999998999 23 (1) 21 23 21 22 21 21 22 22 19 999999889999999999999999 24 (1) 20 22 22 23 22 22 22 23 21 999999999999999989999999 25 (1) 23 23 23 24 23 23 23 24 22 9999999999999999998999999 26 (1) 23 24 24 25 25 25 24 25 22 999999999999999999899999989 27 (1) 24 25 25 26 25 25 25 26 23 9999999998999999999999998999 28 (1) 25 26 27 27 27 26 27 27 25 9999899999999999999999999999 29 (1) 25 27 27 28 27 27 27 28 25 999999989999999999999999999989 30 (1) 26 29 28 29 29 28 28 29 27 999999999999998999999999999999 31 (1) 28 29 29 30 29 29 29 30 27 99999889999999999999999999999999Note that

k=1 is the only value ofkso far where the minimalk-primeval integer (2357) is the same as the minimalk-primeval prime.We close with an observation inspired by a remarkable number sequence. What’s the next number in the sequence 2, 23, 2357, ...? This is a rather good puzzle, because the answer (under suitable interpretation) is no less than the gigantic number

23571113171923293137414347535961677173798389971011031071091131271311371391491511

57163167173179181191193197199211223227229233239241251257263269271277281283293307

31131331733133734734935335936737337938338939740140941942143143343944344945746146

34674794874914995035095215235415475575635695715775875935996016076136176196316416

43647653659661673677683691701709719This is the sequence of

concatenate primes: primes formed by concatenating the firstnprimes. (The values ofnhere are 1, 2, 4, and 128.)It seems abundantly clear that this statement is true:

2357

is the only integer that's both a concatenate prime and a minimal k-primeval prime.For this to be true it is only necessary to prove another conjecture that also seems certainly true - that the minimal

k-primval prime always starts with 1 (fork> 1). Despite its obviousness, it is not clear how to prove this.