## Le Monde puzzle [#1063]

Posted in Books, Kids, R with tags , , , , , , on August 9, 2018 by xi'an

A simple (summertime?!) arithmetic Le Monde mathematical puzzle

1. A “powerful integer” is such that all its prime divisors are at least with multiplicity 2. Are there two powerful integers in a row, i.e. such that both n and n+1 are powerful?
2.  Are there odd integers n such that n² – 1 is a powerful integer ?

The first question can be solved by brute force.  Here is a R code that leads to the solution:

isperfz <- function(n){
divz=primeFactors(n)
facz=unique(divz)
ordz=rep(0,length(facz))
for (i in 1:length(facz))
ordz[i]=sum(divz==facz[i])
return(min(ordz)>1)}

lesperf=NULL
for (t in 4:1e5)
if (isperfz(t)) lesperf=c(lesperf,t)
twinz=lesperf[diff(lesperf)==1]


with solutions 8, 288, 675, 9800, 12167.

The second puzzle means rerunning the code only on integers n²-1…

[1] 8
[1] 288
[1] 675
[1] 9800
[1] 235224
[1] 332928
[1] 1825200
[1] 11309768


except that I cannot exceed n²=10⁸. (The Le Monde puzzles will now stop for a month, just like about everything in France!, and then a new challenge will take place. Stay tuned.)

Posted in Kids, R with tags , , , on July 6, 2018 by xi'an

Another quick riddle from the riddler: solve the equation

EXMREEK + EHKREKK = ?K?H?X?E

which involves every digit between 0 and 9. While the puzzle can be unravelled by considering first E and K, which must be equal to 6 and 3, a simple R code also leads to the conclusion

isok <- function(a,b){
s=as.numeric(unlist(strsplit(as.character(sum(10^(6:0)*a)+
sum(10^(6:0)*b)),"")))
if (length(s)==7){ goal=FALSE}else{
goal=(length(unique(c(a,b,s)))==10)&(a[2]==s[6])&
(s[8]==a[6])&(s[2]==a[7])&(b[2]==s[4])}
return(goal)}

pasok <- function(T=1e3){
for (t in 1:T){
a[1]=a[5]=a[6]=6;a[7]=3
digs=sample(c(0:2,4,5,7:9),4)
a[2:4]=digs[1:3] b[1]=a[1];b[2]=digs[4];
b[3]=a[7];b[4]=a[4];b[5]=a[1];b[6:7]=a[7]
if (isok(a=a,b=b))
print(rbind(a,b))}}

> pasok()
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
a    6    2    4    7    6    6    3
b    6    8    3    7    6    3    3


which sum is 13085296.

## Le Monde puzzle [#1018]

Posted in Books, Kids, R with tags , , , , , on August 29, 2017 by xi'an

An arithmetic Le Monde mathematical puzzle (that first did not seem to involve R programming because of the large number of digits in the quantity involved):

An integer x with less than 100 digits is such that adding the digit 1 on both sides of x produces the integer 99x.  What are the last nine digits of x? And what are the possible numbers of digits of x?

The integer x satisfies the identity

$10^{\omega+2}+10x+1=99x$

where ω is the number of digits of x. This amounts to

10….01 = 89 x,

where there are ω zeros. Working with long integers in R could bring an immediate solution, but I went for a pedestrian version, handling each digit at a time and starting from the final one which is necessarily 9:

#multiply by 9
rap=0;row=NULL
for (i in length(x):1){
prud=rap+x[i]*9
row=c(prud%%10,row)
rap=prud%/%10}
row=c(rap,row)
#multiply by 80
rep=raw=0
for (i in length(x):1){
prud=rep+x[i]*8
raw=c(prud%%10,raw)
rep=prud%/%10}
#find next digit
y=(row[1]+raw[1]+(length(x)>1))%%10


returning

7 9 7 7 5 2 8 0 9


as the (only) last digits of x. The same code can be exploited to check that the complete multiplication produces a number of the form 10….01, hence to deduce that the length of x is either 21 or 65, with solutions

[1] 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9
[1] 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 8 9 8 8 7 6 4 0 4 4 9 4 3 8 2 0 2 2
[39] 4 7 1 9 1 0 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9


The maths question behind is to figure out the powers k of 10 such that

$10^k\equiv -1 \text{ mod } (89)$

For instance, 10²≡11 mod (89) and 11¹¹≡88 mod (89) leads to the first solution ω=21. And then, since 10⁴⁴≡1 mod (89), ω=21+44=65 is another solution…

## continental divide

Posted in Books, Kids, pictures, R with tags , , , , on May 19, 2017 by xi'an

While the Riddler puzzle this week was anticlimactic,  as it meant filling all digits in the above division towards a null remainder, it came as an interesting illustration of how different division is taught in the US versus France: when I saw the picture above, I had to go and check an American primary school on-line introduction to division, since the way I was taught in France is something like that

with the solution being that 12128316 = 124 x 97809… Solved by a dumb R exploration of all constraints:

for (y in 111:143)
for (z4 in 8:9)
for (oz in 0:999){
z=oz+7e3+z4*1e4
x=y*z
digx=digits(x)
digz=digits(z)
if ((digz[2]==0)&(x>=1e7)&(x<1e8)){
r1=trunc(x/1e4)-digz[5]*y
if ((digz[5]*y>=1e3)&(digz[4]*y<1e4) &(r1>9)&(r1<100)){
r2=10*r1+digx[4]-7*y
if ((7*y>=1e2)&(7*y<1e3)&(r2>=1e2)&(r2<1e3)){
r3=10*r2+digx[3]-digz[3]*y
if ((digz[3]*y>=1e2)&(digz[3]*y<1e3)&(r3>9)&(r3<1e2)){
r4=10*r3+digx[2]
if (r4<y) solz=rbind(solz,c(y,z,x))
}}}}


Looking for a computer-free resolution, the constraints on z exhibited by the picture are that (a) the second digit is 0 and the fourth digit is 7.  Moreover, the first and fifth digits are larger than 7 since y times these digits is a four-digit number. Better, since the second subtraction from a three-digit number by 7y returns a three-digit number and the third subtraction from a four-digit number by ny returns a two-digit number, n is larger than 7 but less than the first and fifth digits. Ergo, z is necessarily 97809! Furthermore, 8y<10³ and 9y≥10³, which means 111<y<125. Plus the constraint that 1000-8y≤99 implies y≥112. Nothing gained there! This leaves 12 values of y to study, unless there is another restriction I missed…

## Le Monde puzzle [#1000…1025]

Posted in Kids, R with tags , , , , , , on March 28, 2017 by xi'an

Le Monde mathematical puzzle launched a competition to celebrate its 1000th puzzle! A fairly long-term competition as it runs over the 25 coming puzzles (and hence weeks). Starting with puzzle #1001. Here is the 1000th puzzle, not part of the competition:

Alice & Bob spend five (identical) vouchers in five different shops, each time buying the maximum number of items to get close to the voucher value. In these five shops, they buy sofas at 421 euros each, beds at 347 euros each, kitchen appliances at 289 euros each, tables at 251 euros each and bikes at 211 euros each, respectively. Once the buying frenzy is over, they realise that within a single shop, they would have spent exactly four vouchers for the same products. What is the value of a voucher?

## Le Monde puzzle [#967]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , , , , on September 30, 2016 by xi'an

A Sudoku-like Le Monde mathematical puzzle for a come-back (now that it competes with The Riddler!):

Does there exist a 3×3 grid with different and positive integer entries such that the sum of rows, columns, and both diagonals is a prime number? If there exist such grids, find the grid with the minimal sum?

I first downloaded the R package primes. Then I checked if by any chance a small bound on the entries was sufficient:

cale<-function(seqe){
ros=apply(seqe,1,sum)
cole=apply(seqe,2,sum)
dyag=sum(diag(seqe))
dayg=sum(diag(seqe[3:1,1:3]))
return(min(is_prime(c(ros,cole,dyag,dayg)))>0)}


Running the blind experiment

for (t in 1:1e6){
n=sample(9:1e2,1)
if (cale(matrix(sample(n,9),3))) print(n)}


I got 10 as the minimal value of n. Trying with n=9 did not give any positive case. Running another blind experiment checking for the minimal sum led to the result

> A
[,1] [,2] [,3]
[1,] 8 3 6
[2,] 1 5 7
[3,] 2 11 4


with sum 47.

## Le Monde puzzle [#945]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on January 25, 2016 by xi'an

A rather different Le Monde mathematical puzzle:

A two-person game is played on an nxn grid filled with zero. Each player pick an entry, which is increased by one as well as all adjacent entries. The game stops when all entries are equal. For n=3,4,5, what are the possible grids with identical values all over?

If I define an R neighbourhood function

 nighbo=function(i,n){
neigh=i
if (i%%n!=1) neigh=c(i-1,neigh)
if (i%%n>0) neigh=c(i+1,neigh)
if (i+n<=n*n) neigh=c(i+n,neigh)
if (i-n>0) neigh=c(i-n,neigh)
return(neigh)}


and try a brute force filling of the grid

while ((min(grid)==0)||(length(unique(grid))>1)){
ent=sample(1:(n*n),1,prob=1/as.vector(grid+1)^10)
grid[nighbo(ent,n)]=grid[nighbo(ent,n)]+1}


the loop never stops. When thinking of the case n=3 [while running in the early morning], I wondered whether or not reaching an equal value on all entries was at all possible. Indeed, it is impossible to update one of the four corners without updating at least one of the neighbours, while the converse is false. Experimenting further with simulated annealing to optimise the probabilities of picking different entries in the table when n=4,5 seems to indicate this is also the case for larger values of n, in that all attempts lead to larger values of neighbours to the four corners :

outer=c(1,n,n*n,n*n-n+1)
border=sort(unique(c(2:(n-1),(n*n-n+2):(n*n-1),1+n*(1:(n-2)),n+n*(1:(n-2)))))
inner=(1:(n*n))[-c(outer,border)]
#
target=function(weit){
grid=matrix(0,n,n)
for (t in 1:1e4){
cas=sample(1:3,1,prob=weit)
if (cas==1) ent=sample(outer,1,prob=max(grid[outer])-grid[outer]+1)
if (cas==2) ent=sample(border,1,prob=max(grid[border])-grid[border]+1)
if (cas==3) ent=sample(inner,1,prob=max(grid[inner])-grid[inner]+1)
ent=nighbo(ent,n)
grid[ent]=grid[ent]+1}
ave=c(mean(grid[outer]),mean(grid[border]),mean(grid[inner]))
return(list(dive=max(diff(sort(ave))),ave=ave,ava=mean(grid)))
}
#
weit=rep(1,3)
cur=target(weit)
T=100
while (cur$dive>0){ ind=sample(1:3,1,prob=1/cur$ave)
peit=weit
peit[ind]=weit[ind]-(cur$ave[ind]-cur$ava)*runif(1)/(cur$ava) while(peit[ind]<0) peit[ind]=weit[ind]-(cur$ave[ind]-cur$ava)*runif(1)/(cur$ava)
prop=target(peit)
if (log(runif(1))*1e4/T<prop$dive-cur$dive){
weit=peit;cur=prop}
T=T*1.00001
print(cur\$ave)}