A039997 -id:A039997 - cp's OEIS frontend

A039996 Number of distinct primes embedded in prime(n) as substrings.

1, 1, 1, 1, 1, 2, 2, 1, 3, 2, 2, 3, 1, 2, 2, 3, 2, 1, 2, 2, 3, 2, 2, 1, 2, 1, 2, 2, 1, 4, 3, 4, 5, 3, 1, 2, 3, 2, 3, 5, 4, 1, 2, 3, 4, 2, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 2, 4, 3, 2, 4, 4, 3, 4, 4, 5, 3, 4, 4, 2, 4, 4, 4, 5, 5, 3, 3, 4, 1, 1, 3, 2, 4, 3, 3, 3, 1, 3, 2, 2, 3, 4, 2, 1, 1, 3, 2, 3, 5, 3, 4, 3, 3, 2, 4

Offset: 1

David W. Wilson

			a(26) = 1 since the only prime substring of "101" is 101.
a(48) = 4 since the only distinct prime substrings of "223" are 2, 3, 23, 223. - _David A. Corneth_, Jul 06 2020

David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A039994, A079066, A178597.

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))})))(""||(ithprime(n))):
seq(a(n), n=1..105);  # Alois P. Heinz, Jul 29 2025

f[n_] := Block[{id = IntegerDigits@ Prime@n, len = Floor[ Log[10, Prime@n] + 1]}, Count[ PrimeQ@ Union[ FromDigits@# & /@ Flatten[ Table[ Partition[id, k, 1], {k, len}], 1]], True]]; Array[f, 105] (* Robert G. Wilson v, Jun 28 2010 *)

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, Apr 22 2015

a(n) = A039997(prime(n)).
a(n) <= A039994(n). - Charles R Greathouse IV, Apr 22 2015
a(n) = A079066(n) + 1. - Alois P. Heinz, Jul 29 2025

Name corrected by David A. Corneth, Jul 06 2020

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

Original entry on oeis.org

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

Erich Friedman

No leading 0's allowed in substrings.

			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.

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

Cf. A039997, A039995.

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

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}]

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

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

Edited by Robert G. Wilson v, Feb 24 2003

A079066 "Memory" of prime(n): the number of distinct (previous) primes contained as substrings in prime(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 0, 2, 1, 1, 2, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 3, 4, 2, 0, 1, 2, 1, 2, 4, 3, 0, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 1, 3, 2, 1, 3, 3, 2, 3, 3, 4, 2, 3, 3, 1, 3, 3, 3, 4, 4, 2, 2, 3, 0, 0, 2, 1, 3, 2, 2, 2, 0, 2, 1, 1, 2, 3, 1, 0, 0, 2, 1, 2, 4, 2, 3, 2, 2, 1, 3

Offset: 1

Joseph L. Pe, Feb 02 2003

			The primes contained as substrings in prime(3) = 113 are 3, 11, 13. Hence a(30) = 3. 113 is the smallest prime with memory = 3.

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

Cf. A079075, A035232, A039996, A039997.

Cf. A033274, A179909, A179910, A179911, A179912, A179913, A179914, A179915, A179916, A179917, A179918, A179919, A179922.

import Data.List (isInfixOf)
a079066 n =
   length $ filter (`isInfixOf` (primesDec !! n)) $ take n primesDec
primesDec = "_" : map show a000040_list
-- Reinhard Zumkeller, Jul 19 2011

a:= n-> (s-> -1+nops(select(t -> t[1]<>"0" and isprime(parse(t)),
        {seq(seq(s[i..j], i=1..j), j=1..length(s))})))(""||(ithprime(n))):
seq(a(n), n=1..105);  # Alois P. Heinz, Jul 29 2025

ub = 105; tprime = Table[ToString[Prime[i]], {i, 1, ub}]; a = {}; For[i = 1, i <= ub, i++, m = 0; For[j = 1, j < i, j++, If[Length[StringPosition[tprime[[i]], tprime[[j]]]] > 0, m = m + 1]]; a = Append[a, m]]; a

a(n) = A039997(prime(n)) - 1.

a(n) = A039996(n) - 1. - Alois P. Heinz, Jul 29 2025

Edited by Robert G. Wilson v, Feb 25 2003

Name clarified by Sean A. Irvine, Jul 29 2025

A062115 Numbers with no prime substring in their decimal expansion.

Original entry on oeis.org

0, 1, 4, 6, 8, 9, 10, 14, 16, 18, 40, 44, 46, 48, 49, 60, 64, 66, 68, 69, 80, 81, 84, 86, 88, 90, 91, 94, 96, 98, 99, 100, 104, 106, 108, 140, 144, 146, 148, 160, 164, 166, 168, 169, 180, 184, 186, 188, 400, 404, 406, 408, 440, 444, 446, 448, 460, 464, 466

Offset: 1

Erich Friedman, Jun 28 2001

This is a 10-automatic sequence, a consequence of the finitude of A071062. - Charles R Greathouse IV, Sep 27 2011

Subsequence of A202259 (right-truncatable nonprimes). Supersequence of A202262 (composite numbers in which all substrings are composite), A202265 (nonprime numbers in which all substrings and reversal substrings are nonprimes). - Jaroslav Krizek, Jan 28 2012

			25 is not included because 5 is prime.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jeffrey Shallit, Minimal primes, Journal of Recreational Mathematics 30:2 (1999-2000), pp. 113-117.
Index entries for 10-automatic sequences.

Subsequence of A084984. [Arkadiusz Wesolowski, Jul 05 2011]
Cf. A071062.
Cf. A163753 (complement).

a062115 n = a062115_list !! (n-1)
a062115_list = filter ((== 0) . a039997) a084984_list
-- Reinhard Zumkeller, Jan 31 2012

from sympy import isprime
def ok(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 not any(isprime(k) for k in ss)
print([k for k in range(500) if ok(k)]) # Michael S. Branicky, May 02 2023

# faster for initial segment of sequence; uses ok, import above
from itertools import chain, count, islice, product
def agen(): # generator of terms
    yield from chain((0,), (int(t) for t in (f+"".join(r) for d in count(1) for f in "14689" for r in product("014689", repeat=d-1)) if ok(t)))
print(list(islice(agen(), 100))) # Michael S. Branicky, May 02 2023

A039997(a(n)) = 0. - Reinhard Zumkeller, Jul 16 2007
From Charles R Greathouse IV, Mar 23 2010: (Start)
a(n) = O(n^(log_4 10)) = O(n^1.661) because numbers containing only 0,4,6,8 are in this sequence.
a(n) = Omega(n^(log_13637 1000000)) = Omega(n^1.451) for similar reasons; this bound can be increased by considering longer sequences of digits. (End)

Offset corrected by Arkadiusz Wesolowski, Jul 27 2011

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

Original entry on oeis.org

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

David W. Wilson

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

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

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

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

Cf. A010051.

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

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

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

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

A093301 Earliest positive integer having embedded exactly k distinct primes.

Original entry on oeis.org

1, 2, 13, 23, 113, 137, 1131, 1137, 1373, 11379, 11317, 23719, 111317, 113171, 211373, 1113171, 1113173, 1317971, 2313797, 11131733, 11317971, 13179719, 82337397, 52313797, 113179719, 113733797, 523137971, 1113173331, 1131797193, 1797193373, 2113733797, 11131733311, 11719337397

Offset: 0

Carlos Rivera, Apr 24 2004

			For example: a(5) = 137 because 137 is the earliest number that has embedded 5 distinct primes: 3, 7, 13, 37 & 137.

Robert G. Wilson v, Table of n, a(n) for n = 0..38
Carlos Rivera, Puzzle 265. Primes embedded, The Prime Puzzles & Problems Connection.

Cf. A000040, A039997.

f[n_] := Block[{id = IntegerDigits@ n, lst, len}, len = Length@ id; lst = FromDigits@# & /@ Flatten[ Table[ Take[id, {i, j}], {i, 1, len}, {j, i, len}], 1]; Count[ PrimeQ@ Union@ lst, True]] (* after David W. Wilson in A039997 *); t[] := 0; t[1] = 2; k = 1; While[k < 10000000001, a = f@ k; If[ t[a] == 0, t[a] = k; Print[{a, k}]]; k += 2]; t /@ Range[0, 28] (* _Robert G. Wilson v, Apr 10 2024 *)

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)r,r=t;print1(", "n))) \\ Charles R Greathouse IV, Jul 10 2012

from sympy import isprime
from itertools import count, islice
def A039997(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)))
def agen():
    adict, n = dict(), 0
    for k in count(1):
        v = A039997(k)
        if v not in adict: adict[v] = k
        while n in adict: yield adict[n]; n += 1
print(list(islice(agen(), 14))) # Michael S. Branicky, Aug 07 2022

A039997(a(n)) = n and A039997(m) <> n for m < a(n). - Reinhard Zumkeller, Jul 16 2007

Name clarified, offset corrected, and a(9) inserted by Michael S. Branicky, Aug 07 2022

a(22) inserted and a(30)-a(38) added by Robert G. Wilson v, Apr 10 2024

A163753 At least one prime occurs as a substring of the digits of n.

Original entry on oeis.org

2, 3, 5, 7, 11, 12, 13, 15, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 45, 47, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 65, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 83, 85, 87, 89, 92, 93, 95, 97, 101, 102

Offset: 1

Gil Broussard, Aug 03 2009

A039997(a(n)) > 0. - Reinhard Zumkeller, Jan 31 2012

This sequence (written in decimal) is automatic in the terminology of Allouche & Shallit since A071062 is finite. - Charles R Greathouse IV, Jan 31 2012

			a(6) = 12 because "2" is a prime substring of "12".

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for 10-automatic sequences.

Cf. A062115 (complement), A205667 (subsequence), A071062.

a163753 n = a163753_list !! (n-1)
a163753_list = filter ((> 0) . a039997) [0..]
-- Reinhard Zumkeller, Jan 31 2012

A094535 a(n) is the smallest integer m such that A039995(m)=n.

Original entry on oeis.org

1, 2, 13, 23, 113, 131, 137, 1013, 1031, 1273, 1237, 1379, 6173, 10139, 10193, 10379, 10397, 10937, 12397, 12379, 36137, 36173, 101397, 102371, 101937, 102973, 103917, 106937, 109371, 109739, 123797, 123917, 123719, 346137, 193719, 346173

Offset: 0

Farideh Firoozbakht, May 08 2004

			a(6) = 137 because 137 is the smallest number m such that A039995(m) = 6; the six numbers 3, 7, 13, 17, 37 & 137 are primes.
See also A205956 for a(100) = 39467139.

Giovanni Resta, Table of n, a(n) for n = 0..500 (first 101 terms from Reinhard Zumkeller)
Carlos Rivera, Puzzle 265. Primes embedded, The Prime Puzzles & Problems Connection.
Reinhard Zumkeller, Illustration of initial terms

Cf. A039995, A093301, A039997.

Cf. A205956.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a094535 n = a094535_list !! n
a094535_list = map ((+ 1) . fromJust . (`elemIndex` a039995_list)) [0..]
-- Reinhard Zumkeller, Feb 01 2012

cnt[n_] := Count[ PrimeQ@ Union[ FromDigits /@ Subsets[ IntegerDigits[n]]], True]; a[n_] := Block[{k = 1}, While[cnt[k] != n, k++]; k]; Array[a, 21, 0] (* Giovanni Resta, Jun 16 2017 *)

from sympy import isprime
from itertools import chain, combinations as combs, count, islice
def powerset(s): # nonempty subsets of s
    return chain.from_iterable(combs(s, r) for r in range(1, len(s)+1))
def A039995(n):
    ss = set(int("".join(s)) for s in powerset(str(n)))
    return sum(1 for k in ss if isprime(k))
def agen():
    adict, n = dict(), 0
    for k in count(1):
        v = A039995(k)
        if v not in adict: adict[v] = k
        while n in adict: yield adict[n]; n += 1
print(list(islice(agen(), 36))) # Michael S. Branicky, Aug 07 2022

A039995(a(n)) = n and A039995(m) != n for m < a(n). - Reinhard Zumkeller, Feb 01 2012

A205667 Numbers containing exactly one prime in decimal representation.

Original entry on oeis.org

2, 3, 5, 7, 11, 12, 15, 19, 20, 21, 22, 24, 26, 28, 30, 33, 34, 36, 38, 39, 41, 42, 45, 50, 51, 54, 55, 56, 58, 61, 62, 63, 65, 70, 74, 76, 77, 78, 82, 85, 87, 89, 92, 93, 95, 101, 102, 105, 109, 110, 111, 114, 116, 118, 120, 121, 122, 124, 126, 128, 141

Offset: 1

Reinhard Zumkeller, Jan 31 2012

A039997(a(n)) = 1.

			A039997(10) = #{} = 0, therefore 10 is not a term;
A039997(11) = #{11} = 1, therefore 11 is a term;
A039997(12) = #{2} = 1, therefore 12 is a term;
A039997(13) = #{3, 13} = 2, therefore 13 is not a term.

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

Subsequence of A163753.

a205667 n = a205667_list !! (n-1)
a205667_list = filter ((== 1) . a039997) [0..]
-- Reinhard Zumkeller, Jan 31 2012

A211396 Smallest prime substring of n, or 0 if no such substring exists.

Original entry on oeis.org

0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 2, 3, 0, 5, 0, 7, 0, 19, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 0, 41, 2, 3, 0, 5, 0, 7, 0, 0, 5, 5, 2, 3, 5, 5, 5, 5, 5, 5, 0, 61, 2, 3, 0, 5, 0, 7, 0, 0, 7, 7, 2, 3, 7, 5, 7, 7, 7, 7, 0, 0, 2, 3, 0, 5

Offset: 0

Reinhard Zumkeller, Feb 08 2013

a(n) <= A047814(n);
a(n) = 0 iff A039997(n) = 0, cf. A062115;
a(n) = n iff n is prime and A039997(n) = 1.

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

import Data.List (isInfixOf)
a211396 n = if null ips then 0 else head ips
   where ips = [p | p <- takeWhile (<= n) a000040_list,
                    show p `isInfixOf` show n]

cp's OEIS Frontend

A039996 Number of distinct primes embedded in prime(n) as substrings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A079066 "Memory" of prime(n): the number of distinct (previous) primes contained as substrings in prime(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A062115 Numbers with no prime substring in their decimal expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A093301 Earliest positive integer having embedded exactly k distinct primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula