How many steps for matchstick-Lychrel numbers?

Question

The Lychrel number is famous in the recreational mathematics. The process about the Lychrel numbers reverses arrangement of the previous number.

Mimicking Lychrel numbers, I would like to devise matchstick-Lychrel numbers. The following matchstick digits are also digits when rotated 180 degrees.

Note that 0, 1, 2, 5, 8 do not change and 6 and 9 are coverted to each other. Other digits 3, 4, 7 cannot be rotated.

Given a number made by these digits, we can make a new number by rotating 180 degrees. Then, we obtain the next number by adding two numbers, i.e. the original number and the rotated number.

For example, if we are given 19,

1st step: 19 + 61 = 80
2nd step: 80 + 08 = 88
3rd step: 88 + 88 = 176.

The last number 176 cannot be rotated b/c it contains 7. So, we stop here.

Now, here is my question: Can we do this process infinitely for a number? If we can, the number shoud be called a matchstick-Lychrel number. But, I don't think such a number exists. Then, what is the maximal number of steps needed for this process?

Answer 1

I can prove by hand that we can't have more than 11 iterations. I can prove by python that we can't have more than 6 iterations, but the code is bad enough that I don't want to post it right now; perhaps if I'll post it if I get around to cleaning it up.

At most 11 iterations by hand

The first step is to keep track of the pair $(\textrm{first_digit}, \textrm{last_digit})$. After rotating and adding, the new last digit is $\textrm{Rotate(first_digit)+last_digit} \pmod{10}$. For the new first digit, it is either the first digit of $\textrm{first_digit+Rotate(last_digit)}$ or the first digit of $\textrm{first_digit+Rotate(last_digit)+1},$ depending on whether there is a carry. Here is a graph of all possible updates using only rotateable digits, created at graphonline.ru/en/.

Pairs that use the digits 3, 4, or 7 are not shown, so every leaf node could potentially update once more (depending on the digits between them). All edges are directed except for $(1,5)-(6,6)$, which is undirected because there are edges in both directions.

From this graph, the only way to get more than 7 steps is to get to the $(1,5)-(6,6)$ cycle and do enough steps. It suffices to show that we can't do more than 6 iterations from $(6,6)$.

Now we keep track of the second digit. If the original number was $6..6$, the second digit of the new number is 5 or 6. The new number is now of the form $1\{5,6\}...5$. If the tens digit is 5 or greater, the next iteration would give a number like $7...6$ which can't be rotated, so we're done in that case. Otherwise, the number is of the form $1\{5,6\}...\{0,1,2\}5$. In fact, if the tens digit is nonzero then it's either $15...15$ or $16...25$ to avoid the tens digit being unrotatable in one iteration.

If it is of the form $15...15$ then to avoid unrotatable digits it must go to $66...66$ and then $16...65$ and the next number will start with 7.

If it is of the form $16...25$ then it either goes to $68...86$ or $69...86$; if $68...86$ then the 10s digit of the next iteration will be 7, and if it's $69...86$ then the next iteration will be $16...52$ and the next number will start with 7.

Finally, if the tens digit is 0, it's either $15...05$ or $16...05$. In the former case, it will go to $6\{5,6\}...56$ and then $15...15$, which we showed earlier can only survive for 3 more iterations. In the latter case, it will go to $6\{6,7\}...96$; if the second digit is 7 we're done, and if it's 6 it will go to $16...95$ and the leading digit will be 7 in one more step.

At most 6 iterations by python

Basically what the above proof is doing is keeping track of the graph of possible updates of the leading 2 digits and the last 2 digits and showing that there's no path of length more than 11 pairs of numbers involving only rotatable digits (in fact, my code says there's no path of length of more than 9 such pairs).

But checking that a directed graph is acyclic and computing the longest path can be done in linear time using standard depth first search algorithms, so it's feasible to do this by python on the graph obtained by keeping track of the first and last 3 digits. (Aside1: It's true that we can define equivalence classes of pairs where two pairs are equivalent if we can get from one to the other by rotating opposing pairs of digits, and then say that equivalent pairs will get updated to the same pair, and it is possible to use this to shrink the graph by having nodes represent equivalence classes of pairs, and it's not hard to show that a cycle of length $k$ exists in one graph iff it exists in the other. However, the graph is small enough that we don't need to do this.) (Aside2: (We don't even need to check that the graph is acyclic, since the computation above by hand implies the graph keeping track of 2 digits on each side is acyclic, and a cycle in the graph keeping track of 3 or more digits on each side would imply a cycle in the graph keeping track of 2 digits on each side.)

So I did that, and I don't want to post my code right now, but the code said the claim is true. For now, I can provide the pairs that could possibly lead to something of length 6:

(212, 886), (215, 586), (216, 686), (218, 286), (219, 986), (282, 816), (285, 516),
(286, 616), (288, 216), (289, 916), (600, 196), (601, 096), (602, 996), (606, 296),
(611, 890), (612, 690), (618, 190), (619, 290), (651, 866), (658, 166), (660, 106),
(661, 006), (661, 810), (662, 610), (662, 906), (666, 206), (668, 110), (669, 210),
(691, 856), (698, 156), (900, 199), (901, 099), (902, 999), (906, 299), (912, 882),
(915, 582), (916, 682), (918, 282), (919, 982), (951, 869), (958, 169), (960, 109),
(961, 009), (962, 909), (966, 209), (982, 812), (985, 512), (986, 612), (988, 212),
(989, 912), (991, 859), (998, 159)

I remark that only (600, 196) and (602, 996) (and the equivalent pairs (601, 096) and (606, 296)) don't show up (either as-is or in an equivalent form) by 10 000 000 000, and they don't show up by 1 000 000 000 000 000 either.

---

Below is a bunch of data that is no longer necessary for this answer, but might be of interest to anyone interested in this problem.

I let my code run overnight to get a list up to 1 000 000 000 000 000 (I might post the code later, either here or on codereview.stackexchange; if I do the latter then I'll link it here).

To make this answer a reasonable length (and also to speed up the code), say that two numbers are equivalent if we can get from one to the other by rotating some pair of opposing digits (eg 6119890 <-> 6116890 and 61116890 <-> 66191810). Then, within an equivalence class, I will only write the smallest number to represent the whole equivalence class.

We already know the following numbers:

21586, 6116890, 61116890, 61205690, 212286886, 215286586

Here are the new numbers up to 100 000 000 000 000:

2126059886, 2156059586, 2160299686, 21212098886, 21512098586, 21600819686, 21602099686,
21602599686, 61110066890, 61110086890, 61161686890, 61200155690, 61200685690, 61202695690,
65150609866, 65151599866, 65152869866, 212120098886, 212220966886, 212221866886, 215120098586,
215220966586, 215221866586, 216001919686, 611100066890, 611112696890, 611611686890, 611612866890,
611615566890, 611620566890, 612021695690, 651502609866, 651512899866, 651515599866, 651521969866,
2121200098886, 2121206098886, 2121215998886, 2122200666886, 2122201666886, 2122820986886, 2122825986886,
2126090659886, 2126095659886, 2151200098586, 2151206098586, 2151215998586, 2152200666586, 2152201666586,
2152820986586, 2152825986586, 2156090659586, 2156095659586, 2160000619686, 2160006619686, 2160215999686,
6111000066890, 6111116896890, 6116162686890, 6120006855690, 6120026955690, 6120262695690, 6515060609866,
6515200669866, 6515206669866, 6515600599866, 21212000098886, 21222000666886, 21222006966886, 21222015966886,
21222109866886, 21222118866886, 21222129866886, 21512000098586, 21522000666586, 21522006966586, 21522015966586,
21522109866586, 21522118866586, 21522129866586, 21600000619686, 21600029819686, 21600102519686, 21600111519686,
61110000066890, 61111116896890, 61111205696890, 61161215666890, 61161218666890, 61161619686890, 61200005255690,
61200105155690, 61200215605690, 61200216955690, 61200218605690, 61200229855690, 61200529555690, 61200926655690,
61202619695690, 65150096509866, 65152000669866, 65152029869866, 65152102569866, 65152111569866

And here are the numbers from 100 000 000 000 000 to 1 000 000 000 000 000:

212100209518886, 212100209818886, 212120000098886, 212120606098886, 212220000666886, 212220060666886, 212220159666886,
212221081866886, 212222006666886, 212280006186886, 212280066186886, 212282159986886, 212282208986886, 212282505986886,
212609159659886, 212609208659886, 212609505659886, 212629208659886, 212629505659886, 215100209518586, 215100209818586,
215120000098586, 215120606098586, 215220000666586, 215220060666586, 215220159666586, 215221081866586, 215222006666586,
215280006186586, 215280066186586, 215282159986586, 215282208986586, 215282505986586, 215609159659586, 215609208659586,
215609505659586, 215629208659586, 215629505659586, 216000000619686, 216000060619686, 216000081819686, 216000159619686,
216000209819686, 216001081519686, 216008209819686, 216008259819686, 216020286099686, 216022016699686, 216022066699686,
216022286899686, 216025286599686, 216026005999686, 216515060986686, 216515159986686, 216515286986686, 611100000066890,
611100056086890, 611100105066890, 611100108066890, 611611006686890, 611611008686890, 611612166866890, 611612256866890,
611615166566890, 611615256566890, 611616168686890, 611620015566890, 611620068566890, 611620269566890, 612000015255690,
612001015155690, 612002055855690, 612002058855690, 612002105605690, 612002105655690, 612002108605690, 612002108655690,
612002626955690, 612005055555690, 612005058555690, 612009166655690, 612021006695690, 612021008695690, 612026168695690,
651500906509866, 651500956509866, 651502158609866, 651506060609866, 651506159609866, 651512166899866, 651512529899866,
651512658899866, 651512856899866, 651515060989866, 651515159989866, 651515166599866, 651515286989866, 651515529599866,
651515658599866, 651515856599866, 651520000669866, 651520060669866, 651520081869866, 651520159669866, 651520209869866,
651521081569866, 651528209869866, 651528259869866, 651560906599866, 651560956599866

From this, we can get some infinite families of numbers that can go for 6 iterations, eg 21212000...00098886 will work for any number of 0s in the middle (as long as there is at least one 0).

Answer 2

For the numbers from 10 to 10000, the max we can get is 5 iterations:

(105, 5), (108, 5), (500, 5), (501, 5), (801, 5), (1005, 5), (1008, 5), (5000, 5), (5001, 5), (8001, 5) (output of a Python program)

EDIT: for 10 to 10000000, we can get up to 6:

(21586, 6), (28516, 6), (91582, 6), (98512, 6), (6116890, 6), (6119890, 6), (6186190, 6), (6189190, 6), (6616810, 6), (6619810, 6), (6686110, 6), (6689110, 6)

Here's my code... I know it's not the most efficient or elegant solution, but I didn't have the patience to write it better:

def rotate(number):
    n = str(number)
    n = list(n)
    for i in range(len(n)):
        digit = n[i]
        if '3' == digit or '4' == digit or '7' == digit:
            return False
        if digit == '6':
            n[i] = '9'
        elif digit == '9':
            n[i] = '6'
    n = n[::-1]
    return int(''.join(n))


def last(n):
    return n[-1]


def sort(tuples):
    return sorted(tuples, key=last)


nums = []
for i in range(10, 1000000):
    num = i
    times = 0
    while rotate(num) and times < 10000:
        num += rotate(num)
        times += 1
    nums.append((i, times))
    if times > 9998:
        print(i)

print(sort(nums))