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

%I #25 Aug 08 2022 08:24:04

%S 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,

%T 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,

%U 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

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

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

%H Reinhard Zumkeller, <a href="/A039995/b039995.txt">Table of n, a(n) for n = 1..10000</a>

%F a(A094535(n)) = n and a(m) < n for m < A094535(n); A039995(39467139) = 100, cf. A205956. - _Reinhard Zumkeller_, Feb 01 2012

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

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

%o (Haskell)

%o import Data.List (subsequences, nub)

%o a039995 n = sum $

%o map a010051 $ nub $ map read (tail $ subsequences $ show n)

%o -- _Reinhard Zumkeller_, Jan 31 2012

%o (Python)

%o from sympy import isprime

%o from itertools import chain, combinations as combs

%o def powerset(s): # nonempty subsets of s

%o return chain.from_iterable(combs(s, r) for r in range(1, len(s)+1))

%o def a(n):

%o ss = set(int("".join(s)) for s in powerset(str(n)))

%o return sum(1 for k in ss if isprime(k))

%o print([a(n) for n in range(1, 106)]) # _Michael S. Branicky_, Aug 07 2022

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

%Y Cf. A010051.

%K nonn,base

%O 1,13

%A _David W. Wilson_