Left and Right Truncatable Triprimes

What was done with left and right truncatable semiprimes can also be done with triprimes. The very first triprime is 8 = 2 x 2 x 2 and, by adding suitable digits to the LEFT, we get (permalink):

Triprime             | Factorisation
---------------------------------------------
8                    | 2 * 2 * 2
18                   | 2 * 3 * 3
318                  | 2 * 3 * 53
2318                 | 2 * 19 * 61
12318                | 2 * 3 * 2053
112318               | 2 * 89 * 631
6112318              | 2 * 101 * 30259
16112318             | 2 * 53 * 152003
216112318            | 2 * 7687 * 14057
4216112318           | 2 * 11 * 191641469
24216112318          | 2 * 73 * 165863783
124216112318         | 2 * 19 * 3268845061
5124216112318        | 2 * 3203 * 799908853
25124216112318       | 2 * 3 * 4187369352053
225124216112318      | 2 * 431 * 261164983889
2225124216112318     | 2 * 193 * 5764570508063

Next we have 12 = 2 x 2 x 3 which gives (permalink):

Triprime             | Factorisation
---------------------------------------------
12                   | 2 * 2 * 3
212                  | 2 * 2 * 53
5212                 | 2 * 2 * 1303
15212                | 2 * 2 * 3803
315212               | 2 * 2 * 78803
2315212              | 2 * 2 * 578803

The next triprime (18) gives the same chain as did 8. 

Let's try adding digits to the RIGHT this time. Starting with 8 we don't get very far as no digit when adding to the right of 8 will produce a triprime. However, with 12 we have more success (permalink):

Triprime             | Factorisation
---------------------------------------------
12                   | 2 * 2 * 3
124                  | 2 * 2 * 31
1244                 | 2 * 2 * 311
12445                | 5 * 19 * 131
124453               | 7 * 23 * 773
1244534              | 2 * 349 * 1783
12445341             | 3 * 167 * 24841
124453414            | 2 * 23 * 2705509
1244534143           | 19 * 19 * 3447463
12445341431          | 769 * 2053 * 7883
124453414317         | 3 * 23789 * 1743851
1244534143173        | 3 * 31 * 13382087561
12445341431731       | 13 * 887 * 1079294201

The next triprime (18) produces this chain (permalink):

Triprime             | Factorisation
---------------------------------------------
18                   | 2 * 3 * 3
182                  | 2 * 7 * 13
1825                 | 5 * 5 * 73
18255                | 3 * 5 * 1217
182553               | 3 * 7 * 8693
1825534              | 2 * 227 * 4021
18255345             | 3 * 5 * 1217023
182553451            | 31 * 331 * 17791
1825534511           | 17 * 967 * 111049
18255345115          | 5 * 7 * 521581289
182553451151         | 17 * 5147 * 2086349
1825534511511        | 3 * 53 * 11481349129

With a large triprime like 28282 = 2 x 79 x 179 we end up with (permalink):

Triprime             | Factorisation
---------------------------------------------
28282                | 2 * 79 * 179
282821               | 7 * 11 * 3673
2828211              | 3 * 619 * 1523
28282113             | 3 * 3 * 3142457
282821134            | 2 * 5099 * 27733
2828211341           | 17 * 29 * 5736737
28282113411          | 3 * 32621 * 288997
282821134111         | 43 * 563 * 11682479
2828211341111        | 13 * 26591 * 8181517
28282113411116       | 2 * 2 * 7070528352779
282821134111163      | 59 * 1307821 * 3665317

So the program is working well.

Right Truncatable Semiprimes

Having learned from the experience of creating left truncable semiprimes in the previous post, I won't try creating the longest possible chain associated with a given semiprime. Instead, starting with a given semiprime, digits 0 to 9 will be added to the right of the semiprime until a semiprime is found and the process repeated until none of the digits from 0 to 9 can create a semiprime. Let's start with the first semiprime 6 = 2 x 3 (permalink):

Semiprime            | Factorisation
---------------------------------------------
6                    | 2 * 3
62                   | 2 * 31
622                  | 2 * 311
6227                 | 13 * 479
62277                | 3 * 20759
622771               | 23 * 27077
6227711              | 7 * 889673
62277118             | 2 * 31138559
622771187            | 1889 * 329683
6227711873           | 65267 * 95419
62277118733          | 137 * 454577509
622771187339         | 7 * 88967312477
6227711873391        | 3 * 2075903957797
62277118733913       | 3 * 20759039577971

Next we have 10 = 2 x 5 (permalink):

Semiprime            | Factorisation
---------------------------------------------
10                   | 2 * 5
106                  | 2 * 53
1067                 | 11 * 97
10671                | 3 * 3557
106717               | 13 * 8209
1067173              | 19 * 56167
10671731             | 7 * 1524533
106717315            | 5 * 21343463
1067173151           | 11 * 97015741
10671731513          | 653 * 16342621
106717315135         | 5 * 21343463027
1067173151351        | 523 * 2040484037

Next we have 14 = 2 x 7 (permalink).

Semiprime            | Factorisation
---------------------------------------------
14                   | 2 * 7
141                  | 3 * 47
1411                 | 17 * 83
14111                | 103 * 137
141119               | 11 * 12829
1411193              | 7 * 201599
14111933             | 11 * 1282903
141119339            | 83 * 1700233

Next we have 15 = 3 x 5 (permalink).

Semiprime            | Factorisation
---------------------------------------------
15                   | 3 * 5
155                  | 5 * 31
1555                 | 5 * 311
15553                | 103 * 151
155531               | 43 * 3617

Now we'll try 21 = 3 x 7 (permalink).

Semiprime            | Factorisation
---------------------------------------------
21                   | 3 * 7
213                  | 3 * 71
2138                 | 2 * 1069
21381                | 3 * 7127
213811               | 13 * 16447
2138111              | 61 * 35051
21381117             | 3 * 7127039

Let's try a larger number like 28293.

Semiprime            | Factorisation
---------------------------------------------
28293                | 3 * 9431
282937               | 31 * 9127
2829371              | 1571 * 1801
28293711             | 3 * 9431237
282937111            | 15959 * 17729
2829371119           | 331 * 8547949

Clearly the chains are shorter when creating right truncatable semiprimes.

Left Truncatable Semiprimes

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 * 158176747867593607

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

However, when we input 21 = 3 x 7 the program times out. As Gemini says:

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

By contrast, the semiprime 25 leads to a dead end.

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

The downside of course is that the longest possible chain is not uncovered. Here is the result for 14 when the program is now run (permalink).

Semiprime            | Factorisation
---------------------------------------------
14                   | 2 * 7
214                  | 2 * 107
1214                 | 2 * 607
21214                | 2 * 10607
121214               | 2 * 60607

Here is the result for 33 (permalink):

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

The program works quite well for larger semiprimes too. Take 28293 as an example (permalink):

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.

Truncatable Primes Revisited

The following information is true:

The largest left-truncatable prime in base 10 is the 24-digit number:$$357,686,312,646,216,567,629,137$$A left-truncatable prime is a prime number that contains no zeros and remains prime every time you successively strip away its leading (leftmost) digit. 

However, the same information presented visually where it has a lot more impact.

The largest right truncatable number (73939133) is far shorter because there is the constraint that the right-most digit can only be 1, 3, 7 or 9. A similar inverted pyramid will look like this. Note that 7 is the final prime left as was the case with the right truncatable record holder.

73939133

7393913

739391

73939

7393

739

73

7

If we start with the digit 3, the only other possible choice, and build the longest possible chain of left truncatable primes we end up with the following 20 primes (compared to 24 when we started with the digit 7 - permalink):

3

83

883

6883

76883

676883

6676883

36676883

536676883

3536676883

13536676883

213536676883

7213536676883

57213536676883

957213536676883

4957213536676883

84957213536676883

484957213536676883

6484957213536676883

36484957213536676883

Creating a chain of right-truncatable primes gives us eight primes just as it did when starting with the digit 7 (permalink):

3

37

373

3733

37337

373379

3733799

37337999

We could also start with 2 and in that case we get the following right-truncatable primes:

2

29

293

2939

29399

293999

2939999

29399999

Harshad Numbers

Today I turned 24786 days old and one of the occurrences of this number in the OEIS was in A097569: right-truncatable Harshad numbers (zeros not permitted). Of course, I needed to ask myself the inevitable question: what is a Harshad number? Here is what Wikipedia had to say about it:

In recreational mathematics, a harshad number (or Niven number) in a given number base, is an integer that is divisible by the sum of its digits when written in that base. Harshad numbers in base \(\displaystyle n\) are also known as \(\displaystyle n\)-harshad (or \(\displaystyle n\)-Niven) numbers. Harshad numbers were defined by D. R. Kaprekar, a mathematician from India. The word "harshad" comes from the Sanskrit harṣa (joy) + da (give), meaning joy-giver. The term “Niven number” arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977. 

Stated mathematically, let \(\displaystyle X\) be a positive integer with \(\displaystyle m\) digits when written in base \(\displaystyle n\), and let the digits be \(\displaystyle a_{i}\) ( \(\displaystyle i\) = 0, 1, ..., \(\displaystyle m\) − 1). (It follows that \(\displaystyle a_{i}\) must be either zero or a positive integer up to \(\displaystyle n\) − 1.) \(\displaystyle X\) can be expressed as \[\displaystyle X=\sum _{i=0}^{m-1}a_{i}n^{i}\]
If there exists an integer \(\displaystyle A\) such that the following holds, then \(\displaystyle X\) is a harshad number in base \(\displaystyle n\): \[\displaystyle X=A\sum _{i=0}^{m-1}a_{i}\] A number which is a harshad number in every number base is called an all-harshad number, or an all-Niven number. There are only four all-harshad numbers: 1, 2, 4, and 6 (The number 12 is a harshad number in all bases except octal).

So, getting back to 24786, it can be seen that it is a Harshad number because 2+4+7+8+6 = 27 and 24786/27 = 918. Truncating the last digit on the right gives 2478, so that 2+4+7+8 = 21 and 2478/21 = 118. Truncating again gives 247, so that 2+4+7 = 13 and 247/13 = 19. Truncating again gives 24, so that 2+4=6 and 24/6=4. Finally, 2 itself is of course a Harshad number.

Furthermore, it is asserted in the OEIS entry that 24786 is the final such number in the sequence of right-truncatable Harshad numbers. The full sequence is then given by:

1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18, 21, 24, 27, 36, 42, 45, 48, 54, 63, 72, 81, 84, 126, 216, 243, 247, 364, 423, 481, 486, 846, 2478, 8463, 24786