Le Monde puzzle [#820]

The current puzzle is… puzzling:

Given the set {1,…,N} with N<61, one iterates the following procedure: take (x,y) within the set and replace the pair with the smallest divider of x+y (bar 1). What are the values of N such that the final value in the set is 61?

I find it puzzling because the way the pairs are selected impacts the final value. Or not, depending upon N. Using the following code (with factors() from the pracma package):

library(pracma)
endof=function(N){
  coll=1:N
  for (t in 1:(N-1)){

    pair=sample(1:length(coll),2)
    dive=min(factors(sum(coll[pair])))
    coll=coll[-pair]
    coll=c(coll,dive)
    }
  print(dive)
  }

I got:

> for (t in 1:10) endof(10)
[1] 5
[1] 3
[1] 3
[1] 5
[1] 7
[1] 5
[1] 5
[1] 7
[1] 3
[1] 3> for (t in 1:10) endof(16)
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2

For N of the form 4k or 4k-1, the final number is always 2 while for N‘s of the form 4k-2 and 4k-3, the final number varies, sometimes producing 61′s. Although I could not find solutions for N less than 17…  Looking more closely into the sequence leading to 61, I could not see a pattern, apart from producing prime numbers as, in, e.g.

61 = 2 + [12 +  (4 + {14 + [13 + 16]})]

for N=17.  (Another puzzle is that 61 plays no particular role: a long run of random calls to endof() return all prime numbers up to 79…)

Udate: Looking at the solution in today’s edition, there exist a solution for N=13 and a solution for N=14. Even though my R code fails to spot it. Of course, an exhaustive search would be feasible in these two cases.  (I had also eliminated values below as not summing up to 61.) The argument for eliminating 4k and 4k-1 is that there must be an odd number of odd numbers in the collection, otherwise, the final number is always 2.

Ｒによるモンテカルロ法入門

Here is the cover of the Japanese translation of our Introducing Monte Carlo methods with R book.  A few year after the French translation. It actually appeared last year in August but I was not informed of this till a few weeks ago. The publisher is Maruzen, with an associated webpage if you want to order… Unless I am confused the translators are Hiro Ishida and Kazue Ishida; they deserve a major ありがとう ! And too bad George is no longer with us: this must have been the first translation of one of his books in Japanese..

awalé

Following Le Monde puzzle #810, I tried to code an R program (not reproduced here) to optimise an awalé game but the recursion was too rich for R:

Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?

even with a very small number of holes and seeds in the awalé… Searching on the internet, it seems the computer simulation of a winning strategy for an awalé game still is an open problem! Here is a one-step R function that does  not produce sure gains for the first player, far from it, as shown by the histogram below…  I would need a less myopic strategy by iterating  this function at least twice.

onemorestep=function(x,side){
# x current state of the awale,
# side side of the awale (0 vs 1)

M=length(x);N=as.integer(M/2)
rewa=rep(0,M)
newb=matrix(0,ncol=M,nrow=M)

for (i in ((1:N)+N*side)){

 if (x[i]>0){
   y=x
   y[i]=0
   for (t in 0:(x[i]-1))
     y[1+(i+t)%%M]=y[1+(i+t)%%M]+1

   last=1+(i+t)%%M
   if (side){ gain=(last<=N)
    }else{ gain=(last>N)}

   if (gain){# ending up on the right side
     rewa[i]=0
     while (((last>0)&&(side))||((last>N)||(!side)))
     if ((y[last]==2)||(y[last]==3)){
          rewa[i]=rewa[i]+y[last];y[last]=0
          last=last-1
          }else{ break()}
     }
   newb[i,]=y
   }
  }
if (max(rewa)>0){
  sol=order(-rewa)[1]
  }else{ sol=rang=((1:N)+N*side)[x[((1:N)+N*side)]>0]
   if (length(rang)>1) sol=sample(rang,1,prob=x[rang]^3)}

   return(list(reward=max(rewa),board=newb[sol,]))
}

R for dummies

I already mentioned R for dummies a while ago on the ‘Og and never got around to read it from cover to back. Now that I am reduced to a dummy state with too much free time!, I can produce a full review of the book.

R for dummies was written by two Belgian statistics conultants, de Vries and Meys. It covers the basics of R in five parts: intro to R, bases of R, coding with R, data structures, and graphics in R. Overall, although the “for dummies style” generally grates on my approach to books, I have no objection whatsoever to this R for dummies and given its price  I could even use it in my R class next year. Esp. since it advocates the use of modern tools like Rstudio and ggplot2. It also compares with a lot of other R manuals, providing the proper basics but not going too far into the subtleties of the language. I think there may be a wee bit too much in the handling of data sections and not enough in the statistics and graphics sections. But there are quite useful gems, as well, from the generic recommendations on how to write clean code (not enough on the local vs. global variables) to debugging tools to the entry into the formula interface. (We could have done without the ten things we could have done in Excel!)

A minor criticism is that the graphics are mostly rough outcomes with no attempt at making them “nicer”. Similarly (in terms of importance), the cover involves a ridiculous pseudo-histogram in 3D that was clearly not produced with R… A silly choice when writing about a graphic-friendly computer language!

Overall, a worthy addition to the collection of R manuals. I would certainly put Matloff’s Art of R Programming on top but this one may reach a different audience…

Le Monde puzzle [#818]

The current puzzle is as follows:

Define the symmetric of an integer as the integer obtained by inverting the order of its digits, eg 4321 is the symmetric of 1234. What are the numbers for which the square is equal to the symmetric of the square of the symmetric?

I first consulted stackexchange to find a convenient R function to create the symmetric:

int2digit=function(x){
as.numeric(sapply(sequence(nchar(x)),
  function(y) substr(x, y, y)))}

digit2int=function(a){
as.numeric(paste(a,collapse=""))}

flip=function(x){
  digit2int(rev(int2digit(x)))}

and then found that all integers but the multiples of 10 are symmetric! only some integers involving 1,2,3 and sometimes zero would work:

> for (i in 1:1000){
+   if (i^2==flip(flip(i)^2)) print(i)}
[1] 1
[1] 2
[1] 3
[1] 11
[1] 12
[1] 13
[1] 21
[1] 22
[1] 31
[1] 101
[1] 102
[1] 103
[1] 111
[1] 112
[1] 113
[1] 121
[1] 122
[1] 201
[1] 202
[1] 211
[1] 212
[1] 221
[1] 301
[1] 311

If I am not (again) confused, the symmetric integers would be those (a) not ending with zero and (b) only involving digits whose products are all less than 10.