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

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

Author

N. J. A. Sloane, Oct 12 2002

Keywords

• nonn
• base
• easy

Comments

"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

Examples

			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.
		

Links

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

Crossrefs

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.

Programs

Mathematica

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

PARI

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.

Python

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

Formula

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

Extensions

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

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