Le Monde puzzle (#800)

December 14, 2012
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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 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.

lengths of the sequencesFiguring 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

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.