A039997 Number of distinct primes which occur as substrings of the 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, 1, 1, 2, 0, 1

Offset: 1

Author

David W. Wilson

Keywords

• nonn
• base

Examples

			a(22) = 1 because 22 has two substrings which are prime but they are identical. a(103) = 2, since the primes 3 and 103 occur as substrings.
		

Links

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

Crossrefs

Different from A039995 after the 100th term. Cf. A035232.

Programs

Haskell

import Data.List (isInfixOf)
a039997 n = length [p | p <- takeWhile (<= n) a000040_list,
                        show p `isInfixOf` show n]
a039997_list = map a039997 [1..]
-- Reinhard Zumkeller, Jan 31 2012

Maple

a:= n-> (s-> nops(select(t -> t[1]<>"0" and isprime(parse(t)),
        {seq(seq(s[i..j], i=1..j), j=1..length(s))})))(""||n):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 09 2022

Mathematica

a[n_] := Block[{s = IntegerDigits[n], c = 0, d = {}}, l = Length[s]; t = Flatten[ Table[ Take[s, {i, j}], {i, 1, l}, {j, i, l}], 1]; k = l(l + 1)/2; While[k > 0, If[ t[[k]][[1]] != 0, d = Append[d, FromDigits[ t[[k]] ]]]; k-- ]; Count[ PrimeQ[ Union[d]], True]]; Table[ a[n], {n, 1, 105}]

PARI

dp(n)=if(n<12,return(if(isprime(n),[n],[])));my(v=vecsort(select(isprime, eval(Vec(Str(n)))),,8),t);while(n>9,if(gcd(n%10,10)>1,n\=10;next);t=10; while((t*=10)Charles R Greathouse IV, Jul 10 2012

Python

from sympy import isprime
def a(n):
    s = str(n)
    ss = (int(s[i:j]) for i in range(len(s)) for j in range(i+1, len(s)+1))
    return len(set(k for k in ss if isprime(k)))
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Aug 07 2022

Formula

a(A062115(n)) = 0; a(A093301(n)) = n and a(m) <> n for m < A093301(n). - Reinhard Zumkeller, Jul 16 2007

a(A163753(n)) > 0; a(A205667(n)) = 1. [Reinhard Zumkeller, Jan 31 2012]

Extensions

Edited by Robert G. Wilson v, Feb 24 2003