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

Author

David W. Wilson

Keywords

• nonn
• base

Comments

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

Examples

			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}.
		

Links

• 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).

Crossrefs

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

Cf. A039999.

Programs

Mathematica

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 *)

PARI

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

Python

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

Python

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

Extensions

Edited by Robert G. Wilson v, Nov 25 2002

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