login
Earliest positive integer having embedded exactly k distinct primes.
4

%I #25 Apr 23 2024 07:56:10

%S 1,2,13,23,113,137,1131,1137,1373,11379,11317,23719,111317,113171,

%T 211373,1113171,1113173,1317971,2313797,11131733,11317971,13179719,

%U 82337397,52313797,113179719,113733797,523137971,1113173331,1131797193,1797193373,2113733797,11131733311,11719337397

%N Earliest positive integer having embedded exactly k distinct primes.

%H Robert G. Wilson v, <a href="/A093301/b093301.txt">Table of n, a(n) for n = 0..38</a>

%H Carlos Rivera, <a href="http://www.primepuzzles.net/puzzles/puzz_265.htm">Puzzle 265. Primes embedded</a>, The Prime Puzzles & Problems Connection.

%F A039997(a(n)) = n and A039997(m) <> n for m < a(n). - _Reinhard Zumkeller_, Jul 16 2007

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

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

%o (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

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

%o (Python)

%o from sympy import isprime

%o from itertools import count, islice

%o def A039997(n):

%o s = str(n)

%o ss = (int(s[i:j]) for i in range(len(s)) for j in range(i+1, len(s)+1))

%o return len(set(k for k in ss if isprime(k)))

%o def agen():

%o adict, n = dict(), 0

%o for k in count(1):

%o v = A039997(k)

%o if v not in adict: adict[v] = k

%o while n in adict: yield adict[n]; n += 1

%o print(list(islice(agen(), 14))) # _Michael S. Branicky_, Aug 07 2022

%Y Cf. A000040, A039997.

%K base,nonn

%O 0,2

%A _Carlos Rivera_, Apr 24 2004

%E Name clarified, offset corrected, and a(9) inserted by _Michael S. Branicky_, Aug 07 2022

%E a(22) inserted and a(30)-a(38) added by _Robert G. Wilson v_, Apr 10 2024