## 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&gt;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:

``` 119
 1071
 107
 963
 96
 864
 86
 774
 77
 693
 69
 621
 62
 6
 54
 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 x0 to x1 either sees the removal of the last digit or a multiplication by 9, and the transition from x1 to x2 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 x0 to x2 is always strictly decreasing unless x0 or x1 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 x0‘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!

This site uses Akismet to reduce spam. Learn how your comment data is processed.