 |
Primeval Numbers
Integers containing many
embedded primes |
Introduction
A 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 Numbers
We 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 Contained |
2 |
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 for the 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 begins
2, 37, 137, 1379, 13679, ...
while the maximum number of primes contained in an N-digit integer is
1, 4, 11, 31, 106, ...
Note that the theoretical maximum possible number of primes contained in an N-digit integer is the sum for k = 1 to N of P(N,k), the number of permutations of N things taken k at a time, corresponding to the case when every permutation of every substring of the integer is a prime. This sequence is
1, 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 a and b) then the two-digit pair ab would be divisible by 3, and hence not all substrings would be prime. Suppose the digit a = 0 mod 3, and consider three other digits b,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, then a+b+c = 6 = 0 mod 3, so abc is composite. If a = 1 mod 3, then a+b = 3 = 0 mod 3, so ab is 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 exactly k primes, for each k ³ 1. Here are the first 30 values of this function (for k = 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 k so far (we have checked up to k=66) we have found at least one integer that contains that many primes, which leads to the following:
Conjecture: There is an integer containing exactly k primes for every value of k.
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 Numbers
As we proceed through the primeval numbers, finding integers that contain more and more primes, we expect that eventually we will find an integer containing all the 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 all k-digit primes. We call such an integer a k-primeval number, and if it is itself prime we call it a k-primeval prime. One basic question is: what’s the smallest k-primeval number and k-primeval prime, for each k?
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 any k-digit prime with those digits. For each digit d, the number of d’s we need is the largest number of d’s that occurs in any k-digit prime. Here is a table of the number of each digit required for the first few values of k:
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 5
from which the sequence of minimal k-primeval numbers follows:
2357, 1123456789, 1012233445566778899, 10011222333444555666777888999, ...
Much more interesting are the minimal k-primeval primes. Determining these requires finding the permutation of the corresponding minimal k-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 minimal k-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 the k-primeval number, and then finding a prime permutation. The first four minimal k-primeval primes (for k = 1,2,3,4), which I computed in July 1998, are:
2357
1123465789
10112233445566788997
100111222333444555666777998889
Since 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 to n=31. Here they are, in the compact notation:
k Minimal k-primeval prime 5 (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 99999889999999999999999999999999
Note that k=1 is the only value of k so far where the minimal k-primeval integer (2357) is the same as the minimal k-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
43647653659661673677683691701709719
This is the sequence of concatenate primes: primes formed by concatenating the first n primes. (The values of n here 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 (for k > 1). Despite its obviousness, it is not clear how to prove this.