Problems & Puzzles: Puzzles

Puzzle 1015. Sequence of semprimes Igor Schein sent the following nice puzzle, as a part of a larger one: Get sequences of semiprimes according to the rules implicit in the following example: {15, 35, 57, 319, 2911, 4171} 15=3*5 35=5*7 57=3*19 319=11*29 2911=41*71 4171=43*97 End because 4397 and 9743 are primes. In general the sequence ends when it is not possible to get another semiprime. Q1. Send your largest sequence. Q2. Are possible sequences of any number of members?

---

During the week Aug 24-Set 4, contributions came from Ray Opao, Oscar Volpatti, Adam Stinchcombe, Simon Cavegn, Metin Sariyar, Giorgos Kalogeropoulos, Jeff Heleen, Emmanuel Vantieghem.

***

Ray wrote:

Q1: My largest sequence so far has a length of 20:

1. 35239=131*269
2. 131269=149*881
3. 149881=71*2111
4. 712111=829*859
5. 829859=467*1777
6. 1777467=3*592489
7. 3592489=83*43283
8. 4328383=569*7607
9. 7607569=359*21191
10. 21191359=7*3027337
11. 73027337=3761*19417
12. 194173761=3*64724587
13. 364724587=107*3408641
14. 3408641107=1549*2200543
15. 22005431549=353*62338333
16. 62338333353=3*20779444451
17. 207794444513=54751*3795263
18. 379526354751=3*126508784917
19. 1265087849173=29*43623718937
20. 2943623718937=11*267602156267
 

 

Q2: I think all sequence lengths less than the longest lengths are possible
 (e.g., I could get a length of 18 if I started from the 3rd in my list of 20). However, I tried finding the earliest occurrence
of each length and came up with only the first 12:

 

length = 1
1. 6=2*3

length = 2
1. 4=2*2
2. 22=2*11

length = 3 (overlaps with length=4)
1. 55=5*11
2. 115=5*23
3. 235=5*47

length = 4
1. 25=5*5
2. 55=5*11
3. 115=5*23
4. 235=5*47

length = 5
1. 26=2*13
2. 213=3*71
3. 371=7*53
4. 753=3*251
5. 2513=7*359

length = 6
1. 15=3*5
2. 35=5*7
3. 57=3*19
4. 319=11*29
5. 2911=41*71
6. 4171=43*97

length = 7
1. 118=2*59
2. 259=7*37
3. 737=11*67
4. 1167=3*389
5. 3893=17*229
6. 17229=3*5743
7. 35743=31*1153

length = 8
1. 25=5*5
2. 55=5*11
3. 511=7*73
4. 737=11*67
5. 1167=3*389
6. 3893=17*229
7. 17229=3*5743
8. 35743=31*1153

length = 9
1. 10=2*5
2. 25=5*5
3. 55=5*11
4. 511=7*73
5. 737=11*67
6. 1167=3*389
7. 3893=17*229
8. 17229=3*5743
9. 35743=31*1153

length = 10
1. 187=11*17
2. 1711=29*59
3. 2959=11*269
4. 11269=59*191
5. 59191=11*5381
6. 538111=7*76873
7. 776873=97*8009
8. 800997=3*266999
9. 2669993=137*19489
10. 19489137=3*6496379

length = 11 (overlaps with length=12)
1. 289=17*17
2. 1717=17*101
3. 10117=67*151
4. 15167=29*523
5. 52329=3*17443
6. 174433=7*24919
7. 724919=13*55763
8. 1355763=3*451921
9. 4519213=179*25247
10. 25247179=4217*5987
11. 59874217=13*4605709

length = 12
1. 178=2*89
2. 289=17*17
3. 1717=101*17
4. 10117=151*67
5. 15167=523*29
6. 52329=17443*3
7. 174433=7*24919
8. 724919=13*55763
9. 1355763=451921*3
10. 4519213=25247*179
11. 25247179=5987*4217
12. 59874217=13*4605709

***

Oscar wrote:

Given a known Cunningham chain of the first kind p(1)...p(k), a nice construction allows to build a legal sequence of semiprimes with length k, as follows.

 

Let's start with the semiprime q(1) = 5*p(1).

Then, given a semiprime q(n) = 5*p(n), concatenate its factors by placing p(n) before 5, obtaining the semiprime
 

q(n+1) = 10*p(n)+5 = 5*(2*p(n)+1) = 5*p(n+1).

 

It follows from Dickson's conjecture that for every k there are infinitely many Cunningham chains of the first kind with length k, so that puzzle question Q2 is widely believed to have a positive answer.

 

About question Q1, the largest Cunningham chain of the first kind I'm aware of was found by Jaroslaw Wroblewski in 2008. It has length 17 and starts with p(1)=2759832934171386593519. But of course we have many more degrees of freedom in solving puzzle 1015, so almost surely there are much longer sequences arising from much smaller semiprimes.

...

I searched for some semiprime champion sequences, according to the following rules.

The base-10 representation of the first semiprime can't be the concatenation of two primes, so that the sequence can't be extended backwards.

e.g. 15 is a legal starting semiprime, 25 and 35 are not.

Given the first semiprime, find the longest possible sequence; in case of ties, choose the sequence which minimizes last semiprime.

e.g. 15 -> 35 -> 57 -> 319 -> 2911 -> 7141 -> 19337, not 37193. 

For a given length, choose the sequence which minimizes the first semiprime

(but last semiprime may be shared by sequences with different lengths).

 

Table of semiprime champion sequences starting below 10^8, with length up to 23.
 

1     6 -> 6  

2     4 -> 22 

3     74 -> 793

4     121 -> 17653

5     123 -> 4577

6     34 -> 38937

7     15 -> 19337

8     95 -> 2251523

9     26 -> 1812731

10   10 -> 79727

11   391 -> 19625621

12   178 -> 59874217

13   1253 -> 31990356683

14   6274 -> 8777125967

15   453 -> 8777125967

16   145 -> 172173523

17   311507 -> 315574551293

18   78331 -> 2943623718937

19   1354427 -> 3153029718942797

20   35239 -> 2943623718937

21   28907 -> 3153029718942797

22   none starting below 10^8

23   16064229 -> 66405730062474129

 

This is the champion sequence with claimed length 23:

 

16064229 = 3*5354743

35354743 = 6869*5147

68695147 = 17*4040891

174040891 = 18899*9209

188999209 = 7*26999887

726999887 = 13716979*53

1371697953 = 457232651*3

4572326513 = 2711*1686583

27111686583 = 9037228861*3

90372288613 = 53*1705137521

531705137521 = 124097*4284593

1240974284593 = 17*72998487329

1772998487329 = 463*3829370383

4633829370383 = 133297741*34763

13329774134763 = 3*4443258044921

34443258044921 = 11*3131205276811

113131205276811 = 3*37710401758937

337710401758937 = 19*17774231671523

1917774231671523 = 3*639258077223841

3639258077223841 = 13829*263161333229

13829263161333229 = 19257661*718117489

19257661718117489 = 664057300624741*29

66405730062474129 = 3*22135243354158043

***

Adam wrote:

I found a sequence of length 21, [78107, 211137, 370379, 1721787, 5739293, 7819899, 32606633,
83392851, 277976173, 882131513, 1751890089, 3583963363, 6827524969, 23302133293,
 104166892237, 469008972221, 4196197311177, 13987324370593, 71998189195799, 459089156828391, 3153029718942797]  with  

 

78107=2111*37
211137=3*70379
370379=17*21787

1721787=573929*3
5739293=7*819899
7819899=3*2606633

32606633=83*392851
83392851=27797617*3

277976173=8821*31513
882131513=17*51890089

1751890089=3*583963363
3583963363=6827*524969

6827524969=23302133*293
23302133293=10416689*2237

104166892237=46900897*2221
469008972221=41961973*11177

4196197311177=1398732437059*3

13987324370593=7*1998189195799

71998189195799=459089*56828391

459089156828391=3*153029718942797

3153029718942797=966157*3263475521

 

While     9661573263475521 = (3)^2*241*1553*97523*29411 and 3263475521966157=(3)^2*1019*5350363*66509

***

Simon wrote:

Q1: Length 23
16064229 = 3 * 5354743
35354743 = 6869 * 5147
68695147 = 17 * 4040891
174040891 = 18899 * 9209
188999209 = 7 * 26999887
726999887 = 13716979 * 53
1371697953 = 457232651 * 3
4572326513 = 2711 * 1686583
27111686583 = 9037228861 * 3
90372288613 = 53 * 1705137521
531705137521 = 124097 * 4284593
1240974284593 = 17 * 72998487329
1772998487329 = 463 * 3829370383
4633829370383 = 133297741 * 34763
13329774134763 = 3 * 4443258044921
34443258044921 = 11 * 3131205276811
113131205276811 = 3 * 37710401758937
337710401758937 = 19 * 17774231671523
1917774231671523 = 3 * 639258077223841
3639258077223841 = 13829 * 263161333229
13829263161333229 = 19257661 * 718117489
19257661718117489 = 664057300624741 * 29
66405730062474129 = 3 * 22135243354158043

 

Special Q1: Allowing up to 4 leading zero's for second factor: Length 42

15 = 3 * 5
35 = 5 * 7
57 = 3 * 19
319 = 29 * 11
2911 = 71 * 0041
710041 = 13397 * 53
1339753 = 78809 * 17
7880917 = 11 * 716447
11716447 = 41 * 0285767
410285767 = 167 * 2456801
1672456801 = 4557103 * 367
4557103367 = 198134929 * 0023
1981349290023 = 3 * 660449763341
3660449763341 = 7 * 522921394763
7522921394763 = 3 * 02507640464921
302507640464921 = 223 * 001356536504327
223001356536504327 = 74333785512168109 * 3
743337855121681093 = 53 * 0014025242549465681
530014025242549465681 = 75716289320364209383 * 007
75716289320364209383007 = 29200265838937219199 * 2593
292002658389372191992593 = 97334219463124063997531 * 3
973342194631240639975313 = 353511023 * 02753357409823231
35351102302753357409823231 = 11783700767584452469941077 * 3
117837007675844524699410773 = 5625483729213945896759 * 020947
5625483729213945896759020947 = 3 * 01875161243071315298919673649
301875161243071315298919673649 = 499 * 0604960242972086804206251851
4990604960242972086804206251851 = 3 * 1663534986747657362268068750617
31663534986747657362268068750617 = 47 * 673692233760588454516341888311
47673692233760588454516341888311 = 2509141696513715181816649573069 * 19
250914169651371518181664957306919 = 6119857796374915077601584324559 * 41
611985779637491507760158432455941 = 203995259879163835920052810818647 * 003
203995259879163835920052810818647003 = 747737 * 0272816859242171827688148120019
7477370272816859242171827688148120019 = 3 * 2492456757605619747390609229382706673
32492456757605619747390609229382706673 = 878174506962314047226773222415748829 * 37
87817450696231404722677322241574882937 = 777313 * 000112975661922843699671403054164249
777313000112975661922843699671403054164249 = 3 * 259104333370991887307614566557134351388083
3259104333370991887307614566557134351388083 = 19 * 171531807019525888805663924555638650073057
19171531807019525888805663924555638650073057 = 11 * 1742866527910865989891423993141421695461187
111742866527910865989891423993141421695461187 = 37247622175970288663297141331047140565153729 * 00003
3724762217597028866329714133104714056515372900003 = 923429167 * 004033619849476802227029627853529467362509
923429167004033619849476802227029627853529467362509 = 3 * 0307809722334677873283158934075676542617843155787503
30307809722334677873283158934075676542617843155787503 = 8243 * 3676793609406123725983641748644386332963465140821

***

Metin wrote:

Q1:
The one I found has 16 steps;
1. 636542506 = 2 × 318271253
2. 2318271253 = 4999 × 463747
3. 4999463747 = 23 × 217367989
4. 23217367989 = 3 × 7739122663
5. 37739122663 = 11 × 3430829333
6. 113430829333 = 20549 × 5520017
7. 205495520017 = 31601 × 6502817
8. 316016502817 = 179 × 1765455323
9. 1791765455323 = 19 × 94303445017
10. 1994303445017 = 13 × 153407957309
11. 13153407957309 = 3 × 4384469319103
12. 34384469319103 = 19469 × 1766113787
13. 194691766113787 = 47 × 4142378002421
14. 474142378002421 = 1187 × 399445979783
15. 1187399445979783 = 43 × 27613940604181
16. 4327613940604181 = 17 × 254565525917893

 

Searched up to 76x10^8 for the one with 17 or more steps.

***

Giorgos wrote:

Here is my largest (18-terms) sequence:

{22072747,132411667,575702923,1131047509,1280988301,7535225317,8984665453,70313127781,
135408702137,307441070691,1024803568973,3863265286971,12877550956573,55989351985123,
192946807999217,768712382467251,3256237460822417,19001171371899417}]
 

 

1. 22072747=1667*13241

2. 132411667=23*5757029

3. 575702923=509*1131047

4. 1131047509=12809*88301

5. 1280988301=17*75352253

6. 7535225317=89*84665453

7. 8984665453=70313*127781

8. 70313127781=13*5408702137

9. 135408702137=307*441070691

10. 307441070691=3*102480356897

11. 1024803568973=3863*265286971

12. 3863265286971=3*1287755095657

13. 12877550956573=23*559893519851

14. 55989351985123=19*2946807999217

15.192946807999217=251*768712382467

16. 768712382467251=3*256237460822417

17. 3256237460822417=19001*171371899417

18. 19001171371899417=3*6333723790633139

***

Jeff wrote:

First, in the example given, it actually is one longer.

1. 15 = 3 * 5

2. 35 = 5 * 7

3. 57 = 3 * 19

4. 319 - 11 * 29

5. 2911 = 41 * 71

6. 7141 = 37 * 193

7. 37193 = 13 * 2861 or 19337 = 286113

 

Q1. I found a chain length of 13 for start number 145.

 

1.                                                         145 = 5 * 29

2.                                                         295 = 5 * 59

3.                                                         559 = 13 * 43

4.                                                       1343 = 17 * 79

5.                                                       1779 = 3 * 593

6.                                                       5933 = 17 * 349

7.                                                     17349 = 3 * 5783

8.                                                     57833 = 151 * 383

9.                           151383 = 3 * 50461                                        383151 = 3 * 127717

10. 350461 = 97 * 3613                504613 = 53 * 9521              1277173 = 59 * 21647

11. 361397 = 173 * 2089              952153 = 17 * 56009            5921647 = 313 * 18919

12. 1732089 = 3 * 577363          5600917 = 7 * 800131          18919313 = 7 * 27027597

13. 577363 = 331 * 174433        8001317 = 31 * 258107        27027597 = 3 * 9009199

 

*** 

Emmanuel wrote:

It seems to me that this puzzle is a variant of Puzzle 640 where the concatenations apparently should have been of the form  p&q (with p, q primes, p < q).
In that puzzle, Jan van Delden also allowed p&q AND q&p and found 21 semiprimes (which is, in my opinion, the task in the present puzzle).

My biggest sequence has 23 semiprimes :

16064229 = 3*5354743
35354743 = 5147*6869
68695147 = 17*4040891
174040891 = 9209*18899
188999209 = 7*26999887
726999887 = 53*13716979
1371697953 = 3*457232651
4572326513 = 2711*1686583
27111686583 = 3*9037228861
90372288613 = 53*1705137521
531705137521 = 124097*4284593
1240974284593 = 17*72998487329
1772998487329 = 463*3829370383
4633829370383 = 34763*133297741
13329774134763 = 3*4443258044921
34443258044921 = 11*3131205276811
113131205276811 = 3*37710401758937
337710401758937 = 19*17774231671523
1917774231671523 = 3*639258077223841
3639258077223841 = 13829*263161333229
13829263161333229 = 19257661*718117489
19257661718117489 = 29*664057300624741
66405730062474129 = 3*22135243354158043
322135243354158043 = 43*317*23632546647653, NOT a semiprime (neither is  221352433541580433)  .
 

If there exist a longer sequence, its first element must be greater than  2^32.

***