A134596 -id:A134596 - cp's OEIS frontend

A039993 Number of different primes embedded in n.

0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 3, 1, 1, 1, 3, 0, 1, 1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 3, 1, 2, 3, 1, 4, 2, 1, 0, 1, 1, 2, 0, 1, 0, 2, 0, 0, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 0, 1, 1, 1, 0, 1, 0, 2, 0, 0, 1, 3, 2, 4, 2, 2, 2, 1, 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, 1

Offset: 1

David W. Wilson

a(n) counts (distinct) permuted subsequences of digits of n which denote primes.

			a(17) = 3 since we can obtain 7, 17 and 71. a(22) = 1, since we can get only one prime (in contrast, A075053(22) = 2).
a(1013) = 14 because the prime subsets derived from the digital permutations of 1013 are {3, 11, 13, 31, 101, 103, 113, 131, 311, 1013, 1031, 1103, 1301, 3011}.

T. D. Noe, Table of n, a(n) for n=1..10000
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, Mike Keith's Primeval Number (in French).

Different from A075053. For records see A072857, A076497. See also A134596, A134597.

Cf. A039999.

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]]; Table[ f[n], {n, 1, 105}]
Table[Count[Union[FromDigits/@(Flatten[Permutations/@Subsets[ IntegerDigits[ n]],1])],?PrimeQ],{n,110}] (* _Harvey P. Dale, Nov 29 2017 *)

A039993(n)={my(S=[],D=vecsort(digits(n))); for(i=1,2^#D-1, forperm(vecextract(D,i),p, isprime(fromdigits(Vec(p)))||next; S=setunion(S,[fromdigits(Vec(p))]))); #S} \\ To avoid duplicate scan of identical subsets of digits, one could skip the corresponding range of indices i when a binary pattern ...10... is detected. - M. F. Hasler, Mar 08 2014, simplified Oct 15 2019

from itertools import permutations
from sympy import isprime
def a(n):
    l=list(str(n))
    L=[]
    for i in range(len(l)):
        L+=[int("".join(x)) for x in permutations(l, i + 1)]
    return len([i for i in set(L) if isprime(i)])
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 25 2017

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

Edited by Robert G. Wilson v, Nov 25 2002

Keith link repaired by Charles R Greathouse IV, Aug 13 2009

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

Original entry on oeis.org

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

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

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

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

A373179 a(n) is the smallest n-digit integer whose digit permutations make the maximum possible number of n-digit primes.

Original entry on oeis.org

2, 13, 149, 1237, 13789, 123479, 1235789, 12345679, 102345679, 1123456789, 10123456789, 1011233456789, 1012334567789, 10123345677899

Offset: 1

Gonzalo Martínez, May 26 2024

A065851(n) is the maximum number of n-digit primes which can be made by permuting n digits.
a(n) = k is the smallest n-digit k for which A046810(k) = A065851(n).
a(n) has its relevant digits sorted and not beginning with 0 and may or may not be one of the primes (it is for n = 1 to 7, but not at n = 8).

			For n=3, A065851(3) = 4 primes are reached by permuting the digits of a(3) = 149, namely {149, 419, 491, 941}. (4 primes are also reached from 179 and 379, but they're bigger numbers.)

Kevin Ryde, C Code

Cf. A000040, A046810, A065851, A134596, A179239.

C
```
/* See links. */
```

from sympy import nextprime
from collections import Counter
def smallest(t):
    nz = "".join(sorted(c for c in t if c != "0"))
    s = "".join(t) if "0" not in t else nz[0]+"0"*t.count("0")+nz[1:]
    return int(s)
def a(n):
    c, p = Counter(), nextprime(10**(n-1))
    while p < 10**n:
        c["".join(sorted(str(p)))] += 1
        p = nextprime(p)
    m = min(c.most_common(1), key=lambda x:smallest(x[0]))
    return smallest(m[0])  # m[1] generates A065851
print([a(n) for n in range(1, 8)]) # Michael S. Branicky, May 28 2024

a(9)-a(11) from Michael S. Branicky, May 27 2024

a(12)-a(14) from Kevin Ryde, Jul 16 2024

cp's OEIS Frontend

A039993 Number of different primes embedded in n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Extensions

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

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

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

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

A373179 a(n) is the smallest n-digit integer whose digit permutations make the maximum possible number of n-digit primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C