I have calculated the earliest integer having k distinct primes embedded, for 1<=k<=30. Here are my results (see A093301 )
:

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

Questions

1. Can you predict the quantity of digits of the smallest number having embedded k distinct primes?

2. According with your prediction (or without any prediction at all) can you find a number having a) 100  b) 500 distinct primes embedded?

Solution:

Contributions came from Ray Opao and Faride Firoozbakht.

Ray Opao wrote:

1. If letters represent digits, then the following are the maximum possible imbedded primes: digits number primes k

1 a a 1
2 ab a,b,ab 3
3 abc a,b,c,ab,bc,abc 6
4 abcd a,b,c,d,ab,bc,cd,abc,bcd,abcd 10
5 abcde a,b,c,d,e,ab,bc,cd,de,abc,bcd,cde,abcd,bcde,abcde 15
etc etc etc etc

if n represents the number of digits, then k <= (n^2+n)/2 using the quadratic formula: n >= (2k+.25)^.5-.5

2.a. if k = 100, then n >= 13.7 The number with 100 distinct primes has at least 14 digits, but I haven't found that number yet.

2.b. if k = 500, then n >= 31.1 The number with 500 distinct primes has at least 31 digits, but I also haven't found this number.

***

Faride wrote:

Answer to Q.2: I found many numbers with 100 or 500 distinct embedded primes , the smallest of those for k=100 is a 35-digit number n1 and for k=500 is a 139-digit number n2,

n1= 135793793791919137371711311331397173931359379 (35-digit)

n2= 91813183113113111113111119111111191131117119311/ 19131979731537911379371937918759137371711397973/ 135793793791919137371711311331397173931359379 (139-digit)

Can you find smaller numbers which having embedded 100 or 500 distinct primes?

***

Faride Firoozbakht has found the earliest integer having exactly 9 and 22 embedded primes:

A093301(9)=101317

A093301(22)= 82337397

***

Faride also sent the following contribution to my request ("Can you improve the approximation give by Opao?"):

If f(n) is the largest number of embedded distinct primes of a n-digit number I think an approximation for f(n) which is better than sum(j, {j,1,n})=n(n+1)/2 regarding to Prime Number Theorem is ceiling(sum(j/log(j), {j,2,n})).

Let, g1(1)=1, g1(n)=ceiling( sum(j/log[j], {j,2,n})) (for n > 1) , so I think, " A n-digit number embedded at most g1(n) distinct primes. "

(I) I couldn't find a counter example for this statement.

g1(n) for n=1,2,...,65 :

1,3,6,9,12,15,19,23,27,31,36,41,46,51,57,62,68, 75,81,88,95,102,109,117,124,132,141,149,158,166 ,176,185,194,204,214,224,234,244,255,266,277,288 ,300,311,323,335,347,360,372,385,398,411,425,438 ,452,466,480,494,509,523,538,553,568,584,599

For example a number which embedded 100 distinct primes has at least 22 digits because g1(21)=95 & g1(22)=102 and a number which embedded 500 distinct primes has at least 59 digits because g1(58)=494 & g1(59)=509.

Let g2(m) be number of distinct embedded primes of m. I could find numbers m ,which g2(m)= 100,200,300,...,1000. Here are such numbers m with smallest number of digits, (that I could find ):

m1 (27-digit) g2(m1)=100, m2 (49-digit) g2(m2)=200
m3 (70-digit) g2(m3)=300, m4 (89-digit) g2(m4)=400
m5 (107-digit) g2(m5)=500, m6 (127-digit) g2(m6)=600
m7 (143-digit) g2(m7)=700, m8 (160-digit) g2(m8)=800
m9 (177-digit) g2(m9)=900, m10 (192-digit) g2(m10)=1000

m1= 179719337391131771739397731 (27-digit) g2(m1)=100

m5= 28187696823241434725761797193373911317717393977317791
733113933197137313779397911717737397191199733379371333 (107-digit) g2(m5)=500

m10= 1818769682324143472576179719337391131771739397731779
1733113933197137313779397911717737397191199733379379
3397799133999139373991311971711937993939191337331193
113997719991117319133911711177773173(192-digit) g2(m10)=1000.

According to my empirical results I guess that:

" f(n)< 6*n " (II)

Opao proved that f(n)<= 1/2*n*(n+1).

(II) implies g2(m) < 6/Ln(10)*log(10*m) (III).

***