login
A075053
Number of primes (counted with repetition) that can be formed by rearranging some or all of the digits of n.
14
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,14
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
LINKS
M. F. Hasler, Primeval numbers, OEIS wiki, 2014, updated 2019.
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
EXAMPLE
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.
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 *)
PROG
(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
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.
Sequence in context: A332488 A068153 A039993 * A328516 A328517 A007362
KEYWORD
nonn,base,easy
AUTHOR
N. J. A. Sloane, Oct 12 2002
EXTENSIONS
Corrected and extended by John W. Layman, Oct 15 2002
Examples & crossrefs edited by M. F. Hasler, Oct 14 2019
STATUS
approved