A076449 -id:A076449 - cp's OEIS frontend

A072857 Primeval numbers: numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits.

1, 2, 13, 37, 107, 113, 137, 1013, 1037, 1079, 1237, 1367, 1379, 10079, 10123, 10136, 10139, 10237, 10279, 10367, 10379, 12379, 13679, 100279, 100379, 101237, 102347, 102379, 103679, 123479, 1001237, 1002347, 1002379, 1003679, 1012349, 1012379, 1023457, 1023467, 1023479, 1234579, 1234679, 10012349

Offset: 1

Lekraj Beedassy, Jul 26 2002

RECORDS transform of A039993. - N. J. A. Sloane, Jan 25 2008. See A239196 and A239197 for the RECORDS transform of the closely related sequence A075053. - M. F. Hasler, Mar 12 2014
"73 is the largest integer with the property that all permutations of all of its substrings are primes." - M. Keith
Smallest monotonic increasing subsequence of A076449. - Lekraj Beedassy, Sep 23 2006
From M. F. Hasler, Oct 15 2019: (Start)
All terms > 37 start with leading digit 1 and have all other digits in nondecreasing order. The terms are smallest representatives of the class of numbers having the same digits, cf. A179239 and A328447 which both contain this as a subsequence.
The frequency of primes is roughly 50% for the displayed values, but appears to decrease. Can it be proved that the asymptotic density is zero?
Can we prove that there are infinitely many even terms? (Of the form 10...01..12345678?)
Can it be proved that there is no term that is a multiple of 3? (Or the contrary? Are there infinitely many?) (End)

			1379 is in the sequence because it is the smallest number whose digital permutations form a total of 31 primes, viz. 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.

J.-P. Delahaye, Merveilleux nombres premiers ("Amazing primes"), "1379's quite primeval, is it not?", pp. 318-321, Pour la Science, Paris 2000.

Giovanni Resta, Table of n, a(n) for n = 1..100
C. K. Caldwell, The Prime Glossary, primeval number
J. P. Delahaye, Primes Hunters, 1379 is very primeval (in French)
M. Keith, Integers containing many embedded primes
W. Schneider, Primeval Numbers
N. J. A. Sloane, Transforms
G. Villemin's Almanach of Numbers, Nombre Primeval de Mike Keith
Wikipedia, Primeval number

Cf. A039993, A075053, A076497, A239196, A239197.
A076449 gives a similar sequence.
Cf. A119535 (prime subsequence).

(*first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) f[n_] := Length[ Select[ FromDigits /@ Flatten[ Permutations /@ Subsets[ IntegerDigits[ n]], 1], PrimeQ[ # ] &]]; d = -1; Do[ b = f[n]; If[b > d, Print[n]; d = b], {n, 2^20}] (* Robert G. Wilson v, Feb 12 2005 *)
Join[{1},DeleteDuplicates[Table[{n,Count[Union[FromDigits/@Flatten[Permutations[#]&/@Subsets[IntegerDigits[n]],1]],?PrimeQ]},{n,2,125000}],GreaterEqual[#1[[2]],#2[[2]]]&][[;;,1]]] (* The program generates the first 30 terms of the sequence. *) (* _Harvey P. Dale, Nov 16 2024 *)

A072857_upto(num_digits,s=1,m=-1,L=List())={for(n=s,num_digits, my(u=10^(n-1)); forvec(v=vector(n-(n>2),i,[0,if(n>6,9*(i+1)\n,n>3,10-(n-i)\.6,7)]), m<A039993(u+fromdigits(v)) && m=A039993(listput(L,u+fromdigits(v))),1)); Vec(L)} \\ Optional 2nd and 3rd arg allow to extend a previous computation. - M. F. Hasler, Oct 15 2019

Python
```
# see linked program in A076449
```

Edited, corrected and extended by Robert G. Wilson v, Nov 12 2002

Comment corrected by N. J. A. Sloane, Jan 25 2008

A075053 Number of primes (counted with repetition) that can be formed by rearranging some or all of the digits of n.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 3, 1, 1, 1, 3, 0, 1, 1, 1, 2, 3, 1, 2, 1, 2, 1, 2, 1, 3, 3, 2, 2, 3, 1, 4, 2, 1, 0, 1, 1, 2, 0, 1, 0, 2, 0, 0, 1, 1, 2, 3, 1, 2, 1, 2, 1, 2, 0, 1, 1, 1, 0, 1, 0, 2, 0, 0, 1, 3, 2, 4, 2, 2, 2, 2, 1, 3, 0, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 2, 0, 3, 1, 0, 0, 2, 1, 4, 2

Offset: 0

N. J. A. Sloane, Oct 12 2002

"Counted with repetition" means that if the same prime can be obtained using different digits, then it is counted several times (e.g., 13 obtained from 113 using the 1st and 3rd digit or the 2nd and 3rd digit), but not so if it is obtained as different permutations of the same digits (e.g., a(11) = 1 because the identical permutation and the transposition (2,1) of the digits [1,1] both yield 11, but this does not count twice since the same digits are used). - M. F. Hasler, Mar 12 2014

See A039993 for the variant which counts only distinct primes, e.g., A039993(22) = 1, A039993(113) = 7. See A039999 for the variant which requires all digits to be used. - M. F. Hasler, Oct 14 2019

			From 13 we can obtain 3, 13 and 31 so a(13) = 3. In the same way, a(17) = 3.
From 22 we obtain 2 in two ways, so a(22) = 2.
a(101) = 2 because from the digits of 101 one can form the primes 11 (using digits 1 & 3) and 101 (using all digits). The prime 11 = 011 formed using all 3 digits does not count separately because it has a leading zero.
a(111) = 3 because one can form the prime 11 using digits 1 & 2, 1 & 3 or 2 & 3.

T. D. Noe, Table of n, a(n) for n = 0..10000
M. F. Hasler, Primeval numbers, OEIS wiki, 2014, updated 2019.

Different from A039993 (counts only distinct primes). Cf. A072857, A076449.
Cf. A039999 (use all digits, count only distinct primes, allow leading zeros), A046810 (similar but don't allow leading zeros).
Cf. A134597 (maximum over all n-digit numbers), A076730 (maximum of A039993 for all n-digit numbers).
Cf. A239196 and A239197 for record indices and values.

f[n_] := Length@ Select[ Union[ FromDigits@# & /@ Flatten[ Subsets@# & /@ Permutations@ IntegerDigits@ n, 1]], PrimeQ@# &]; Array[f, 105, 0] (* Robert G. Wilson v, Mar 12 2014 *)

A075053(n,D=vecsort(digits(n)),S=0)=for(b=1,2^#D-1,forperm(vecextract(D,b),p,p[1]&&isprime(fromdigits(Vec(p)))&&S++));S \\ Second optional arg allows to give the digits if they are already known. - M. F. Hasler, Oct 14 2019, replacing earlier code from 2014.

from itertools import combinations
from sympy.utilities.iterables import multiset_permutations
from sympy import isprime
def A075053(n): return sum(1 for l in range(1,len(str(n))+1) for a in combinations(str(n),r=l) for b in multiset_permutations(a) if b[0] !='0' and isprime(int(''.join(b)))) # Chai Wah Wu, Sep 13 2022

a(n) >= A039993(n) with equality iff n has no duplicate digit. - M. F. Hasler, Oct 14 2019

a(n) = Sum_{k in S(n)} A039999(k), if n has not more than one digit 0, where S(n) are the numbers whose nonzero digits are a subsequence of those of n, and which contain the digit 0 if n does, taken with multiplicity (for numbers using some but not all digits that are repeated in n). - M. F. Hasler, Oct 15 2019

Corrected and extended by John W. Layman, Oct 15 2002

Examples & crossrefs edited by M. F. Hasler, Oct 14 2019

A134596 The largest n-digit primeval number A072857.

Original entry on oeis.org

2, 37, 137, 1379, 13679, 123479, 1234679, 12345679, 102345679, 1123456789, 10123456789

Offset: 1

N. J. A. Sloane, Jan 25 2008

Former definition: The least n-digit number m (i.e., m >= 10^(n-1)) which yields A076730(n) = the maximum, for m < 10^n, of A039993(m) = number of primes that can be formed using some or all digits of m.

Subsequence of A072857 consisting of the largest terms of given length. - M. F. Hasler, Mar 12 2014

M. Keith, Integers containing many embedded primes

Cf. A039993, A072857, A076730, A134597, A076449.

A134596(n,A=A072857)=vecmax(select(t->logint(t,10)+1==n,A)) \\ where A072857 must comprise all n digit terms of that sequence. - M. F. Hasler, Oct 14 2019

Python
```
# see linked program in A076449
```

a(n) = max { m in A072857, m < 10^n }. - M. F. Hasler, Mar 12 2014

Link fixed by Charles R Greathouse IV, Aug 13 2009

Definition reworded and values of a(6)-a(11) added by M. F. Hasler, Mar 11 2014

A076730 Maximum number of (distinct) primes that an n-digit number may shelter (i.e., primes contained among all digital substrings' permutations).

Original entry on oeis.org

1, 4, 11, 31, 106, 402, 1953, 10542, 64905, 362451, 2970505

Offset: 1

Lekraj Beedassy, Nov 08 2002

See sequence A134596 for the least numbers of given length which yields these maxima over n-digit indices for A039993. - M. F. Hasler, Mar 11 2014

By definition this is a subsequence of A076497. The term a(10) was incorrectly given as 398100 = A075053(1123456789), which double-counts each prime using only one digit '1'. But a(10) = A039993(1123456789) = A076497(80) = 362451. The values given for a(9) and a(11) were also incorrect, the latter probably for the same reason, and for a(9) probably due to double-counting of primes with leading zeros. - M. F. Hasler and David A. Corneth, Oct 15 2019

			We have a(3)=11, since among numbers 100 through 999, the smallest ones having 5, 6, 7, 8, 10, 11 embedded primes are respectively 107, 127, 113, 167, 179, 137 (the last of these being the first reaching the maximum number of 11 embedded primes, viz. 3, 7, 13, 17, 31, 37, 71, 73, 137, 173, 317).

M. Keith, Integers containing many embedded primes
W. Schneider, MATHEWS, Primeval Numbers

Cf. A072857, A076449, A076497, A134596 (largest n-digit primeval number).

Cf. A075053 (a variant of A039993), A134597 (= max A075053(1..10^n-1)).

a(n,m=0)=for(k=10^(n-1),10^n-1,A039993(k)>m&&m=A039993(k));m \\ M. F. Hasler, Mar 09 2014

Python
```
# see linked program in A076449
```

a(n) = A039993(A134596(n)) = max { A039993(m); m in A072857 and m < 10^n }. - M. F. Hasler, Mar 12 2014

a(n) = A076497(k) for k such that A072857(k) = A134596(n). - M. F. Hasler, Oct 15 2019

Link fixed by Charles R Greathouse IV, Aug 13 2009
a(6) from M. F. Hasler, Mar 09 2014
a(7)-a(11) from Robert G. Wilson v, Mar 11 2014
a(9)-a(11) corrected by M. F. Hasler, Oct 15 2019

A307624 Least number whose digits can be used to form exactly n distinct composite numbers (not necessarily using all digits).

Original entry on oeis.org

1, 4, 12, 18, 46, 103, 122, 104, 102, 108, 124, 128, 126, 148, 246, 468, 1002, 1008, 1137, 1077, 1014, 1055, 1044, 1022, 1124, 1126, 1079, 1145, 1037, 1224, 1266, 1448, 1379, 1039, 1367, 1036, 1057, 1034, 1027, 1047, 1024, 1023, 1025, 1029, 1026, 1068, 1247, 1235, 3579, 1234, 1257, 1289, 1239, 1236, 1278, 1245

Offset: 0

Daniel Lignon, Apr 19 2019

a(n) always exists because with 10^n, you can form exactly n composite numbers... but, in general, it's not the least.

			The digits of 103 can be used to form the numbers 1, 3, 10, 13, 30, 31, 103, 130, 301, and 310. Of these, exactly 5 are composite (10, 30, 130, 301 = 7*43, and 310). Since 103 is the smallest such number, a(5) = 103.

Cf. A002808 (composite numbers).

Cf. A076449 (the same with primes instead of composite numbers) and A307623 (the sequence of corresponding records).

f[n_] := Length[Union[ Select[FromDigits /@ Flatten[Permutations /@ Subsets[IntegerDigits[n]],  1], CompositeQ]]];
t = Table[0, {100}]; Do[ a = f[n]; If[a < 100 && t[[a + 1]] == 0, t[[a + 1]] = n], {n, 100000}]; t

A370322 Least prime p such that exactly n distinct primes can be formed using one or more of the digits of p.

Original entry on oeis.org

2, 29, 13, 37, 107, 127, 113, 167, 1033, 179, 137, 1063, 1217, 1013, 1399, 1249, 1163, 1123, 1307, 1193, 1097, 10477, 11351, 1439, 1279, 1237, 3947, 11353, 1367, 10343, 1973, 10271, 10079, 10831, 10321, 10243, 10253, 10247, 13093, 10267, 10163, 10429, 12487, 11437, 10357, 10337

Offset: 1

Robert G. Wilson v, Mar 22 2024

Inspired by A076449.
a(n) >= A076449(n). As an example, a(727) is 3569887, but A076449(727) is 3567889, a difference of 1998. Notice that they possess identical digits.
a(n) = A076449(n) at n = 1, 3, 4, 5, 6, 7, 8, 10, 11, 14, 18, 19, 25, 26, 29, 33, 38, 40, 45, 46, ..., .
a(n) <> A076449(n) but they have identical digits at n = 12, 13, 17, 19, 20, 21, 24, 27, 31, 32, 34, 35, 36, 37, 39, ..., .
a(n) <> A076449(n) and they do not have identical digits at n = 2, 9, 15, 16, 22, 23, 28, 30, ..., .

			a(0) would be 1, but 1 is not a prime (A075053);
a(1) is 2, the first prime;
a(2) is 29 since {2 & 29} are primes but {9 & 92} are not;
a(3) is 13 since {3, 13 & 31} are primes, but 1 is not;
a(4) is 37 since all the permutations are prime, i.e.: {3, 7, 37 & 73};
a(5) is 107 since {7, 17, 71, 107 & 701} are primes; etc.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1755 terms from Robert G. Wilson v)

Cf. A072857, A075053, A076449.

f = Compile[{{n, Integer}}, Floor@ Length[ Select[ Union[ FromDigits /@ Flatten[ Permutations /@ Subsets[ IntegerDigits@n], 1]], PrimeQ@# &]]]; p = 2; t[] := 0; While[p < 114500, a = f@p; If[ t[a] == 0, t[a] = p]; p = NextPrime@ p]; t /@ Range@ 100

A173052 Partial sums of A072857.

Original entry on oeis.org

1, 3, 16, 53, 160, 273, 410, 1423, 2460, 3539, 4776, 6143, 7522, 17601, 27724, 37860, 47999, 58236, 68515, 78882, 89261, 101640, 115319, 215598, 315977, 417214, 519561, 621940, 725619, 849098, 1850335, 2852682, 3855061, 4858740, 5871089

Offset: 1

Jonathan Vos Post, Feb 08 2010

Partial sums of primeval numbers. Primeval number: a prime which "contains" more primes in it than any preceding number. Here "contains" means may be constructed from a subset of its digits. E.g., 1379 contains 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 and 9371. The subsequence of prime partial sums of primeval numbers begins: 3, 53, 1423, 3539, 6143, 89261, 115319, 315977. What is the smallest primeval prime partial sums of primeval numbers, i.e. the intersection of this sequence with A119535?

			a(36) = 1 + 2 + 13 + 37 + 107 + 113 + 137 + 1013 + 1037 + 1079 + 1237 + 1367 + 1379 + 10079 + 10123 + 10136 + 10139 + 10237 + 10279 + 10367 + 10379 + 12379 + 13679 + 100279 + 100379 + 101237 + 102347 + 102379 + 103679 + 123479 + 1001237 + 1002347 + 1002379 + 1003679 + 1012349 + 1012379.

Chris K. Caldwell AND G. L. Honaker, Jr., A BRIEF PRIME CURIOS! GLOSSARY.

Cf. A000040, A072857, A039993, A075053, A076497, A076449, A119535 (prime subsequence).

a(n) = SUM[i=1..n] A072857(i) = SUM[i=1..n] {numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits}.

cp's OEIS Frontend

A072857 Primeval numbers: numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A075053 Number of primes (counted with repetition) that can be formed by rearranging some or all of the digits of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A134596 The largest n-digit primeval number A072857.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A076730 Maximum number of (distinct) primes that an n-digit number may shelter (i.e., primes contained among all digital substrings' permutations).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A307624 Least number whose digits can be used to form exactly n distinct composite numbers (not necessarily using all digits).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A370322 Least prime p such that exactly n distinct primes can be formed using one or more of the digits of p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A173052 Partial sums of A072857.

Views

Author

Keywords

Comments

Examples

Links