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 35digit
number n1 and for k=500 is a 139digit number n2,
n1= 135793793791919137371711311331397173931359379
(35digit)
n2= 91813183113113111113111119111111191131117119311/
19131979731537911379371937918759137371711397973/
135793793791919137371711311331397173931359379 (139digit)
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 ndigit 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 ndigit 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 (27digit) g2(m1)=100, m2 (49digit) g2(m2)=200
m3 (70digit) g2(m3)=300, m4 (89digit) g2(m4)=400
m5 (107digit) g2(m5)=500, m6 (127digit) g2(m6)=600
m7 (143digit) g2(m7)=700, m8 (160digit) g2(m8)=800
m9 (177digit) g2(m9)=900, m10 (192digit) g2(m10)=1000
m1= 179719337391131771739397731 (27digit) g2(m1)=100
m5=
28187696823241434725761797193373911317717393977317791
733113933197137313779397911717737397191199733379371333 (107digit)
g2(m5)=500
m10=
1818769682324143472576179719337391131771739397731779
1733113933197137313779397911717737397191199733379379
3397799133999139373991311971711937993939191337331193
113997719991117319133911711177773173(192digit) 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).
***
