%I #53 Apr 03 2023 10:36:09
%S 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,
%T 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,
%U 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
%N Number of different primes embedded in n.
%C a(n) counts (distinct) permuted subsequences of digits of n which denote primes.
%H T. D. Noe, <a href="/A039993/b039993.txt">Table of n, a(n) for n=1..10000</a>
%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=Primeval">Primeval Number</a>
%H J. P. Delahaye, Primes Hunters, <a href="http://web.archive.org/web/20020901024608/http://www.pour-la-science.com/numeros/pls-258/logique.htm">1379 is very primeval (in French)</a>
%H Mike Keith, <a href="http://www.cadaeic.net/primeval.htm">Integers containing many embedded primes</a>
%H W. Schneider, <a href="http://web.archive.org/web/2004/www.wschnei.de/digit-related-numbers/primeval-numbers.html">Primeval Numbers</a>
%H G. Villemin's Almanach of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Premier/primeval.htm#top">Mike Keith's Primeval Number</a> (in French).
%e 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).
%e 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 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}]
%t Table[Count[Union[FromDigits/@(Flatten[Permutations/@Subsets[ IntegerDigits[ n]],1])],_?PrimeQ],{n,110}] (* _Harvey P. Dale_, Nov 29 2017 *)
%o (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
%o (Python)
%o from itertools import permutations
%o from sympy import isprime
%o def a(n):
%o l=list(str(n))
%o L=[]
%o for i in range(len(l)):
%o L+=[int("".join(x)) for x in permutations(l, i + 1)]
%o return len([i for i in set(L) if isprime(i)])
%o print([a(n) for n in range(1, 101)]) # _Indranil Ghosh_, Jun 25 2017
%o (Python)
%o from sympy.utilities.iterables import multiset_permutations
%o from sympy import isprime
%o 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
%Y Different from A075053. For records see A072857, A076497. See also A134596, A134597.
%Y Cf. A039999.
%K nonn,base
%O 1,13
%A _David W. Wilson_
%E Edited by _Robert G. Wilson v_, Nov 25 2002
%E Keith link repaired by _Charles R Greathouse IV_, Aug 13 2009