A039995 Number of distinct primes which occur as subsequences of the sequence of digits of n.

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

Offset

1,13

Comments

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Formula

a(A094535(n)) = n and a(m) < n for m < A094535(n); A039995(39467139) = 100, cf. A205956. - Reinhard Zumkeller, Feb 01 2012

Example

a(103) = 3; the 3 primes are 3, 13 and 103.

Mathematica

cnt[n_] := Module[{d = IntegerDigits[n]}, Length[Union[Select[FromDigits /@ Subsets[d], PrimeQ]]]]; Table[cnt[n], {n, 105}] (* T. D. Noe, Jan 31 2012 *)

Prog

(Haskell)
import Data.List (subsequences, nub)
a039995 n = sum $
   map a010051 $ nub $ map read (tail $ subsequences $ show n)
-- Reinhard Zumkeller, Jan 31 2012
(Python)
from sympy import isprime
from itertools import chain, combinations as combs
def powerset(s): # nonempty subsets of s
    return chain.from_iterable(combs(s, r) for r in range(1, len(s)+1))
def a(n):
    ss = set(int("".join(s)) for s in powerset(str(n)))
    return sum(1 for k in ss if isprime(k))
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Aug 07 2022

Crossrefs

A039997 counts only the primes which occur as substrings, i.e. contiguous subsequences. Cf. A035232.

Cf. A010051.

Sequence in context: A193403 A354272 A039997 * A035232 A359269 A091603

Adjacent sequences: A039992 A039993 A039994 * A039996 A039997 A039998

Keyword

nonn,base

Author

David W. Wilson

Status

approved