A076730 -id:A076730 - cp's OEIS frontend

A039999 Number of permutations of digits of n which yield distinct primes.

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

Offset: 1

David W. Wilson

Consider all k! permutations of digits of a k-digit number n, discard initial zeros, count distinct primes.

			a(20) = 1, since from {02, 20} we get {2,20} and only 2 is prime.
From 107 we get 4 primes: (0)17, (0)71, 107 and 701; so a(107) = 4.

T. D. Noe, Table of n, a(n) for n = 1..10000
C. Hilliard, PARI program.

Cf. A046810.
Cf. A039993 (number of primes embedded in n), A076730 (maximum for n digits), A072857 (record indices: primeval numbers), A134596 (largest with n digits).
Cf. A075053 (as A039993 but counted with multiplicity), A134597 (maximum for n digits).

import Data.List (permutations, nub)
a039999 n = length $ filter ((== 1) . a010051)
                   (map read (nub $ permutations $ show n) :: [Integer])
-- Reinhard Zumkeller, Feb 07 2011

[ #[ s: s in Seqset([ Seqint([m(p[i]):i in [1..#x] ], 10): p in Permutations(Seqset(x)) ]) | IsPrime(s) ] where m is map< x->y | [:i in [1..#x] ] > where x is [1..#y] where y is Intseq(n,10): n in [1..120] ]; // Klaus Brockhaus, Jun 15 2009

Table[Count[FromDigits/@Permutations[IntegerDigits[n]],?PrimeQ], {n,110}] (* _Harvey P. Dale, Jun 26 2011 *)

for(x=1, 400, print1(permprime(x), ",")) /* for definition of function permprime cf. link */ \\ Cino Hilliard, Jun 07 2009

A039999(n,D=vecsort(digits(n)),S)={forperm(D,p, isprime(fromdigits(Vec(p))) && S++);S} \\ Giving the 2nd arg avoids computing it and increases efficiency when the digits are already known. Must be sorted because forperm() only considers "larger" permutations. - M. F. Hasler, Oct 14 2019

from sympy import isprime
from itertools import permutations
def a(n): return len(set(t for p in permutations(str(n)) if isprime(t:=int("".join(p)))))
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Feb 17 2024

Contribution of Cino Hilliard edited by Klaus Brockhaus, Jun 15 2009

Edited by M. F. Hasler, Oct 14 2019

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

A076449 Least number whose digits can be used to form exactly n different primes (not necessarily using all digits).

Original entry on oeis.org

1, 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, 1237, 3479, 10699, 1367, 10179, 1379, 10127, 10079, 10138, 10123, 10234, 10235, 10247, 10339, 10267

Offset: 0

Lekraj Beedassy, Nov 07 2002

Smallest m such that A039993(m) = n. - M. F. Hasler, Mar 08 2014

Mike Keith conjectures that a(n) always exists and reports that he has checked this for n <= 66. - N. J. A. Sloane, Jan 25 2008

			a(10) = 179 because 179 is the least number harboring ten primes (namely 7, 17, 19, 71, 79, 97, 179, 197, 719, 971).

Michael S. Branicky, Table of n, a(n) for n = 0..2702 (terms 1..457 from Robert G. Wilson v)
Michael S. Branicky, Python program for A076449, A072857, A076730, A134596
C. K. Caldwell, The Prime Glossary, Primeval Number
J. P. Delahaye, Primes Hunters, 1379 is very primeval (in French)
Mike Keith, Integers containing many embedded primes
W. Schneider, Primeval Numbers
G. Villemin's Almanach of Numbers, Nombre Primeval de Mike Keith

Cf. A075053, A072857 gives a similar sequence, A134596.

(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) f[n_] := Length[ Select[ FromDigits /@ Flatten[ Permutations /@ Subsets[ IntegerDigits[ n]], 1], PrimeQ[ # ] &]]; t = Table[0, {50}]; Do[ a = f[n]; If[a < 50 && t[[a + 1]] == 0, t[[a + 1]] = n], {n, 12500}]; t (* Robert G. Wilson v, Feb 12 2005 *)

A076449(n)=for(m=1,oo,A039993(m)==n&&return(m)) \\ Not very efficient. - M. F. Hasler, Mar 08 2014

Python
```
# see linked program
```

a(n) = min { m | A039993(m)=n } = min A039993^{-1}(n). - M. F. Hasler, Mar 08 2014

Edited by Robert G. Wilson v, Nov 24 2002
Keith link repaired by Charles R Greathouse IV, Aug 13 2009
Definition reworded by M. F. Hasler, Mar 08 2014
a(26) corrected by Robert G. Wilson v, Mar 12 2014

A076497 Number of primes corresponding to n-th primeval number A072857(n).

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 14, 19, 21, 26, 29, 31, 33, 35, 41, 53, 55, 60, 64, 89, 96, 106, 122, 153, 188, 248, 311, 349, 402, 421, 547, 705, 812, 906, 1098, 1162, 1268, 1662, 1738, 1953, 2418, 2920, 3133, 3457, 4483, 4517, 4917, 5174, 5953, 6552, 6799, 8938, 10219

Offset: 1

Lekraj Beedassy, Nov 08 2002

			a(3) = 3 because the primeval number A072857(3) = 13 can be used to create 3 prime numbers, namely 3, 13 and 31.
a(6) = 7 because the primeval number A072857(7) = 113 can be used to create 7 prime numbers, namely 3, 11, 13, 31, 113, 131 and 311. (The two primes 13 and 31 can be obtained in 2 ways, therefore A075053(113) = 9.)

Giovanni Resta, Table of n, a(n) for n = 1..100
C. K. Caldwell, The Prime Glossary, Primeval Number
M. Keith, Integers containing many embedded primes
G. Villemin's Almanach of Numbers, Nombre Primeval de Mike Keith
Wikipedia, Primeval number.

Cf. A072857, A077623, A076730.

Needs["DiscreteMath`Combinatorica`"]; f[n_] := Block[{a = Drop[ Sort[ Subsets[ IntegerDigits[n]]], 1], b = c = {}, k = 1, l}, l = Length[a] + 1; While[k < l, b = Append[b, Permutations[ a[[k]] ]]; k++ ]; b = Union[ Flatten[b, 1]]; l = Length[b] + 1; k = 1; While[k < l, c = Append[c, FromDigits[ b[[k]] ]]; k++ ]; Count[ PrimeQ[ Union[c]], True]]; d = -1; Do[ b = f[n]; If[b > d, Print[b]; d = b], {n, 1, 10^6}]

a(n) = A039993(A072857(n)). - M. F. Hasler, Mar 12 2014

Edited and extended by Robert G. Wilson v, Nov 12 2002
Links fixed by Charles R Greathouse IV, Aug 13 2009
a(40)-a(54) from Giovanni Resta, Nov 06 2013

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

A134597 a(n) gives the maximal value of A075053(m) for any n-digit number m.

Original entry on oeis.org

1, 4, 11, 31, 106, 402, 1953

Offset: 1

N. J. A. Sloane, Jan 25 2008

In A075053(m), the primes obtained as permutations of digits of m are counted several times if they can be obtained in several different ways. See sequence A076730 which uses A039993 instead, i.e., counting only different primes. - M. F. Hasler, Mar 11 2014

The original data given for n = 3, 4, 5 was erroneously A007526(n). - Up to n = 6, a(n) = A076730(n), but the two will differ not later than for n = 10, where A134596(10) = 1123456789 gives a(10) >= 398100 = A075053(1123456789) > A039993(1123456789) = 362451 = A076730(10). The difference arises because each prime containing a single '1' will be counted twice by A075053, but only once by A039993. - M. F. Hasler, Oct 14 2019

			From _M. F. Hasler_, Oct 14 2019: (Start)
a(2) = 4 = A075053(37), because from 37 one can obtain the primes {3, 7, 37, 73}, and there is obviously no 2-digit number which could give more primes.
a(3) = 11 = A075053(137), because from 137 one can obtain the primes {3, 7, 13, 17, 31, 37, 71, 73, 137, 173, 317}, and no 3-digit number yields more.
a(4) = 31 = A075053(1379), because from 1379 one can obtain the 31 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}, and no 4-digit number yields more.
a(5) = 106 = A075053(13679). a(6) = 402 = A075053(123479).
a(7) = 1953 = A075053(1234679). (End)

M. Keith, Integers containing many embedded primes

Cf. A075053, A039993, A134596.

Cf. A239196 for record indices of A075053, A239197 for associated record values.

A134597(n)={my(m=0);forvec(D=vector(n,i,[0,9]), vecsum(D)%3||next;m=max(A075053(fromdigits(D),D),m),1);m} \\ M. F. Hasler, Oct 14 2019

a(n) <= A007526(n), with equality iff n <= 2. [Keith]

a(n) = max { A075053(m); 10^(n-1) <= m < 10^n } >= A076730(n) = max { A039993(m); 10^(n-1) <= m < 10^n }. - M. F. Hasler, Mar 11 2014

Link fixed by Charles R Greathouse IV, Aug 13 2009
Definition corrected by M. F. Hasler, Mar 11 2014
Data corrected and extended by M. F. Hasler, Oct 14 2019

cp's OEIS Frontend

A039999 Number of permutations of digits of n which yield distinct primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

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

A076449 Least number whose digits can be used to form exactly n different primes (not necessarily using all digits).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A076497 Number of primes corresponding to n-th primeval number A072857(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A134596 The largest n-digit primeval number A072857.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A134597 a(n) gives the maximal value of A075053(m) for any n-digit number m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions