## 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:

- if the last digit of the previous term is between 6 and 9, multiply it by 9;
- 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..

**T**he math solution for the sequence to converge is a two-line proof as the transition from x_{0} to x_{1} either sees the removal of the last digit or a multiplication by 9, and the transition from x_{1} to x_{2} 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_{0} to x_{2} is always strictly decreasing unless x_{0} or x_{1} is zero, in which case the sequence ends up. Therefore, a strictly decreasing integer sequence can only stop in zero.

**F**iguring out the longest sequence is a much harder problem. Because the transform is not monotonous, the larger x_{0}‘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!

## Leave a Reply