A035232 Number of substrings of n which are primes (counted with multiplicity).

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

Comments

No leading 0's allowed in substrings.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Formula

Trivial upper bound: a(n) <= binomial(floor(log(n)/log(10)+2), 2) ~ k*log^2 n with k = 0.09430584850580... = 1/log(10)^2/2. - Charles R Greathouse IV, Nov 15 2022

Example

The primes occurring as substrings of 37 are 3, 7, 37, so a(37) = 3.
a(22) = 2, since the prime 2 occurs twice as a substring.

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 07 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[d], True]]; Table[ a[n], {n, 1, 105}]

Prog

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

Crossrefs

Cf. A039997, A039995.

Sequence in context: A354272 A039997 A039995 * A359269 A091603 A370884

Adjacent sequences: A035229 A035230 A035231 * A035233 A035234 A035235

Keyword

base,easy,nonn

Author

Erich Friedman

Extensions

Edited by Robert G. Wilson v, Feb 24 2003

Status

approved