A093301 Earliest positive integer having embedded exactly k distinct primes.

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,2

Links

Robert G. Wilson v, Table of n, a(n) for n = 0..38

Carlos Rivera, Puzzle 265. Primes embedded, The Prime Puzzles & Problems Connection.

Formula

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

Example

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

Mathematica

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

Prog

(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)<n*10, if(isprime(n%t), v=concat(v, n%t))); v=vecsort(v, , 8); n\=10); v
print1(1); r=0; for(n=1, 1e6, t=#dp(n); if(t>r, r=t; print1(", "n))) \\ Charles R Greathouse IV, Jul 10 2012
(Python)
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

Crossrefs

Cf. A000040, A039997.

Sequence in context: A035244 A085822 A213321 * A079397 A118524 A029971

Adjacent sequences: A093298 A093299 A093300 * A093302 A093303 A093304

Keyword

base,nonn,more,changed

Author

Carlos Rivera, Apr 24 2004

Extensions

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

Status

approved