Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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:

``` 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 x 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 x to x2 is always strictly decreasing unless x 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 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!

Filed under: R Tagged: Le Monde, mathematical puzzle, R  