Archive for arithmetics

Le Monde puzzle [#752]

Posted in R, Statistics with tags , , , , , , , on December 9, 2011 by xi'an

After a loooong break, here is one Le Monde mathematical puzzle I had time to look at, prior to going to Dauphine for a Saturday morning class (in replacement of my R class this week)! The question is as follows:

A set of numbers {1,…,N} is such that multiples of 4 are tagged C and multiples of 5 and of 11 are tagged Q. Numbers that are not multiples of 4, 5, or 11, and numbers that are multiples of both 4 and 5 or of both 4 and 11 are not tagged. Find N such that the number of C tags is equal to the number of Q tags.

This is a plain enumeration problem.

N=0
noco=TRUE
nbC=nbQ=0

while (noco){
 N=N+1
 divF=FALSE
 if (trunc(N/4)*4==N){
    nbC=nbC+1
    divF=TRUE
    }
 if ((trunc(N/5)*5==N)||(trunc(N/11)*11==N)){
   if (divF){
     nbC=nbC-1
     }else{ nbQ=nbQ+1}
   }
 noco=(nbC!=nbQ)
 }

When I ran the code, I found many solutions

[1] 1 0 0
[1] 2 0 0
[1] 3 0 0
[1] 5 1 1
[1] 6 1 1
[1] 7 1 1
[1] 10  2  2
[1] 12  3  3
[1] 13  3  3
[1] 14  3  3
[1] 16  4  4
[1] 17  4  4
[1] 18  4  4
[1] 19  4  4
[1] 20  4  4
[1] 21  4  4
[1] 24  5  5
[1] 28  6  6
[1] 29  6  6
[1] 32  7  7
[1] 64 12 12

with no value further than 64 (testing all the way to 3,500,000). This seems in line with the fact that there are more multiples of 5 or 11 than of 4 when N is large enough. This can be seen by drawing the curves of the (approximate) number of multiples:

curve((trunc(x/4)-trunc(x/20)-trunc(x/44)),
  from=10,to=250,n=500)
curve((trunc(x/5)+trunc(x/11)-trunc(x/55)-
  trunc(x/20)-trunc( /44)),from=10,to=250,add=TRUE,n=500)

Le Monde puzzle [#738]

Posted in R with tags , , , , , on September 2, 2011 by xi'an

The Friday puzzle in Le Monde this week is about “friendly perfect squares”, namely perfect squares x2>10 and y2>10 with the same number of digits and such that, when drifting all digits of x2 by the same value a (modulo 10), one recovers y2. For instance, 121 is “friend” with 676. Here is my R code:

xtrct=function(x){
  x=as.integer(x)
  digs=NULL
  for (i in 0:trunc(log(x,10))){
    digs[i+1]=trunc((x-sum(digs[1:i]*10^(trunc(log(x,10)):(trunc(log(x,10))-
    i+1))))/10^(trunc(log(x,10))-i))}
  return(digs)
  }

pdfct=(4:999)^2
for (t in 1:5){
  pfctsq=pdfct[(pdfct>=10^t)&(pdfct<10^(t+1))]
  rstrct=apply(as.matrix(pfctsq),1,xtrct)

  for (i in 1:(dim(rstrct)[2]-2)){

   dive=apply(matrix(rstrct[,(i+1):dim(rstrct)[2]]-
   rstrct[,i],nrow=t+1),2,unique)
    if (is.matrix(dive))
       dive=lapply(seq_len(ncol(dive)), function(i) dive[,i])
    dive=as.integer(lapply(dive,length))
    if (sum(dive==1)>0)
       print(c(pfctsq[i],pfctsq[
       ((i+1):dim(rstrct)[2])[(dive==1)]]))
    }
  }

which returns

[1] 121 676
[1] 1156 4489
[1] 2025 3136
[1] 13225 24336
[1] 111556 444889

namely the pairs (121,676), (1156,4489), (2025,3136), (13225,24336), and (111556,444889) as the solutions. The strange line of R code

    if (is.matrix(dive))
       dive=lapply(seq_len(ncol(dive)), function(i) dive[,i])

is due to the fact that, when the above result is a matrix, turning it into a list means each entry of the matrix is an entry of the list. After trying to solve the problem on my own for a long while (!), I found the above trick on stackoverflow. (As usual, the puzzle is used as an exercise in [basic] R programming. There always exists a neat mathematical solution!)

Candy branching process

Posted in R, Statistics with tags , , , on May 6, 2010 by xi'an

The mathematical puzzle in the latest weekend edition of Le Monde is as follows:

Two kids are given three boxes of chocolates with a total of 32 pieces. Rather than sharing evenly, they play the following game: Each in turn, they pick one of the three boxes, empty its contents in a jar and pick some chocolates from one of the remaining boxes so that no box stays empty. The game ends with the current player’s loss when this is no longer possible. What is the optimal strategy?

This led me to consider a simple branching process starting from a multinomial

(u_1,v_1,w_1)\sim \mathcal{M}_3(29;1/3,1/3,1/3)

to define (x_1=1+u_1,y_1=1+v_1,z_1=1+w_1). and then following the above splitting process, namely the selection of the dead and of the split components, x_t and y_t>1 say, and the generation of

(u_{t+1},v_{t+1})\sim \mathcal{M}_2(y_t-2;1/2,1/2)

with the updated value being

(x_{t+1},y_{t+1},z_{t+1}) = (1+u_{t+1},1+v_{t+1},z_t).

This process is obviously not optimal but on the opposite completely random. Running a short R program like

N=32
prc=story=rep(1,3)+as.vector(rmultinom(1,(N-3),prob=rep(1,3)))
while (sum(prc)>3){
  if (sum(prc>1)==1)
         i=(1:3)[prc>1]           #split
   else
         i=sample((1:3)[prc>1],1) #split
   j=sample((1:3)[-i],1)          #unchanged
   prc=c(prc[j],1+as.vector(rmultinom(1,prc[i]-2,prob=rep(1,2))))
   story=rbind(story,prc)
}

leads to a histogram of the game duration which is as follows. (Note that the R command sample((1:3)[prc>1]) does not produce what it should when only one term of prc is different from 1, hence the condition.) Obviously, this is not a very interesting branching process in that the sequence always ends up in a few steps…

Of course, this does not tell much about the initial puzzle. However, discussing the problem with Antoine Dreyer and Robin Ryder led to Antoine obtaining all winning and loosing configurations up to N=32 by a recursive R algorithm and to Robin establishing a complete resolution (I do not want to unveil it before he does!) that involves the funny facts [a] any starting configuration with only odd numbers is loosing and [b] any N that is a power of 2, like 32, always produces winning configurations.

schoolmath

Posted in R with tags , , , on March 7, 2010 by xi'an

In connection with the Le Monde puzzle of last week, I was looking for an R function that would give me the prime factor decomposition of any integer. Such a function exists within the package schoolmath, developped by Joerg Schlarmann and Josef Wienand. It is called prime.factor and it returns the prime factors of any integer:

> prime.factor(2016)
[1] 2 2 2 2 2 3 3 7
> prime.factor(2032)
[1]   2   2   2   2 127
> prime.factor(2031)
[1]   3 677
> prime.factor(2039)
2039 is a prime!
[1] 2039

Warning [06/14/10]! As pointed out in this blog by Neil Gunther, schoolmath contains mistakes in the function primes, listing 1 as a prime number but also including decomposable numbers like 133.

Follow

Get every new post delivered to your Inbox.

Join 652 other followers