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

Author

David W. Wilson

Keywords

• nonn
• base

Comments

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

Examples

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

Links

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

Crossrefs

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

Cf. A010051.

Programs

Haskell

import Data.List (subsequences, nub)
a039995 n = sum $
   map a010051 $ nub $ map read (tail $ subsequences $ show n)
-- Reinhard Zumkeller, Jan 31 2012

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

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

Formula

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