Thursday, 24 January 2019

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 
SageMath code to generate the cycle length of the L-th order palindrome
104949
1054350
527175
1098900
549450
274725
802197
1593405
6637356
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

No comments:

Post a Comment