Archive for Le Monde

Egyptian fractions [Le Monde puzzle #922]

Posted in Books, Kids, R with tags , , , , , , , on July 28, 2015 by xi'an

For its summer edition, Le Monde mathematical puzzle switched to a lighter version with immediate solution. This #922 considers Egyptian fractions which only have distinct denominators (meaning the numerator is always 1) and can be summed. This means 3/4 is represented as ½+¼. Each denominator only appears once. As I discovered when looking on line, a lot of people are fascinated with this representation and have devised different algorithms to achieve decompositions with various properties. Including Fibonacci who devised a specific algorithm called the greedy algorithm in 1202 in the Liber Abaci. In the current Le Monde edition, the questions were somewhat modest and dealt with the smallest decompositions of 2/5, 5/12, and 50/77 under some additional constraint.

Since the issue was covered in so many places, I just spent one hour or so constructing a basic solution à la Fibonacci and then tried to improve it against a length criterion. Here are my R codes (using the numbers library):

osiris=function(a,b){
#can the fraction a/b be simplified
diva=primeFactors(a)
divb=primeFactors(b)
divc=c(unique(diva),unique(divb))
while (sum(duplicated(divc))>0){
  n=divc[duplicated(divc)]
  for (i in n){a=div(a,i);b=div(b,i)}
  diva=primeFactors(a)
  divb=primeFactors(b)
  divc=c(unique(diva),unique(divb))
  }
  return(list(a=a,b=b))
}

presumably superfluous for simplifying fractions

horus=function(a,b,teth=NULL){
#simplification
anubis=osiris(a,b)
a=anubis$a;b=anubis$b
#decomposition by removing 1/b
 isis=NULL
 if (!(b %in% teth)){
   a=a-1
   isis=c(isis,b)
   teth=c(teth,b)}
 if (a>0){
#simplification
  anubis=osiris(a,b)
  bet=b;a=anubis$a;b=anubis$b
  if (bet>b){ isis=c(isis,horus(a,b,teth))}else{
  # find largest integer
    k=ceiling(b/a)
    while (k %in% teth) k=k+1
    a=k*a-b
    b=k*b
    isis=c(isis,k,horus(a,b,teth=c(teth,k)))
    }}
 return(isis)}

which produces a Fibonacci solution (with the additional inclusion of the original denominator) and

nut=20
seth=function(a,b,isis=NULL){
#simplification
anubis=osiris(a,b)
a=anubis$a;b=anubis$b
if ((a==1)&(!(b %in% isis))){isis=c(isis,b)}else{
 ra=hapy=ceiling(b/a)
 if (max(a,b)<1e5) hapy=horus(a,b,teth=isis)
 k=unique(c(hapy,ceiling(ra/runif(nut,min=.1,max=1))))
 propa=propb=propc=propd=rep(NaN,le=length((k %in% isis)))
 bastet=1
 for (i in k[!(k %in% isis)]){
   propa[bastet]=i*a-b
   propb[bastet]=i*b
   propc[bastet]=i
   propd[bastet]=length(horus(i*a-b,i*b,teth=c(isis,i)))
   bastet=bastet+1
   }
 k=propc[order(propd)[1]]
 isis=seth(k*a-b,k*b,isis=c(isis,k))
 }
return(isis)}

which compares solutions against their lengths. When calling those functions for the three fractions above the solutions are

> seth(2,5)
[1] 15 3
> seth(5,12)
[1] 12  3
> seth(50,77)
[1]   2 154   7

with no pretension whatsoever to return anything optimal (and with some like crashes when the magnitude of the entries grows, try for instance 5/121). For this latest counter-example, the alternative horus works quite superbly:

> horus(5,121)
[1] 121 31 3751 1876 7036876

Le Monde puzzle [#920]

Posted in Books, Kids, R, Statistics, University life with tags , on July 23, 2015 by xi'an

A puzzling Le Monde mathematical puzzle (or blame the heat wave):

A pocket calculator with ten keys (0,1,…,9) starts with a random digit n between 0 and 9. A number on the screen can then be modified into another number by two rules:
1. pressing k changes the k-th digit v whenever it exists into (v+1)(v+2) where addition is modulo 10;
2. pressing 0k deletes the (k-1)th and (k+1)th digits if they both exist and are identical (otherwise nothing happens.
Which 9-digit numbers can always be produced whatever the initial digit?

I did not find an easy entry to this puzzle, in particular because it did not state what to do once 9 digits had been reached: would the extra digits disappear? But then, those to the left or to the right? The description also fails to explain how to handle n=000 000 004 versus n=4.

Instead, I tried to look at the numbers with less than 7 digits that could appear, using some extra rules of my own like preventing numbers with more than 9 digits. Rules which resulted in a sure stopping rule when applying both rules above at random:

leplein=rep(0,1e6)
for (v in 1:1e6){
 x=as.vector(sample(1:9,1))
 for (t in 1:1e5){
  k=length(x) #as sequence of digits
  if (k<3){

   i=sample(rep(1:k,2),1)
   x[i]=(x[i]+1)%%10
   y=c(x[1:i],(x[i]+1)%%10)
   if (i<k){ x=c(y,x[(i+1):k])}else{ x=y}
 }else{

  prop1=prop2=NULL
  difs=(2:(k-1))[abs(x[-(1:2)]-x[-((k-1):k)])==0]
  if (length(difs)>0) prop1=sample(rep(difs,2),1)
  if (k<9) prop2=sample(rep(1:k,2),1)

  if (length(c(prop1,prop2))>1){
   if (runif(1)<.5){

    x[prop2]=(x[prop2]+1)%%10
    y=c(x[1:prop2],(x[prop2]+1)%%10)
    if (prop2<k){ x=c(y,x[(prop2+1):k])}else{ x=y}
    }else{
      x=x[-c(prop1-1,prop1+1)]}
    while ((length(x)>1)&(x[1]==0)) x=x[-1]}

  if (length(c(prop1,prop2))==1){
    if (is.null(prop2)){ x=x[-c(prop1-1,prop1+1)]
    }else{
     x[prop2]=(x[prop2]+1)%%10
     y=c(x[1:prop2],(x[prop2]+1)%%10)
     if (prop2<k){ x=c(y,x[(prop2+1):k])
     }else{ x=y}
     x=c(x[1:(prop2-1)],
       (x[prop2]+1)%%10,
       (x[prop2]+2)%%10,x[(prop2+1):k])}
    while ((length(x)>1)&(x[1]==0)) x=x[-1]}

  if (length(c(prop1,prop2))==0) break()
  }

 k=length(x)
 if (k<7) leplein[sum(x*10^((k-1):0))]=
          leplein[sum(x*10^((k-1):0))]+1
}}

code that fills an occupancy table for the numbers less than a million over 10⁶ iterations. The solution as shown below (with the number of zero entries over each column) is rather surprising in that it shows an occupancy that is quite regular over a grid. While it does not answer the original question…

lemonde920

Le Monde puzzle [#919]

Posted in Books, Kids, Statistics, University life with tags , , , , on July 19, 2015 by xi'an

A rather straightforward Le Monde mathematical puzzle:

Find 3 digit integers x such that the integer created by collating x with (x+1) gives a 6 digit integer that is a perfect square.

Easy once you rewrite the constraint as 1000x+x+1 being a perfect square a², which means that x is equal to (a-1)(a+1)/1001, hence that 1001=7x11x13 divides either a+1 or a=1.

sol=NULL
vals=as.vector(outer(c(7,11,13),1:999,"*"))
vals=c(vals-1,vals+1)
for (a in vals){
  x=round((a-1)*(a+1)/1001)
  if ((1000*x+x+1==a^2)&(x<999)&(x>99)) sol=c(sol,x)}

which returns four solutions:

> unique(sol)
[1] 183 328 528 715

An addendum to the puzzle is

Find 4 digit integers x such that the integer created by collating x with (x+1) gives an 8 digit integrer that is a perfect square.

Similarly easy once you rewrite the constraint as 10,000x+x+1 being a perfect square a², which means that x is equal to (a-1)(a+1)/10,001, hence that 10,001=73×137 divides either a+1 or a=1.

sol=NULL
vals=as.vector(outer(c(73,137),(1:9999),"*"))
vals=c(vals-1,vals+1)
for (a in vals){
  x=round((a-1)*(a+1)/10001)
  if ((10000*x+x+1==a^2)&(x<9999)&(x>999)) sol=c(sol,x)}

leading to the conclusion there is a single solution:

> unique(sol)
[1] 6099

Le Monde puzzle [#913]

Posted in Books, Kids, Statistics, University life with tags , , , , , , , on June 12, 2015 by xi'an

An arithmetics Le Monde mathematical puzzle:

Find all bi-twin integers, namely positive integers such that adding 2 to any of their dividers returns a prime number.

An easy puzzle, once the R libraries on prime number decomposition can be found!, since it is straightforward to check for solutions. Unfortunately, I could not install the recent numbers package. So I used instead the schoolmath R package. Despite its possible bugs. But it seems to do the job for this problem:

lem=NULL
for (t in 1:1e4) 
  if (prod(is.prim(prime.factor(t)+2)==1)) 
    lem=c(lem,t)digin=function(n){

which returned all solutions, albeit in a lengthy fashion:

> lem
 [1] 1 3 5 9 11 15 17 25 27 29 33 41 45 51 55
 [16] 59 71 75 81 85 87 99 101 107 121 123 125 135 137 145
 [31] 149 153 165 177 179 187 191 197 205 213 225 227 239 243 255
 [46] 261 269 275 281 289 295 297 303 311 319 321 347 355 363 369
 [61] 375 405 411 419 425 431 435 447 451 459 461 493 495 505 521
 [76] 531 535 537 561 569 573 591 599 605 615 617 625 639 641 649
 [91] 659 675 681 685 697 717 725 729 745 765 781 783 807 809 821
[106] 825 827 841 843 857 867 881 885 891 895 909 933 935 955 957
[121] 963 985 1003 1019 1025 1031 ...

terrible graph of the day

Posted in Books, Kids, R, Statistics with tags , , , , , , on May 12, 2015 by xi'an

A truly terrible graph in Le Monde about overweight and obesity in the EU countries (and Switzerland). The circle presentation makes no logical sense. Countries are ordered by 2030 overweight percentages, which implies the order differs for men and women. (With a neat sexist differentiation between male and female figures.)  The allocation of the (2010) grey bar to its country is unclear (left or right?). And there is no uncertain associated with the 2030 predictions. There is no message coming out of the graph, like the massive explosion in the obesity and overweight percentages in EU countries. Now, given that the data is available for women and men, ‘Og’s readers should feel free to send me alternative representations!

Le Monde puzzle [#910]

Posted in Books, Kids, Statistics, University life with tags , , on May 8, 2015 by xi'an

An game-theoretic Le Monde mathematical puzzle:

A two-person game consists in choosing an integer N and for each player to successively pick a number in {1,…,N} under the constraint that a player cannot pick a number next to a number this player has already picked. Is there a winning strategy for either player and for all values of N?

for which I simply coded a recursive optimal strategy function:

gain=function(mine,yours,none){
  fine=none
  if (length(mine)>0)
    fine=none[apply(abs(outer(mine,none,"-")),
              2,min)>1]
  if (length(fine)>0){
   rwrd=0
   for (i in 1:length(fine)) 
    rwrd=max(rwrd,1-gain(yours,c(mine,fine[i]),
         none[none!=fine[i]]))
   return(rwrd)}
  return(0)}

which returned a zero gain, hence no winning strategy for all values of N except 1.

> gain(NULL,NULL,1)
[1] 1
> gain(NULL,NULL,1:2)
[1] 0
> gain(NULL,NULL,1:3)
[1] 0
> gain(NULL,NULL,1:4)
[1] 0

Meaning that the starting player is always the loser!

Le Monde puzzle [#909]

Posted in Books, Kids, R with tags , , on May 1, 2015 by xi'an

Another of those “drop-a-digit” Le Monde mathematical puzzle:

Find all integers n with 3 or 4 digits, no exterior zero digit, and a single interior zero digit, such that removing that zero digit produces a divider of x.

As in puzzle #904, I made use of the digin R function:

digin=function(n){
  as.numeric(strsplit(as.character(n),"")[[1]])}

and simply checked all integers up to 10⁶:

plura=divid=NULL
for (i in 101:10^6){
 dive=rev(digin(i))
 if ((min(dive[1],rev(dive)[1])>0)&
    (sum((dive[-c(1,length(dive))]==0))==1)){
   dive=dive[dive>0]
   dive=sum(dive*10^(0:(length(dive)-1)))
 if (i==((i%/%dive)*dive)){
   plura=c(plura,i)
   divid=c(divid,dive)}}}

which leads to the output

> plura
1] 105 108 405 2025 6075 10125 30375 50625 70875
> plura/divid
[1] 7 6 9 9 9 9 9 9 9

leading to the conclusion there is no solution beyond 70875. (Allowing for more than a single zero within the inner digits sees many more solutions.)

Follow

Get every new post delivered to your Inbox.

Join 905 other followers