Primeval numbers (A072857) are defined by Mike Keith as integers which contain more primes formed using subsets of its digits than any smaller integer. The integer 107 for example contains the following 5 primes:
- 7, 17, 71, 107, 701.
Because no integer less than 107 contains 5 primes or more, 107 is a primeval number.
The number of primes "contained" in any number is A039993, which counts the distinct primes that can be obtained by permuting a subsequence of the number's digits. Thus,
- the primeval numbers A072857 = (2, 13, 37, 107, 113, 137, 1013, ...) are indices of records of A039993. The corresponding record values, i.e., number of primes in these numbers are listed in A076497. There are 22 primeval numbers less than 100 000.
- all numbers having the same multiset of digits have the same value for A039993, and the records are necessarily reached at numbers which have their digit sorted in nondecreasing order, except for the smallest nonzero digit which must precede the digits '0'. See sequence A328447 for this smallest representative of the "permutation class", in this sense, of a number.
A variant of A039993 is A075053 which counts the "contained primes" with multiplicity, when the same prime can be obtained using a different choice of [indices of] digits of n. The two functions coincide for arguments which don't have duplicate digits, otherwise A075053 is strictly larger. Record indices and values of A075053 are listed in A239196 and A239197.
Sequence A039999 counts the (distinct) primes obtained by permuting all digits of a number, allowing (but ignoring) leading zeros, i.e., A039999(130) = 2 counts 013 = 13 and 031 = 31. Therefore, if n has at most one digit 0, the value of A075053(n) equals the sum over the values A039999(k) for all k (possibly with multiplicity) whose nonzero digits are a subsequence of those of n and which contain the digit 0 if n has one, to avoid counting primes twice due to leading zeros. For example,
A075053(103) = A039999(103) + A039999(10) + A039999(30) = 3 + 0 + 1, and A075053(113) = A039999(113) + A039999(11) + A039999(13) + A039999(13) + A039999(1) + A039999(1) + A039999(3).
However, if there are multiple digits 0 in n, this will not count correctly the multiplicity of primes containing only some but not all of them. One has to take into account "by hand" the multiplicity of these. (For example, A075053(1003) = 6 = #[3, 13, 31, 103, 103, 3001], where 103 is counted twice according to which 0 is used to produce it. But A039999(1003) + A039999(100) + A039999(300) = 4 + 0 + 1 = 5.
Maxima for given size = length = number of digits
The maximum number of primes contained (in the sense of A039993) in an n-digit number is A076730 = (1, 4, 11, 31, 106, ...) These are the values of A039993 at the largest primeval numbers of given size, i.e., the largest one below a given power of ten, listed in A134596 = (2, 37, 137, 1379, 13679, 123479, 1234679, 12345679, 102345679, ...). The analog sequence for A075053 is A134597 (maxima for n-digit numbers; the indices appear to be the same so far). (... to be continued ...)
- Caldwell, Chris: primeval number, The Prime Glossary, http://www.utm.edu/research/primes/glossary/Primeval.html.
- Keith, Mike: Integers Containing Many Embedded Primes, http://users.aol.com/s6sj7gt/primeval.htm. - or rather http://www.cadaeic.net/primeval.htm ?
- Schneider, Walter: Primeval numbers, MATHEWS: the Archive of Recreational Mathematics
Cite this page as
M. F. Hasler, Primeval numbers. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki. (Available at https://oeis.org/wiki/Primeval_numbers)