Recurring Digital Invariant Variant (RDIV) Algorithm

Let's consider the following algorithm (formally called the Recurring Digital Invariant Variant or RDIV algorithm - see this link for an explanation of the name):

• choose a number \(n\)
• let \(k\) be the number of digits in \(n\)
• raise each digit of \(n\) to the \(k\)-th power and add the results
• call the new number \(n\) and repeat

Let's use \(n=14\) as an example:

• \(14 \rightarrow 1^2 + 4^2 = 17\)
• \(17 \rightarrow 1^2 + 7^2 = 50\)
• \(50 \rightarrow 5^2 + 0^2 = 25\)
• \(25 \rightarrow 2^2 + 5^2 = 29\)
• \(29 \rightarrow 2^2 + 9^2 = 85\)
• \(85 \rightarrow 8^2 + 5^2 = 89\)
• \(89 \rightarrow 8^2 + 9^2 = 145\)
• \(145 \rightarrow 1^3 + 4^3 + 5^3 = 190\)
• \(190 \rightarrow 1^3 + 9^3 + 0^3 = 730\)
• \(730 \rightarrow 7^3 + 3^3 + 0^3 = 370\)
• \(370 \rightarrow 3^3 + 7^3 + 0^3 = 370\) 

370 is a narcissistic number as explained in my post Narcissistic, D-Powerfull and Friedman Numbers. The trajectory of any number under this algorithm will either end with a narcissistic number (as was the case with 14) or it will enter a loop (as is the case with 28218). The latter has the following trajectory (permalink):

==================================================

RDIV TRAJECTORY ANALYSIS FOR INPUT: 28218

==================================================

Full Trajectory Visited:

28218, 65601, 18678, 90120, 59082, 94974, 136953, 595181, 824837, 646826, 406272, 168529, 855931, 825565, 355739, 681798, 1220035, 80569, 102718, 379859, 1459029, 9660576, 6524445, 485466, 379273, 768261, 473170, 240124, 8321, 4194, 7074, 5058, 5346, 2258, 4753, 3363, 1539, 7268, 7809, 13058, 36137, 25070, 19964, 126899, 1371747, 2489202, 6896889, 16417266, 10869443, 61641187, 25966788, 86116067, 27580867, 47154531, 6683686, 5316235, 440689, 848433, 533938, 811397, 911965, 1125165, 436317, 169860, 886898, 1626673, 1665667, 2021413, 18829, 124618, 312962, 578955, 958109, 1340652, 376761, 329340, 537059, 681069 -> [loops back to 886898]

Loop Entry Point:   886898 (encountered at step 65)

Pre-period Length:  64 step(s) before entering cycle

Cycle Length:       14 distinct number(s) in the loop

Canonical Cycle:    18829, 124618, 312962, 578955, 958109, 1340652, 376761, 329340, 537059, 681069, 886898, 1626673, 1665667, 2021413

==================================================

Figure 1 shows a graph of its trajectory:

Figure 1: permalink

I've incorporated this algorithm into my daily number analysis.

Zeroless Tetranacci Numbers

In a post titled, Sequences Formed By Removing Zeros, from January 2023,  I wrote that "It's interesting to consider what happens to a sequence if a certain rule is applied but with the stipulation that any zeros arising must be removed". In that post I looked at the zeroless Fibonacci sequence that falls into a repeating loop with a confirmed period of 912. 

The zeroless Tribonacci sequence falls into a much larger repeating loop with a confirmed period of 300,056,874. It reaches this cycle at index 208,666,297. However, it is not known whether the zeroless Tetranacci sequences cycles or not but, if it does, then \(s+p > 10^{10}\) where \(s\) and \(p\) are the starting index and period of the cycle, respectively.

 

 A371916: zeroless analog of tetranacci numbers.

The initial members are:

1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673, 1297, 25, 2344, 4339, 85, 6793, 13561, 24778, 45217, 9349, 9295, 88639, 1525, 1888, 11347, 13399, 28159, 54793, 17698, 11449, 11299, 95239, 135685, 253672, 495895, 98491, 983743, 183181, 176131, 1441546, 278461, 279319, 2175457

Figure 1 shows a plot of the first 100 terms:

Figure 1: permalink

Like the zeroless Fibonacci and Tribonacci sequences the ratio between successive terms of the zeroless Tetranacci sequence never approaches a limit. With no suppression of zeros, the following are the convergences:

• Fibonacci: $\phi = \frac{1+\sqrt{5}}{2} \text{ which is }\approx 1.61803$
• Tribonacci: the real root of $x^3 - x^2 - x - 1 = 0 \text{ which is } \approx 1.83929$
• Tetranacci: the real root of $x^4 - x^3 - x^2 - x - 1 = 0 \text{ which is }\approx 1.92756$

Additive Fibonacci-like Numbers

Consider all two digit numbers from 10 to 99 and use these as the seed digits that will generate a third digit by ADDITION of the two digits and by then finding the DIGITAL ROOT of the resultant sum. Here are the 90 starting numbers.

10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

These 90 two digit numbers will generate another 90 three digit numbers. These are:

101, 112, 123, 134, 145, 156, 167, 178, 189, 191, 202, 213, 224, 235, 246, 257, 268, 279, 281, 292, 303, 314, 325, 336, 347, 358, 369, 371, 382, 393, 404, 415, 426, 437, 448, 459, 461, 472, 483, 494, 505, 516, 527, 538, 549, 551, 562, 573, 584, 595, 606, 617, 628, 639, 641, 652, 663, 674, 685, 696, 707, 718, 729, 731, 742, 753, 764, 775, 786, 797, 808, 819, 821, 832, 843, 854, 865, 876, 887, 898, 909, 911, 922, 933, 944, 955, 966, 977, 988, 999

These in turn will produce 90 four digit numbers. These are:

1011, 1123, 1235, 1347, 1459, 1562, 1674, 1786, 1898, 1911, 2022, 2134, 2246, 2358, 2461, 2573, 2685, 2797, 2819, 2922, 3033, 3145, 3257, 3369, 3472, 3584, 3696, 3718, 3821, 3933, 4044, 4156, 4268, 4371, 4483, 4595, 4617, 4729, 4832, 4944, 5055, 5167, 5279, 5382, 5494, 5516, 5628, 5731, 5843, 5955, 6066, 6178, 6281, 6393, 6415, 6527, 6639, 6742, 6854, 6966, 7077, 7189, 7292, 7314, 7426, 7538, 7641, 7753, 7865, 7977, 8088, 8191, 8213, 8325, 8437, 8549, 8652, 8764, 8876, 8988, 9099, 9112, 9224, 9336, 9448, 9551, 9663, 9775, 9887, 9999

These in turn will produce 90 five digit numbers. These are:

10112, 11235, 12358, 13472, 14595, 15628, 16742, 17865, 18988, 19112, 20224, 21347, 22461, 23584, 24617, 25731, 26854, 27977, 28191, 29224, 30336, 31459, 32573, 33696, 34729, 35843, 36966, 37189, 38213, 39336, 40448, 41562, 42685, 43718, 44832, 45955, 46178, 47292, 48325, 49448, 50551, 51674, 52797, 53821, 54944, 55167, 56281, 57314, 58437, 59551, 60663, 61786, 62819, 63933, 64156, 65279, 66393, 67426, 68549, 69663, 70775, 71898, 72922, 73145, 74268, 75382, 76415, 77538, 78652, 79775, 80887, 81911, 82134, 83257, 84371, 85494, 86527, 87641, 88764, 89887, 90999, 91123, 92246, 93369, 94483, 95516, 96639, 97753, 98876, 99999

Forgetting about the original two digit numbers, let's group all the three, four and five digits number together so that we have 270 numbers. These are:

101, 112, 123, 134, 145, 156, 167, 178, 189, 191, 202, 213, 224, 235, 246, 257, 268, 279, 281, 292, 303, 314, 325, 336, 347, 358, 369, 371, 382, 393, 404, 415, 426, 437, 448, 459, 461, 472, 483, 494, 505, 516, 527, 538, 549, 551, 562, 573, 584, 595, 606, 617, 628, 639, 641, 652, 663, 674, 685, 696, 707, 718, 729, 731, 742, 753, 764, 775, 786, 797, 808, 819, 821, 832, 843, 854, 865, 876, 887, 898, 909, 911, 922, 933, 944, 955, 966, 977, 988, 999, 1011, 1123, 1235, 1347, 1459, 1562, 1674, 1786, 1898, 1911, 2022, 2134, 2246, 2358, 2461, 2573, 2685, 2797, 2819, 2922, 3033, 3145, 3257, 3369, 3472, 3584, 3696, 3718, 3821, 3933, 4044, 4156, 4268, 4371, 4483, 4595, 4617, 4729, 4832, 4944, 5055, 5167, 5279, 5382, 5494, 5516, 5628, 5731, 5843, 5955, 6066, 6178, 6281, 6393, 6415, 6527, 6639, 6742, 6854, 6966, 7077, 7189, 7292, 7314, 7426, 7538, 7641, 7753, 7865, 7977, 8088, 8191, 8213, 8325, 8437, 8549, 8652, 8764, 8876, 8988, 9099, 9112, 9224, 9336, 9448, 9551, 9663, 9775, 9887, 9999, 10112, 11235, 12358, 13472, 14595, 15628, 16742, 17865, 18988, 19112, 20224, 21347, 22461, 23584, 24617, 25731, 26854, 27977, 28191, 29224, 30336, 31459, 32573, 33696, 34729, 35843, 36966, 37189, 38213, 39336, 40448, 41562, 42685, 43718, 44832, 45955, 46178, 47292, 48325, 49448, 50551, 51674, 52797, 53821, 54944, 55167, 56281, 57314, 58437, 59551, 60663, 61786, 62819, 63933, 64156, 65279, 66393, 67426, 68549, 69663, 70775, 71898, 72922, 73145, 74268, 75382, 76415, 77538, 78652, 79775, 80887, 81911, 82134, 83257, 84371, 85494, 86527, 87641, 88764, 89887, 90999, 91123, 92246, 93369, 94483, 95516, 96639, 97753, 98876, 99999

Viewed as a Fibonacci-like sequence, the sequence of digits will eventually cycle. Take 27977 as an example. The progression is:$$2, 7, 9, 7, 7, 5, 3, 8, 2, 1, 3, 4, 7, 2, 9, 2, 2, 4, 6, 1, 7, 8, 6, 5, 2, 7, 9, 7, 7, \dots $$An alternative to this progression of digits is to determine the arithmetical digital root of the cumulative sum of digits and use this as the next digit. Here is a permalink that will generate this sequence of 270 numbers. Here are the numbers:

101, 112, 123, 134, 145, 156, 167, 178, 189, 191, 202, 213, 224, 235, 246, 257, 268, 279, 281, 292, 303, 314, 325, 336, 347, 358, 369, 371, 382, 393, 404, 415, 426, 437, 448, 459, 461, 472, 483, 494, 505, 516, 527, 538, 549, 551, 562, 573, 584, 595, 606, 617, 628, 639, 641, 652, 663, 674, 685, 696, 707, 718, 729, 731, 742, 753, 764, 775, 786, 797, 808, 819, 821, 832, 843, 854, 865, 876, 887, 898, 909, 911, 922, 933, 944, 955, 966, 977, 988, 999, 1012, 1124, 1236, 1348, 1451, 1563, 1675, 1787, 1899, 1912, 2024, 2136, 2248, 2351, 2463, 2575, 2687, 2799, 2812, 2924, 3036, 3148, 3251, 3363, 3475, 3587, 3699, 3712, 3824, 3936, 4048, 4151, 4263, 4375, 4487, 4599, 4612, 4724, 4836, 4948, 5051, 5163, 5275, 5387, 5499, 5512, 5624, 5736, 5848, 5951, 6063, 6175, 6287, 6399, 6412, 6524, 6636, 6748, 6851, 6963, 7075, 7187, 7299, 7312, 7424, 7536, 7648, 7751, 7863, 7975, 8087, 8199, 8212, 8324, 8436, 8548, 8651, 8763, 8875, 8987, 9099, 9112, 9224, 9336, 9448, 9551, 9663, 9775, 9887, 9999, 10124, 11248, 12363, 13487, 14512, 15636, 16751, 17875, 18999, 19124, 20248, 21363, 22487, 23512, 24636, 25751, 26875, 27999, 28124, 29248, 30363, 31487, 32512, 33636, 34751, 35875, 36999, 37124, 38248, 39363, 40487, 41512, 42636, 43751, 44875, 45999, 46124, 47248, 48363, 49487, 50512, 51636, 52751, 53875, 54999, 55124, 56248, 57363, 58487, 59512, 60636, 61751, 62875, 63999, 64124, 65248, 66363, 67487, 68512, 69636, 70751, 71875, 72999, 73124, 74248, 75363, 76487, 77512, 78636, 79751, 80875, 81999, 82124, 83248, 84363, 85487, 86512, 87636, 88751, 89875, 90999, 91124, 92248, 93363, 94487, 95512, 96636, 97751, 98875, 99999

Let's take 26875 as an example. We begin with 26 as our seed number and then proceed thus: $$ \begin{align} 26 \text{ has digit sum } 8 &\rightarrow 268 \\ 268 \text{ has digit sum } 16 \equiv 7 &\rightarrow 2687 \\ 2687 \text{ has digit sum } 23 \equiv 5 &\rightarrow 26875 \end{align} $$The three digit numbers are the same as earlier but the differences arise in the four and five digit numbers. Let's compare the previous cumulative results with the seed number 26 again but using the earlier two digit approach:$$ \begin{align} 26 \text{ has digit sum } 8 &\rightarrow 268 \\ 68 \text{ has digit sum } 14 \equiv 5 &\rightarrow 2685 \\ 85 \text{ has digit sum } 13 \equiv 4 &\rightarrow 26854 \end{align} $$

Subtractive Fibonacci-like Numbers

Consider all two digit numbers from 10 to 99 and use these as the seed digits that will generate a third number NOT by ADDITION of the two digits but by SUBTRACTION, subtracting the smaller digit from the larger when they are different. This ensures that the result is always positive or zero. Taking the absolute value of the result is another way to regard it. Here are the 90 numbers.

10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

These 90 two digit numbers will generate another 90 three digit numbers. These are:

101, 110, 121, 132, 143, 154, 165, 176, 187, 198, 202, 211, 220, 231, 242, 253, 264, 275, 286, 297, 303, 312, 321, 330, 341, 352, 363, 374, 385, 396, 404, 413, 422, 431, 440, 451, 462, 473, 484, 495, 505, 514, 523, 532, 541, 550, 561, 572, 583, 594, 606, 615, 624, 633, 642, 651, 660, 671, 682, 693, 707, 716, 725, 734, 743, 752, 761, 770, 781, 792, 808, 817, 826, 835, 844, 853, 862, 871, 880, 891, 909, 918, 927, 936, 945, 954, 963, 972, 981, 990

These in turn will spawn another 90 numbers. These are:

1011, 1101, 1211, 1321, 1431, 1541, 1651, 1761, 1871, 1981, 2022, 2110, 2202, 2312, 2422, 2532, 2642, 2752, 2862, 2972, 3033, 3121, 3211, 3303, 3413, 3523, 3633, 3743, 3853, 3963, 4044, 4132, 4220, 4312, 4404, 4514, 4624, 4734, 4844, 4954, 5055, 5143, 5231, 5321, 5413, 5505, 5615, 5725, 5835, 5945, 6066, 6154, 6242, 6330, 6422, 6514, 6606, 6716, 6826, 6936, 7077, 7165, 7253, 7341, 7431, 7523, 7615, 7707, 7817, 7927, 8088, 8176, 8264, 8352, 8440, 8532, 8624, 8716, 8808, 8918, 9099, 9187, 9275, 9363, 9451, 9541, 9633, 9725, 9817, 9909

These in turn will spawn another 90 numbers. These are:

10110, 11011, 12110, 13211, 14312, 15413, 16514, 17615, 18716, 19817, 20220, 21101, 22022, 23121, 24220, 25321, 26422, 27523, 28624, 29725, 30330, 31211, 32110, 33033, 34132, 35231, 36330, 37431, 38532, 39633, 40440, 41321, 42202, 43121, 44044, 45143, 46242, 47341, 48440, 49541, 50550, 51431, 52312, 53211, 54132, 55055, 56154, 57253, 58352, 59451, 60660, 61541, 62422, 63303, 64220, 65143, 66066, 67165, 68264, 69363, 70770, 71651, 72532, 73413, 74312, 75231, 76154, 77077, 78176, 79275, 80880, 81761, 82642, 83523, 84404, 85321, 86242, 87165, 88088, 89187, 90990, 91871, 92752, 93633, 94514, 95413, 96330, 97253, 98176, 99099

Let's forget about our two digit starting numbers and consider only the resulting three, four and five digit numbers. Grouping them all together we have the following 270 member sequence:

101, 110, 121, 132, 143, 154, 165, 176, 187, 198, 202, 211, 220, 231, 242, 253, 264, 275, 286, 297, 303, 312, 321, 330, 341, 352, 363, 374, 385, 396, 404, 413, 422, 431, 440, 451, 462, 473, 484, 495, 505, 514, 523, 532, 541, 550, 561, 572, 583, 594, 606, 615, 624, 633, 642, 651, 660, 671, 682, 693, 707, 716, 725, 734, 743, 752, 761, 770, 781, 792, 808, 817, 826, 835, 844, 853, 862, 871, 880, 891, 909, 918, 927, 936, 945, 954, 963, 972, 981, 990, 1011, 1101, 1211, 1321, 1431, 1541, 1651, 1761, 1871, 1981, 2022, 2110, 2202, 2312, 2422, 2532, 2642, 2752, 2862, 2972, 3033, 3121, 3211, 3303, 3413, 3523, 3633, 3743, 3853, 3963, 4044, 4132, 4220, 4312, 4404, 4514, 4624, 4734, 4844, 4954, 5055, 5143, 5231, 5321, 5413, 5505, 5615, 5725, 5835, 5945, 6066, 6154, 6242, 6330, 6422, 6514, 6606, 6716, 6826, 6936, 7077, 7165, 7253, 7341, 7431, 7523, 7615, 7707, 7817, 7927, 8088, 8176, 8264, 8352, 8440, 8532, 8624, 8716, 8808, 8918, 9099, 9187, 9275, 9363, 9451, 9541, 9633, 9725, 9817, 9909, 10110, 11011, 12110, 13211, 14312, 15413, 16514, 17615, 18716, 19817, 20220, 21101, 22022, 23121, 24220, 25321, 26422, 27523, 28624, 29725, 30330, 31211, 32110, 33033, 34132, 35231, 36330, 37431, 38532, 39633, 40440, 41321, 42202, 43121, 44044, 45143, 46242, 47341, 48440, 49541, 50550, 51431, 52312, 53211, 54132, 55055, 56154, 57253, 58352, 59451, 60660, 61541, 62422, 63303, 64220, 65143, 66066, 67165, 68264, 69363, 70770, 71651, 72532, 73413, 74312, 75231, 76154, 77077, 78176, 79275, 80880, 81761, 82642, 83523, 84404, 85321, 86242, 87165, 88088, 89187, 90990, 91871, 92752, 93633, 94514, 95413, 96330, 97253, 98176, 99099

The sequence will continue indefinitely and what drew my attention to these types of numbers was the number associated with my diurnal age today, 27520. I noticed that it almost qualified because 7 - 2 = 5, 7 - 5 = 2 but 5 - 2 does not produce the required final digit of 3. However, in three more days it will when my diurnal age reaches 27523 days. The next number in the sequence is 28624 which is some three years away. Such numbers are certainly not frequent so they deserve to be given some attention.

Viewed as a Fibonacci-like sequence of numbers, the sequences all settle down to a repetitive \(0, n, n\) pattern where \(n\) is a digit between 1 and 9. For example, 27523 becomes:$$2, 7, 5, 2, 3, 1, 2, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, \dots$$The fact that the absolute value of the repeated subtraction of the two digits cannot produce numbers greater than 9 ensures eventual repetition. Subtraction aside, there are similar sequences to explore like adding the first two digits together to produce a third number that is not the sum of the first two, as in the Fibonacci sequence, but the DIGITAL ROOT of the number. For example:$$ \begin{align} 27 &\rightarrow 279 \\279 &\rightarrow 2797 \text{ since } 9 + 7 = 16 \rightarrow 7 \\ 2797 &\rightarrow 27977 \end{align} $$This sequence will be examined in my next post.

A Fibonacci Variant

I was happy to discover a variant of the famous Fibonacci sequence today when I began searching the OEIS for properties of the number associated with my diurnal age today: 27345. Let's look at OEIS  A321021:

A321021

a(0)=0, a(1)=1; thereafter a(\(n\)) = a(\(n\)-2)+a(\(n\)-1), keeping just the digits that appear exactly once.

This is a Fibonacci-like sequence in that the next term is formed from the sum of the two previous terms but the fact that we keep only the digits that appear exactly once in this addend makes a huge difference. After 171 terms, the sequence enters a 100 term loop shown in blue below with 27345 marked in bold (permalink):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 0, 34, 34, 68, 102, 170, 7, 1, 8, 9, 17, 26, 43, 69, 2, 71, 73, 1, 74, 75, 149, 4, 153, 157, 310, 467, 0, 467, 467, 934, 40, 974, 4, 978, 982, 1960, 94, 2054, 2148, 40, 21, 61, 82, 143, 5, 148, 153, 301, 5, 306, 3, 309, 312, 621, 9, 630, 639, 1269, 1908, 31, 13, 0, 13, 13, 26, 39, 65, 104, 169, 273, 2, 275, 2, 2, 4, 6, 10, 16, 26, 42, 68, 0, 68, 68, 136, 204, 340, 5, 345, 350, 695, 1045, 1740, 2785, 42, 87, 129, 216, 345, 561, 906, 1467, 27, 19, 46, 65, 0, 65, 65, 130, 195, 325, 520, 845, 1365, 10, 1375, 1385, 2760, 15, 25, 40, 65, 105, 170, 275, 5, 280, 285, 6, 291, 297, 5, 302, 307, 609, 916, 12, 928, 940, 16, 956, 972, 1928, 29, 1957, 1986, 94, 28, 1, 29, 30, 59, 89, 148, 237, 385, 6, 391, 397, 7, 0, 7, 7, 14, 21, 35, 56, 91, 147, 238, 385, 623, 18, 641, 659, 13, 672, 685, 1357, 4, 36, 40, 76, 6, 82, 0, 82, 82, 164, 246, 410, 5, 415, 420, 835, 12, 847, 859, 1706, 26, 1732, 1758, 3490, 5248, 73, 5321, 5394, 75, 5469, 0, 5469, 5469, 10938, 16407, \( \textbf{27345} \), 43752, 109, 43861, 43970, 731, 701, 1432, 21, 1453, 17, 1470, 1487, 2957, 0, 2957, 2957, 5914, 71, 98, 169, 267, 436, 703, 39, 742, 781, 1523, 2304, 3827, 63, 3890, 95, 3985, 48, 40, 0, 40, 40, 80, 120, 2, 1, 3, 4, 7, 0, 7, 7, 14, 21, 35, ...

Thus 27345 is a term in this 100 term loop and this qualifies it for membership in OEIS  A321022:

A321022

The 100 terms of the cycle that A321021 goes into.

As with the Fibonacci sequence, this Fibonacci-like sequence need not begin with 0 and 1 but could be a Lucas-like sequence beginning with 2 and 1:

2, 1, 3, 4, 7, 0, 7, 7, 14, 21, 35, 56, 91, 147, 238, 385, 623, 18, 641, 659, 13, 672, 685, 1357, 4, 36, 40, 76, 6, 82, 0, 82, 82, 164, 246, 410, 5, 415, 420, 835, 12, 847, 859, 1706, 26, 1732, 1758, 3490, 5248, 73, 5321, 5394, 75, 5469, 0, 5469, 5469, 10938, 16407, 27345, 43752, 109, 43861, 43970, 731, 701, 1432, 21, 1453, 17, 1470, 1487, 2957, 0, 2957, 2957, 5914, 71, 98, 169, 267, 436, 703, 39, 742, 781, 1523, 2304, 3827, 63, 3890, 95, 3985, 48, 40, 0, 40, 40, 80, 120, 2, 1, 3, 4, 7, 0, 7, 7, 14, 21, 35, 56, ...

Again we end up with the same cycle of 100 terms, it just starts a little earlier. One can also try a tribonacci approach with starting points of 0, 1 and 2. This gives a loop of almost 1000 terms (permalink) with a maximum value reached of 120487 (shown in bold red):

0, 1, 2, 3, 6, 0, 9, 15, 24, 48, 87, 159, 294, 540, 3, 837, 1380, 0, 17, 1397, 0, 0, 1397, 1397, 2794, 0, 49, 2843, 89, 2981, 5913, 93, 97, 6103, 6293, 12493, 249, 19035, 31, 935, 21, 987, 1943, 2951, 51, 95, 3097, 24, 3216, 67, 7, 3290, 64, 61, 3415, 3540, 7016, 397, 10953, 183, 5, 4, 192, 201, 397, 790, 13, 12, 815, 840, 17, 1672, 59, 1748, 3479, 5286, 53, 1, 5340, 5394, 10735, 21469, 37598, 69802, 1269, 1089, 72160, 74518, 146, 1682, 734, 56, 47, 837, 940, 1824, 3601, 35, 5460, 6, 1, 5467, 57, 2, 26, 85, 3, 4, 92, 0, 96, 1, 97, 194, 9, 3, 206, 218, 427, 851, 1496, 24, 2371, 3891, 28, 6290, 129, 67, 48, 2, 7, 57, 0, 64, 2, 0, 0, 2, 2, 4, 8, 14, 26, 48, 0, 74, 1, 75, 150, 6, 231, 387, 624, 14, 1025, 13, 1052, 29, 1094, 2175, 3298, 57, 30, 85, 172, 287, 5, 6, 298, 309, 613, 10, 932, 1, 943, 1876, 80, 28, 1984, 9, 1, 14, 24, 39, 0, 63, 102, 165, 0, 267, 432, 6, 705, 43, 754, 1502, 0, 56, 18, 74, 148, 240, 462, 850, 12, 1324, 2186, 35, 34, 0, 69, 103, 172, 3, 278, 453, 734, 1465, 65, 64, 1594, 1723, 81, 98, 1902, 2081, 4081, 8064, 146, 9, 8219, 8374, 102, 195, 8671, 96, 8962, 129, 9187, 127, 93, 9407, 9627, 927, 6, 156, 1089, 25, 1270, 2384, 3679, 7, 67, 75, 149, 291, 1, 1, 293, 295, 589, 0, 4, 593, 597, 94, 1284, 1975, 5, 3264, 52, 21, 7, 80, 108, 195, 8, 3, 206, 217, 426, 849, 1492, 26, 2367, 35, 48, 2450, 25, 53, 58, 136, 247, 1, 384, 632, 7, 1023, 12, 1042, 20, 1074, 2136, 20, 20, 2176, 16, 1, 2193, 10, 4, 7, 21, 32, 60, 3, 95, 158, 256, 509, 923, 16, 18, 957, 1, 976, 1934, 29, 23, 1986, 2038, 7, 4031, 7, 5, 3, 15, 23, 41, 79, 143, 263, 485, 891, 1639, 3015, 4, 4658, 6, 48, 4712, 47, 4807, 95, 0, 4902, 47, 0, 0, 47, 47, 94, 1, 142, 237, 380, 759, 1376, 21, 2156, 0, 21, 21, 42, 84, 147, 273, 504, 924, 70, 1498, 49, 67, 64, 180, 3, 247, 430, 680, 1357, 2467, 50, 3874, 6391, 35, 13, 6439, 6487, 123, 13049, 165, 17, 2, 184, 203, 389, 6, 598, 3, 607, 1208, 0, 85, 1293, 1378, 2756, 5427, 9561, 1, 148, 9710, 85, 43, 93, 1, 137, 231, 369, 3, 603, 975, 58, 13, 1046, 7, 10, 1063, 18, 9, 19, 46, 74, 139, 259, 472, 870, 60, 1402, 0, 1462, 2864, 4326, 8652, 15842, 0, 29, 587, 1, 617, 1205, 1823, 3645, 73, 41, 3759, 87, 37, 0, 124, 6, 130, 260, 396, 786, 12, 94, 892, 8, 4, 904, 916, 1824, 36, 26, 16, 78, 120, 214, 412, 746, 1372, 2530, 68, 3970, 58, 4096, 8124, 178, 12398, 27, 12603, 508, 8, 39, 0, 47, 86, 1, 134, 1, 136, 271, 408, 815, 19, 14, 4, 37, 0, 41, 78, 9, 128, 215, 352, 695, 16, 1063, 14, 1093, 2170, 32, 3295, 5497, 24, 16, 37, 0, 53, 90, 143, 286, 519, 948, 1753, 30, 2731, 51, 81, 2863, 25, 26, 2914, 2965, 90, 56, 3, 149, 208, 360, 1, 569, 930, 15, 54, 0, 69, 123, 192, 384, 6, 582, 972, 1560, 34, 25, 69, 128, 0, 197, 325, 5, 527, 857, 1389, 23, 69, 48, 140, 257, 5, 402, 4, 4, 410, 418, 832, 10, 1260, 10, 1280, 20, 30, 10, 60, 1, 71, 132, 204, 407, 743, 1354, 2504, 4601, 8459, 164, 134, 85, 8, 7, 1, 16, 24, 41, 81, 146, 268, 495, 0, 763, 1258, 1, 0, 1259, 1260, 2519, 5038, 17, 54, 5109, 5180, 104, 109, 59, 7, 175, 241, 423, 839, 1503, 2765, 5107, 9375, 124, 140, 63, 327, 530, 920, 1, 45, 9, 0, 54, 63, 7, 124, 194, 325, 643, 62, 13, 718, 793, 1524, 5, 3, 1532, 1540, 3075, 6147, 10762, 184, 17093, 28039, 45316, 908, 74263, 120487, 1968, 9678, 2, 648, 10328, 10978, 21954, 43260, 76192, 6, 9458, 8, 9472, 193, 9673, 198, 164, 135, 497, 796, 1428, 71, 95, 1594, 1760, 39, 9, 10, 58, 0, 68, 126, 194, 3, 2, 1, 6, 9, 16, 31, 56, 103, 190, 349, 642, 8, 0, 650, 658, 1308, 21, 1987, 16, 4, 27, 47, 78, 152, 2, 3, 157, 162, 3, 3, 168, 174, 345, 687, 1206, 38, 93, 17, 148, 258, 423, 829, 50, 1302, 28, 1380, 2710, 48, 4138, 89, 4275, 8502, 128, 12905, 213, 13246, 234, 169, 13649, 14052, 280, 27981, 421, 6, 240, 7, 253, 5, 265, 523, 793, 58, 1374, 5, 1437, 2816, 4258, 85, 7159, 502, 46, 0, 548, 594, 42, 84, 720, 846, 1650, 3216, 5712, 10578, 19506, 35796, 650, 92, 658, 14, 764, 1436, 14, 14, 16, 0, 30, 46, 76, 152, 274, 502, 928, 1704, 14, 24, 1742, 1780, 3546, 7068, 12394, 238, 197, 189, 624, 0, 813, 1437, 50, 23, 50, 123, 196, 369, 6, 571, 946, 1523, 34, 2503, 46, 2583, 5132, 61, 6, 51, 8, 65, 124, 197, 386, 0, 583, 6, 589, 78, 673, 1340, 2091, 10, 31, 13, 54, 98, 165, 317, 580, 1062, 15, 1657, 2734, 6, 4397, 13, 16, 26, 0, 42, 68, 0, 0, 68, 68, 136, 7, 2, 145, 154, 301, 6, 461, 768, 1235, 26, 9, 1270, 1305, 2584, 19, 3908, 65, 32, 45, 142, 219, 406, 6, 631, 1043, 1680, 54, 2, 1736, 1792, 50, 3578, 5420, 9048, 18046, 32514, 59608, 68, 210, 596, 874, 1680, 3150, 5704, 10534, 193, 643, 370, 1206, 19, 19, 12, 50, 81, 143, 274, 498, 915, 1687, 31, 26, 17, 74, 7, 98, 179, 284, 561, 1024, 1869, 35, 98, 0, 1, 0, 1, 2, 3, ...

The Game of Life

I've mentioned the mathematician John Conway in three posts to this blog. The first was the Look and Say Sequence on February 10th 2017, the second was the RATS Sequence on September 26th 2020 and the third was the Free Fibonacci Sequences on July 18th 2021.

John Conway: 1937 - 2020
MacTutor Biography

I've known about his Game of Life for quite some time now but had avoided delving into it. However, yesterday I downloaded an iOS app that allows one to play around with it and this kindled an interest to find out more. Here is some information about the game together with its rules taken from Wikipedia:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if by underpopulation.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Figures 1, 2 and 3 show examples of commonly occurring patterns that occur during the game:

Figure 1: Loaf
Example of a still life

Figure 2: Blinker
Example of an Oscillator

Figure 3: Glider
Example of a Spaceship

The Pulsar is the most common period-3 oscillator as shown in Figure 4.

Figure 4: Pulsar
The most common
Period-3 oscillator

The Wikipedia comments go on to say:

The pulsar is the most common period-3 oscillator. The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist, and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions. Patterns which evolve for long periods before stabilizing are called Methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that eventually disappears, rather than stabilizing, after 130 generations, which is conjectured to be maximal for starting patterns with seven or fewer cells. Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.

Figure 5: R-Pentomino
The first discovered Methuselah

Of course, I've encountered numerous references to the Game of Life in the OEIS over the years but have uniformly ignored them. OEIS A019473 is one example.

A019473

Number of stable \(n\)-celled patterns ("still lifes") in Conway's Game of Life, up to rotation and reflection.

The initial members of the sequence are: 0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, 3286, 7773, 19044, 45759, 112243 (beginning with \(n\)=1).

Figure 1 shows the Loaf, one of the four 7-celled stable patterns. OEIS A089520 is another such sequence:

A089520

In Conway's Game of Life, the number of steps it takes for an \(n \times n\) square, in which all the cells are in the "on" state, to die out or start to cycle, or -1 if there is no cycle.

The initial members are:

1, 0, 5, 4, 11, 5, 5, 6, 16, 17, 32, 9, 18, 9, 22, 11, 33, 17, 20, 12, 26, 13, 48, 15, 46, 26, 295, 45, 154, 38, 62, 309, 38, 87, 78, 53, 96, 150, 641, 69, 82, 265, 216, 70, 70, 70, 120, 401, 107, 78, 70, 351, 318, 109, 297, 95, 122, -1, -1, 85, 232, 294, 127 (beginning with \(n\)=1).

The 1 x 1 square disappears in one step but the 2 x 2 square (called the Block) is stable and an example of a still life. The 3 x 3 square takes five steps to turn into four blinkers (one of which is shown in Figure 2). The 4 x 4 square takes four steps to disappear and so on. The OEIS comments for this sequence state that:

The -1 terms for \(n\) = 58, 59, 80, 92, 95, 96, 98, 99, 100 correspond to starting \(n \times n \) squares that produce 8 gliders (16 for \(n\) = 99) that go off to infinity, hence never reaching a cycle.

Here is a link to an interesting article in Quanta Magazine about the latest news regarding the Game of Life. Here is an excerpt:

Throughout the 1970s, mathematicians and hobbyists filled in the other short periods and found a smattering of longer ones. Eventually, mathematicians discovered a systematic way to build long-period oscillators. But oscillators with periods between 15 and 43 proved tough to find. “People have been trying to figure out the middle for years,” said Maia Karpovich, a graduate student at the University of Maryland. Filling in the gaps forced researchers to dream up a slew of new techniques that pushed the boundaries of what was thought possible with cellular automata, as mathematicians call evolving grids like Life.

Now Karpovich and six co-authors have announced in a December preprint that they have found the last two missing periods: 19 and 41. With those gaps filled, Life is now known to be “omniperiodic” — name a positive integer, and there exists a pattern that repeats itself after that many steps.

Sequences Formed By Removing Zeros

It's interesting to consider what happens to a sequence if a certain rule is applied but with the stipulation that any zeros arising must be removed. If we start with 1, double it and then double the result and continue this process, we end up with an infinite sequence:

1, 2, 4, 6, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, ...

But what happens once any zeros that arise are removed? Well, nothing until 1024 is reached and it becomes 124, then 248, 496 etc. It turns out that the sequence enters a loop (marked in blue below) that has a period of 36. The minimum value within the loop is 28714 and the largest is 11,772,544. The maximum value reached overall is 765,257,552.

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 253952, 5794, 11588, 23176, 46352, 9274, 18548, 3796, 7592, 15184, 3368, 6736, 13472, 26944, 53888, 17776, 35552, 7114, 14228, 28456, 56912, 113824, 227648, 455296, 91592, 183184, 366368, 732736, 1465472, 293944, 587888, 1175776, 2351552, 47314, 94628, 189256, 378512, 75724, 151448, 32896, 65792, 131584, 263168, 526336, 152672, 35344, 7688, 15376, 3752, 754, 158, 316, 632, 1264, 2528, 556, 1112, 2224, 4448, 8896, 17792, 35584, 71168, 142336, 284672, 569344, 1138688, 2277376, 4554752, 91954, 18398, 36796, 73592, 147184, 294368, 588736, 1177472, 2354944, 479888, 959776, 1919552, 383914, 767828, 1535656, 371312, 742624, 1485248, 297496, 594992, 1189984, 2379968, 4759936, 9519872, 1939744, 3879488, 7758976, 15517952, 313594, 627188, 1254376, 258752, 51754, 1358, 2716, 5432, 1864, 3728, 7456, 14912, 29824, 59648, 119296, 238592, 477184, 954368, 198736, 397472, 794944, 1589888, 3179776, 6359552, 1271914, 2543828, 587656, 1175312, 235624, 471248, 942496, 1884992, 3769984, 7539968, 1579936, 3159872, 6319744, 12639488, 25278976, 5557952, 1111594, 2223188, 4446376, 8892752, 1778554, 355718, 711436, 1422872, 2845744, 5691488, 11382976, 22765952, 4553194, 916388, 1832776, 3665552, 733114, 1466228, 2932456, 5864912, 11729824, 23459648, 46919296, 93838592, 187677184, 375354368, 7578736, 15157472, 3314944, 6629888, 13259776, 26519552, 533914, 167828, 335656, 671312, 1342624, 2685248, 537496, 174992, 349984, 699968, 1399936, 2799872, 5599744, 11199488, 22398976, 44797952, 8959594, 17919188, 35838376, 71676752, 14335354, 286778, 573556, 1147112, 2294224, 4588448, 9176896, 18353792, 3677584, 7355168, 1471336, 2942672, 5885344, 1177688, 2355376, 471752, 94354, 18878, 37756, 75512, 15124, 3248, 6496, 12992, 25984, 51968, 13936, 27872, 55744, 111488, 222976, 445952, 89194, 178388, 356776, 713552, 142714, 285428, 57856, 115712, 231424, 462848, 925696, 1851392, 372784, 745568, 1491136, 2982272, 5964544, 1192988, 2385976, 4771952, 954394, 198788, 397576, 795152, 15934, 31868, 63736, 127472, 254944, 59888, 119776, 239552, 47914, 95828, 191656, 383312, 766624, 1533248, 366496, 732992, 1465984, 2931968, 5863936, 11727872, 23455744, 46911488, 93822976, 187645952, 37529194, 7558388, 15116776, 3233552, 646714, 1293428, 2586856, 5173712, 1347424, 2694848, 5389696, 1779392, 3558784, 7117568, 14235136, 2847272, 5694544, 1138988, 2277976, 4555952, 911194, 1822388, 3644776, 7289552, 1457914, 2915828, 5831656, 11663312, 23326624, 46653248, 9336496, 18672992, 37345984, 74691968, 149383936, 298767872, 597535744, 119571488, 239142976, 478285952, 95657194, 191314388, 382628776, 765257552, 15351514, 37328, 74656, 149312, 298624, 597248, 1194496, 2388992, 4777984, 9555968, 19111936, 38223872, 76447744, 152895488, 3579976, 7159952, 1431994, 2863988, 5727976, 11455952, 2291194, 4582388, 9164776, 18329552, 3665914, 7331828, 14663656, 29327312, 58654624, 11739248, 23478496, 46956992, 93913984, 187827968, 375655936, 751311872, 152623744, 35247488, 7494976, 14989952, 2997994, 5995988, 11991976, 23983952, 4796794, 9593588, 19187176, 38374352, 7674874, 15349748, 3699496, 7398992, 14797984, 29595968, 59191936, 118383872, 236767744, 473535488, 9477976, 18955952, 3791194, 7582388, 15164776, 3329552, 665914, 1331828, 2663656, 5327312, 1654624, 339248, 678496, 1356992, 2713984, 5427968, 1855936, 3711872, 7423744, 14847488, 29694976, 59389952, 11877994, 23755988, 47511976, 9523952, 194794, 389588, 779176, 1558352, 311674, 623348, 1246696, 2493392, 4986784, 9973568, 19947136, 39894272, 79788544, 15957788, 31915576, 63831152, 12766234, 25532468, 5164936, 1329872, 2659744, 5319488, 1638976, 3277952, 655594, 1311188, 2622376, 5244752, 148954, 29798, 59596, 119192, 238384, 476768, 953536, 19772, 39544, 7988, 15976, 31952, 6394, 12788, 25576, 51152, 1234, 2468, 4936, 9872, 19744, 39488, 78976, 157952, 31594, 63188, 126376, 252752, 5554, 1118, 2236, 4472, 8944, 17888, 35776, 71552, 14314, 28628, 57256, 114512, 22924, 45848, 91696, 183392, 366784, 733568, 1467136, 2934272, 5868544, 1173788, 2347576, 4695152, 93934, 187868, 375736, 751472, 152944, 35888, 71776, 143552, 28714, 57428, 114856, 229712, 459424, 918848, 1837696, 3675392, 735784, 1471568, 2943136, 5886272, 11772544, 2354588, 479176, 958352, 191674, 383348, 766696, 1533392, 366784

This sequence is in fact OEIS  A242350:

A242350

Multiply a(n-1) by 2 and drop all 0's where a(0)=1.

Figure 1 shows a graph of the sequence with a logarithmic scale for the y axis.

Figure 1: permalink

It doesn't matter what the starting point, the sequence will cycle sooner or later. If the starting point is 3 then the cycle begins with 479712 at the 207th term and returns to this number on the 387th term. The largest value reached overall is 582,269,952. Figure 2 shows the graph of the sequence using a logarithmic scale for the y axis.

Figure 2: permalink

The pattern in Figure 2 is very similar to that in Figure 1. The removal of zeroes, when they occur, brings the size of the number down, often drastically. The logarithmic scale gives a false sense of the magnitude of these ups and downs. Figure 3 shows the data without the logarithmic scale for the starting value of 3.

Figure 3: permalink

The same thing can be done with the Fibonacci sequence and again a cycle is reached. The 26th term is 7841 and this number is reached again at the 434th term. I won't list all the terms, just those up to 7841 (permalink):

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 61, 438, 499, 937, 1436, 2373, 389, 2762, 3151, 5913, 964, 6877, 7841, ...

Notice how 233 + 377 = 610 --> 61 and 3151 + 5913 = 9064 --> 964 in the sequence above.

These numbers form OEIS A243063:

A243063

Numbers generated by a Fibonacci-like sequence in which zeros are suppressed.

Another example is provided by OEIS A256227:

A256227

Naught-y numbers (A011540) that after removing all zeros become zeroless primes (A038618).

The initial members of the sequence (up to 1000) are (permalink):

20, 30, 50, 70, 101, 103, 107, 109, 110, 130, 170, 190, 200, 203, 209, 230, 290, 300, 301, 307, 310, 370, 401, 403, 407, 410, 430, 470, 500, 503, 509, 530, 590, 601, 607, 610, 670, 700, 701, 703, 709, 710, 730, 790, 803, 809, 830, 890, 907, 970

This sequence of course is infinite. Up to one million, there are 45304 terms or about 4.5% of the numbers in the range. That's enough for the time being.

Factorions

Figure 1

On Chris Pickover's Twitter feed, I came across the factorion, a term he uses to describe numbers of the form 145 where 1! + 4! + 5! = 145. Figure 1 shows his tweet. He defines a factorion as a natural number that equals the sum of the factorials of its digits. There are only two of these: 145 and 40585. 

Drawing on an analogy to amicable numbers, Wikipedia introduces the term amicable factorions to describe a pair of numbers in which the factorial digit sum of one number equals the other number. The two such pairs of numbers are (871, 45361) and (872, 45362). 

871 --> 45361 --> 871

872 --> 45362 --> 872

Again, in keeping with the analogy to sociable numbers, Wikipedia introduces the term sociable factorians to describe numbers that eventually return to themselves after repeated applications of the factorial sum of digits. Examples are 169, 363601 and 1454 where:

169 --> 363601 --> 1454 --> 169

These three numbers can be said to have a cycle length of three and thus amicable factorions could be considered as sociable factorions with a cycle length of 2. Similarly factorians could be viewed as sociable factorions with a cycle length of 1.

Thus factorions of whatever ilk are few and far between. The list comprises only:

• 145 factorion
• 169 sociable factorion
• 871 amicable factorion
• 872 amicable factorion
• 1454 sociable factorion
• 40585 factorion
• 45361 amicable factorion
• 45362 amicable factorion
• 363601 sociable factorion

Thus the largest factorion, 363601, has six digits. A factorion could, theoretically, have seven digits because the smallest seven digit number is 1,000,000 and the largest factorial digit sum of a seven digit number is 7 x 9! = 2,540,160. However, factorions of eight digits and beyond are not possible because the smallest eight digit number is 10,000,000 and the largest factorial digit sum of an eight digit number is 8 x 9! = 2,903,040. Let's not forget that 0! = 1 by the way.

The Wikipedia articles looks at the topic using more mathematical terminology and considers number bases other than 10 but I'll keep this post simple (and I'm feeling lazy). Here is permalink to the SageMath algorithm that generates the above list. Below I've embedded the SageMath code:

Free Fibonacci Sequences

On turning 26404 days, I couldn't help but notice the 404, a number made famous by the experience of everyone who has searched the Internet and failed to find what was being sought.

Apart from containing 404 as a subset of its digits, 26404 has some other interesting properties. Foremost amongst these is the fact that it is a member of OEIS A008892.

A008892

Aliquot sequence starting at 276.

I wrote about aliquot sequences in an eponymous post of December 20th 2017 and again, only recently, in Aliquot Sequences Revisited on June 21st 2021. 276 is the first of a sequence of numbers that are not known to be finite or periodic when the aliquot algorithm is applied. This algorithm takes as its input any integer \(n\) and returns the sum of the number's aliquot parts or proper divisors, \( \sigma(n)-n\). This output serves as the new input and the process is repeated until, most commonly, a prime number \(p\) is reached. Since \( \sigma(p)-p=1\), this means the process terminates because \( \sigma(1)=0\).

For some numbers, as far as can be determined, the process never terminates. These numbers include:

276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... and forming OEIS A131884 

In the case of 276, the sequence of numbers up to and including 26404 is:

276, 396, 696, 1104, 1872, 3770, 3790, 3050, 2716, 2772, 5964, 10164, 19628, 19684, 22876, 26404

However, this post is mainly about another interesting property of 26404 and that is its membership of OEIS A232666:

A232666

6-free Fibonacci numbers.

The OEIS comment is that:

The sequences of \(n\)-free Fibonacci numbers were suggested by John H. Conway. \(a(n)\) is the sum of the two previous terms divided by the largest possible power of 6. The sequence coincides with the Fibonacci sequence until the first multiple of 6 in the Fibonacci sequence: 144, which in this sequence is divided by 36 to produce 4.

The sequence of numbers leading to 26404 in OEIS A232666 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 4, 93, 97, 190, 287, 477, 764, 1241, 2005, 541, 2546, 3087, 5633, 8720, 14353, 23073, 37426, 60499, 97925, 26404

Here is the permalink to the generation of this sequence. There is a paper titled Free Fibonacci Sequences by Brandon Avila and Tanya Khovanova that appears in the Journal of Integer Sequences (Vol. 17 (2014), Article 14.8.5) that analyses these sequences in some detail. The authors of the paper write:

Let us denote Fibonacci numbers by \(F_k\). We define our indices such that \(F_0 = 0\) and \(F_1 = 1\). The sequence is defined by the Fibonacci recurrence: \(F_{n+1} = F_n + F_{n−1} \) (see OEIS A000045). We call an integer sequence \(a_n\) Fibonacci-like if it satisfies the Fibonacci recurrence: \(a_k = a_{k−1} + a_{k−2}\). A Fibonacci-like sequence is similar to the Fibonacci sequence, except that it starts with any two integers. The second most famous Fibonacci-like sequence is the sequence of Lucas numbers \(L_i\) that starts with \(L_0 = 2\) and \(L_1 = 1\): \(2, 1, 3, 4, 7, 11, \dots \) (see OEIS A000032). 

An \(n\)-free Fibonacci sequence starts with any two integers, \(a_1\) and \(a_2\), and is defined by the recurrence:$$a_k = \frac{a_{k−1} + a_{k−2}}{n^{ν_n(a_{k−1}+a_{k−2})}}$$where \(ν_n(x)\) is the exponent of the largest power of \(n\) that is a divisor of \(x\). To continue the tradition, we call numbers in the \(n\)-free Fibonacci sequence that starts with \(a_0 = 0\) and \(a_1 = 1\) \(n\)-free Fibonacci numbers.

The authors then go on to look at a variety of \(n\)-free Fibonacci sequences. They start with 2-free Fibonacci sequences and find that they all end in a cycle of length 1. For example, starting with \(a_0=5\) and \(a_1=10\) gives:$$5, 10, 15, 25, 5, 15, \overbrace{5}, \dots$$For 3-free Fibonacci sequences, it is suspected that all end in a cycle of \(k, k, 2k\) but it has not been proven. For example, starting with \(a_0=3\) and \(a_1=7\) gives:$$3, 7, 10, 17, 1, 2, \overbrace{1, 1, 2}, \dots$$with 1, 1, 2 repeating. Similarly, taking \(a_0=13\) and \(a_1=7\), the sequence generated is$$13, 7, 20, 1, 7, 8, 5, 13, 2, 5, 7, 4, 11, 5, 16, 7, 23, 10, 11, 7, 2, \overbrace{1, 1, 2} \dots$$ with 1, 1, 2 again repeating. The authors then go on to say that:

Consider the 4-free Fibonacci sequence starting with 0, 1. This sequence is OEIS A224382: 0, 1, 1, 2, 3, 5, 2, 7, 9, 1, 10, 11, 21, 2, 23, 25, .... It seems that this sequence grows and does not cycle. In checking many other 4-free Fibonacci sequences, we still did not find any cycles. The behaviour of 4-free sequences is completely different from the behaviour of 3-free sequences. For 3-free sequences, we expected that all of them cycle. Here, it might be possible that none of them cycles.

Let us look at the Lucas sequence mod 5: 2, 1, 3, 4, 2, 1, ... and see that no term is divisible by 5. Clearly, no term in the Lucas sequence will require that we factor out a power of 5, and the terms will grow indefinitely. Thus, the Lucas sequence is itself a 5-free Fibonacci sequence. On the other hand, it becomes quickly evident that the sequence of 5-free Fibonacci numbers: 0, 1, 1, 2, 3, 1, 4, 1, 1, 2, ... (see OEIS A214684) cycles. Some sequences cycle, and some clearly do not!

John Conway: 1937 - 2020

At the beginning of the paper, it's said that "John Horton Conway likes playing with the Fibonacci sequence. Instead of summing the two previous terms, he sums them up and then adds a twist: some additional operation." Of course, at that time, John Conway was still alive. He only died on April 11th 2020. That's a good way of thinking about the free Fibonacci sequences: Fibonacci with a twist!

I've posted frequently about Fibonacci sequences:

• The Fibonacci Number Base on July 30th 2019
• Fibonacci and Finance on April 15th 2019
• Random Fibonacci Numbers on March 9th 2020
• Dying Rabbits on June 26th 2021
• Fibonacci-like Sequences on June 10th 2020
• Finding Fibonacci and Tribonacci Seed Numbers on July 12th 2019
• Beyond Fibonacci on March 10th 2019
• Vishwanath Number on March 8th 2019
• Goldbach's Conjecture and Zeckendorf's Theorem on November 15th 2015
• Heptagonal Numbers on April 22nd 2019
• Metallic Means on March 3rd 2019

The paper contains more detailed information but the takeaway is that there is plenty of scope for further investigation of Fibonacci-like sequences with a twist. Consider this "twist" on the tribonacci sequence with initial terms of 0, 1 and 2. Each successive term is the sum of the previous three terms but (and here's the twist), if the result is a composite number, replace the term with the composite number's highest prime factor. The first terms are:

0, 1, 2, 3, 3, 2, 2, 7, 11, 5, 23, 13, 41, 11, 13, 13, 37, 7, 19, 7, 11, 37, 11, 59, 107, 59, 5, 19, 83, 107, 19, 19, 29, 67, 23, 17, 107, 7, ...

So what's going on. Well, a plot of the first 400 terms reveals the story. See Figure 1.

Figure 1: permalink

This composite number to highest prime factor "twist" is just something that popped into my head and it instantly yielded a most interesting result: a quick spike and then settling into a cycle after 255 terms. Figure 2 shows the first 1000 terms and the cycles are evident.

Figure 2: permalink

The dramatic rise and fall of the terms and their settling into an endless loop, with its own dramatic peak, are unexpected but that is what happens.

L-th Order Palindromes

It took me a little time to come to terms with what was meant exactly by an L-th order palindrome but eventually I did. It all started with an entry in the Online Encyclopaedia of Integer Sequences (OEIS) for 25487, my diurnal age on 23rd January 2019. The entry states:

A089381: L-th order palindromes with L>2.

10917, 11907, 11997, 12987, 13977, 14967, 15957, 16947, 17937, 18927, 19917, 20997, 21834, 21987, 22977, 23814, 23967, 23994, 24957, 25497, 25947, 25974, 26487, 26937, 27477, 27927, 27954, 28467, 28917, 29457, 29907, 29934, 30915

$$ P(m) = \begin{cases} m/2 & \quad \text{if } m \text{ is even}\\ m+\text{rev}(m) & \quad \text{if } m \text{ is odd}\\ \end{cases}$$ $$ \text{where rev( \(m \) ) is \(m \)'s base 10 representation reversed}$$ The following explanation is given as to what it's all about:

Let P(m) = m/2 if m is even, m + rev(m) if m is odd, where rev(m) is m's base 10 representation reversed. It is conjectured that any number k eventually cycles when P is repeatedly applied to it. If the cycle has length L, k is called an L-th order palindrome. 

It has not been proved that every number eventually cycles, but all numbers less than a million do. Palindromes of order L>2 seem to be quite rare. 10917 is the smallest and has order 7. There are 263 less than 100000 and 7745 less than 1000000. 

The first number with L>2 that doesn't end in the same cycle as 10917 is 1000353. Other cycles are known, most of them fairly small, but one has length 327 (starting with 1447132589595). 

There are an infinite number of different cycles of length 7 because one can insert any number of 9's in the middle of a number in the 7th order cycle and get a new cycle of length 7 - e.g., taking the number 13748625 from the cycle, one can produce another cycle from 13749998625.

The following example is also provided:

For most numbers, iterating P produces a cycle of length 2:
e.g., 121 -> 242 -> 121 -> ... 

The sequence for 10917 is 10917, 82818, 41409, 131823, 459954, 229977, 1009899, 10998900, 5499450, 2749725, 8029197, 15948405, {66433356, 33216678, 16608339, 109989000, 54994500, 27497250, 13748625} where the numbers in the brackets repeat. There are 7 numbers inside the brackets so 10917 is a 7th-order palindrome. 

 For 25497, the sequence generated is as follows (click here for SageMath permalink):

L-th order palindrome of cycle length 7 

104949
1054350
527175
1098900
549450
274725
802197
15934056637356
3318678
1659339
10998900
5499450
2749725
8029197
15948405
66433356
33216678
16608339
109989000
54994500
27497250
13748625
66433356

I tested the algorithm out with 1447132589595 and a cycle of length 327 is indeed produced. So the previous L-th order palindrome as well as the next two are all permutations of the same digits: 24957, 25497, 25947, 25974