Problems & Puzzles: Puzzles

Puzzle 265.  Primes embedded

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

k Qty. of primes
1 2
2 13
3 23
4 113
5 137
6 1131
7 1137
8 1373
10 11317
11 23719
12 111317
13 113171
14 211373
15 1113171
16 1113173
17 1317971
18 2313797
19 11131733
20 11317971
21 13179719
23 52313797
24 113179719
25 113733797
26 523137971
27 1113173331
28 1131797193
29 1797193373
30 2113733797

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

***

 

 



Records   |  Conjectures  |  Problems  |  Puzzles