Just as with primes, we can have left truncatable and right truncatable semiprimes. The smallest semiprime is 6 = 2 x 3 and using that as our starting point, we can build a chain of left truncatable semiprimes as shown below (permalink):
Semiprime | Factorisation --------------------------------------------- 6 | 2 * 3 46 | 2 * 23 446 | 2 * 223 2446 | 2 * 1223 62446 | 2 * 31223 762446 | 2 * 381223 6762446 | 2 * 3381223 86762446 | 2 * 43381223 986762446 | 2 * 493381223 4986762446 | 2 * 2493381223 34986762446 | 2 * 17493381223 634986762446 | 2 * 317493381223 9634986762446 | 2 * 4817493381223 59634986762446 | 2 * 29817493381223 959634986762446 | 2 * 479817493381223 9959634986762446 | 2 * 4979817493381223 39959634986762446 | 2 * 19979817493381223 439959634986762446 | 2 * 219979817493381223 8439959634986762446 | 2 * 4219979817493381223 48439959634986762446 | 2 * 24219979817493381223 248439959634986762446 | 2 * 124219979817493381223 4248439959634986762446 | 2 * 2124219979817493381223 84248439959634986762446 | 2 * 42124219979817493381223 984248439959634986762446 | 2 * 492124219979817493381223
The next semiprime is 10 = 2 x 5 stops right where it starts and no digits added its left will produce a semiprime. Next we have 14 = 2 x 7 (permalink):
Semiprime | Factorisation --------------------------------------------- 14 | 2 * 7 214 | 2 * 107 7214 | 2 * 3607 87214 | 2 * 43607 187214 | 2 * 93607 5187214 | 2 * 2593607 35187214 | 2 * 17593607 735187214 | 2 * 367593607 5735187214 | 2 * 2867593607 95735187214 | 2 * 47867593607 495735187214 | 2 * 247867593607 3495735187214 | 2 * 1747867593607 53495735187214 | 2 * 26747867593607 353495735187214 | 2 * 176747867593607 6353495735187214 | 2 * 3176747867593607 16353495735187214 | 2 * 8176747867593607 316353495735187214 | 2 * 158176747867593607However, when we input 21 = 3 x 7 the program times out. As Gemini says:
The next semiprime is 15 = 3 x 5 and it produces the following chain (permalink):Semiprime | Factorisation --------------------------------------------- 15 | 3 * 5 415 | 5 * 83 7415 | 5 * 1483 27415 | 5 * 5483 927415 | 5 * 185483 7927415 | 5 * 1585483 97927415 | 5 * 19585483 597927415 | 5 * 119585483 6597927415 | 5 * 1319585483 66597927415 | 5 * 13319585483 366597927415 | 5 * 73319585483 3366597927415 | 5 * 673319585483 33366597927415 | 5 * 6673319585483 733366597927415 | 5 * 146673319585483 9733366597927415 | 5 * 1946673319585483 69733366597927415 | 5 * 13946673319585483 869733366597927415 | 5 * 173946673319585483 9869733366597927415 | 5 * 1973946673319585483 49869733366597927415 | 5 * 9973946673319585483
The timeout occurs because some starting numbers, like 21, spawn massive branching paths of valid semiprimes. As the numbers grow larger with each prepended digit, the prime factorization calculations become increasingly computationally expensive.
Setting a maximum depth prevents a timeout but we never get to see the end of the chain. With a maximum depth of 10, we get the following chain of semiprimes:
Semiprime | Factorisation --------------------------------------------- 21 | 3 * 7 121 | 11 * 11 1121 | 19 * 59 81121 | 23 * 3527 181121 | 71 * 2551 2181121 | 853 * 2557 32181121 | 7 * 4597303 932181121 | 139 * 6706339 3932181121 | 11 * 357471011 33932181121 | 87683 * 386987
33 = 3 x 11 has the same problem as 21. As I said to Gemini:
The problem with the generation of the semiprime chain seems to be ensuring that it is the longest possible chain. Let’s not try to ensure this. Let’s start with a semiprime like 21 and look for the smallest possible digit that, appended to the left, produces a new semiprime. Let’s proceed on that basis until no suitable digit can be found and the chain ends. Can you construct a chain based on that criterion (with no maximum depth specified). Output as before: table and comma-separated list.The resultant program produced this output for 21 when it was revised (permalink):
Semiprime | Factorisation --------------------------------------------- 21 | 3 * 7 121 | 11 * 11 1121 | 19 * 59 81121 | 23 * 3527 181121 | 71 * 2551 2181121 | 853 * 2557 32181121 | 7 * 4597303 932181121 | 139 * 6706339 3932181121 | 11 * 357471011 33932181121 | 87683 * 386987 633932181121 | 181 * 3502387741 2633932181121 | 3 * 877977393707 52633932181121 | 17 * 3096113657713 252633932181121 | 976453 * 258726157 3252633932181121 | 36187 * 89884044883 63252633932181121 | 31 * 2040407546199391 363252633932181121 | 3851 * 94326833012771 3363252633932181121 | 757811 * 4438115353211 53363252633932181121 | 3 * 17787750877977393707 153363252633932181121 | 103 * 1488963617805166807 3153363252633932181121 | 809657423 * 3894688250927 73153363252633932181121 | 13 * 5627181788664148629317 373153363252633932181121 | 331537 * 1125525546930309233 2373153363252633932181121 | 35724754739 * 66428821711739
Semiprime | Factorisation --------------------------------------------- 14 | 2 * 7 214 | 2 * 107 1214 | 2 * 607 21214 | 2 * 10607 121214 | 2 * 60607
Semiprime | Factorisation --------------------------------------------- 33 | 3 * 11 133 | 7 * 19 1133 | 11 * 103 21133 | 7 * 3019 121133 | 29 * 4177 2121133 | 7 * 303019 22121133 | 3 * 7373711 122121133 | 107 * 1141319 9122121133 | 4363 * 2090791 39122121133 | 19 * 2059059007 139122121133 | 2801 * 49668733 4139122121133 | 3 * 1379707373711 44139122121133 | 13 * 3395317086241 144139122121133 | 683 * 211038246151 8144139122121133 | 60510661 * 134590153 18144139122121133 | 11 * 1649467192920103
Semiprime | Factorisation --------------------------------------------- 28293 | 3 * 9431 428293 | 53 * 8081 1428293 | 131 * 10903 11428293 | 3 * 3809431 211428293 | 9419 * 22447 2211428293 | 6073 * 364141 12211428293 | 4073 * 2998141 312211428293 | 7433 * 42003421 2312211428293 | 13 * 177862417561 32312211428293 | 4967 * 6505377779 332312211428293 | 3659 * 90820500527 4332312211428293 | 18301 * 236725436393 84332312211428293 | 41 * 2056885663693373 284332312211428293 | 3 * 94777437403809431 2284332312211428293 | 17 * 134372488953613429
I'll investigate the generation of right truncatable semiprimes in a future post.
No comments:
Post a Comment