Le Monde puzzle (#800)

Here is the mathematical puzzle of the weekend edition of Le Monde:

Consider a sequence where the initial number is between 1 and 10³, and each term in the sequence is derived from the previous term as follows:

1. if the last digit of the previous term is between 6 and 9, multiply it by 9;
2. if the last digit of the previous term is between 0 and 5, take this digit away

Show that all sequences stop and give the length of the largest sequence.

To solve it, I wrote the following code:

seqlength=function(i){
las=i %% 10 #final digit
if (las>5){u=i*9}else{u=trunc(i/10)}
if(u==0){return(1)}else{return(seqlength(u)+1)}
}

and found that the largest sequence started with 119 and lasted 16 steps:

[1] 119
[1] 1071
[1] 107
[1] 963
[1] 96
[1] 864
[1] 86
[1] 774
[1] 77
[1] 693
[1] 69
[1] 621
[1] 62
[1] 6
[1] 54
[1] 5

Similarly, the optimum between 1 and 10⁵ is attained for 95209 with 41 steps..

The math solution for the sequence to converge is a two-line proof as the transition from x to x₁ either sees the removal of the last digit or a multiplication by 9, and the transition from x₁ to x₂ sees at worst a multiplication by 10 in the first case and always an integer division by 10 in the second case (since 9×6=54,…). So the move from x to x₂ is always strictly decreasing unless x or x₁ is zero, in which case the sequence ends up. Therefore, a strictly decreasing integer sequence can only stop in zero.

Figuring out the longest sequence is a much harder problem. Because the transform is not monotonous, the larger x‘s do not induce longer sequences. For instance, the solution between 1 and 10³ is 119, not 999… And moving to the longest between 10³ and 10⁴ it does not visit 119, as one could think! Even the length of the sequence is an unknown: for three digits, it is 16, for four (8518), it is 30, and for five (95209), it is 41… For six, waiting on the Berlin Teugel Airport runway, I found 469999 and a length of 45. (Note that 999999 gives a length of 18, while 199999 gives a length of 31!) Very surprising also in the lack of monotonicity in the dependence on the number of digits!