Le Monde puzzle [#1164]

The weekly puzzle from Le Monde is quite similar to older Diophantine episodes (I find myself impossible to point out):

Give the maximum integer that cannot be written as 105x+30y+14z. Same question for 105x+70y+42z+30w.

These are indeed Diophantine equations and the existence of a solution is linked with Bézout’s Lemma. Take the first equation. Since 105 and 30 have a greatest common divisor equal to 3×5=15, there exists a pair (x⁰,y⁰) such that

105 x⁰ + 30 y⁰ = 15

hence a solution to every equation of the form

105 x + 30 y = 15 a

for any relative integer a. Similarly, since 14 and 15 are co-prime,

there exists a pair (a⁰,b⁰) such that

15 a⁰ + 14 b⁰ = 1

hence a solution to every equation of the form

15 a⁰ + 14 b⁰ = c

for every relative integer c. Meaning 105x+30y+14z=c can be solved in all cases. The same result applies to the second equation. Since algorithms for Bézout’s decomposition are readily available, there is little point in writing an R code..! However, the original question must impose the coefficients to be positive, which of course kills the Bézout’s identity argument. Stack Exchange provides the answer as the linear Diophantine problem of Frobenius! While there is no universal solution for three and more base integers, Mathematica enjoys a FrobeniusNumber solver. Producing 271 and 383 as the largest non-representable integers. Also found by my R code

o=function(i,e,x){
  if((a<-sum(!!i))==sum(!!e))sol=(sum(i*e)==x) else{sol=0
    for(j in 0:(x/e[a+1]))sol=max(sol,o(c(i,j),e,x))}
  sol}
a=(min(e)-1)*(max(e)-1)#upper bound
M=b=((l<-length(e)-1)*prod(e))^(1/l)-sum(e)#lower bound
for(x in a:b){sol=0
for(i in 0:(x/e[1]))sol=max(sol,o(i,e,x))
M=max(M,x*!sol)}

(And this led me to recover the earlier ‘Og entry on the coin problem! As of last November.) The published solution does not bring any useful light as to why 383 is the solution, except for demonstrating that 383 is non-representable and any larger integer is representable.

stochastic magnetic bits, simulated annealing and Gibbs sampling

A paper by Borders et al. in the 19 September issue of Nature offers an interesting mix of computing and electronics and optimisation. With two preparatory tribunes! One [rather overdone] on Feynman’s quest. As a possible alternative to quantum computers for creating probabilistic bits. And making machine learning (as an optimisation program) more efficient. And another one explaining more clearly what is in the paper. As well as the practical advantage of the approach over quantum computing. As for the paper itself, the part I understood about factorising an integer F via minimising the squared difference between a product of two integers and F and using simulated annealing sounded rather easy, while the part I did not about constructing a semi-conductor implementing this stochastic search sounded too technical (especially in the métro during rush hour). Even after checking the on-line supplementary material. Interestingly, the paper claims for higher efficiency thanks to asynchronicity than a regular Gibbs simulation of Boltzman machines, quoting Roberts and Sahu (1997) without further explanation and possibly out of context (as the latter is not concerned with optimisation).

Le Monde puzzle [#1105]

Another token game as Le Monde mathematical puzzle:

Archibald and Beatrix play with a pile of n>100 tokens, sequentially picking m tokens from the pile with m being a prime number [including m=1] or a multiple of 6, the winner taking the last tokens. If Beatrix knows n and proposes to Archibald to start, what is the value of n?

Which cannot be solved in a few lines of R code:

k<-function(n)n<4||all(n%%2:ceiling(sqrt(n))!=0)||!n%%6
g=(1:3)
n=c(4,i<-4)
while(max(n)<101){
  if(k(i)) g=c(g,i) else{
  while(i%in%g)i=i+1;j=4;o=!j
  while(!o&(j<i)){ 
    o=(j%in%n)&k(i-j);j=j+1}
  if(o) g=c(g,i) else n=c(n,i)}
  i=i+1}

since it returned no unsuccessful value above 100! With 4, 8, 85, 95, and 99 as predecessors. A rather surprising outcome and a big gap that most certainly has a straightforward explanation! Or a lack of understanding from yours truly: this post appears after the solution was published in Le Monde and I am more bemused than ever since the losing numbers in the journal are given as 4, 8, 85, … 89, and 129. With the slight hiccup that 89 is a prime number…. The other argument in the solution that there can only be five such losers is well-taken since there are only five possible non-zero remainders in the division by 6.

Le Monde puzzle [#1048]

An arithmetic Le Monde mathematical puzzle:

A magical integer m is such that the remainder of the division of any prime number p by m is either a prime number or 1. What is the unique magical integer between 25 and 100? And is there any less than 25?

The question is dead easy to code

primz=c(1,generate_primes(2,1e6))
for (y in 25:10000)
  if (min((primz[primz>y]%%y)%in%primz)==1) print(y)

and return m=30 as the only solution. Bon sang but of course!, since 30=2x3x5… (Actually, the result follows by dividing the quotient of the division of a prime number by 2 by 3 and then the resulting quotient by 5: all possible cases produce a remainder that is a prime number.) For the second question, the same code returns 2,3,4,6,8,12,18,24 as further solutions. There is no solution beyond 30.

Le Monde puzzle [#1028]

Back to standard Le Monde mathematical puzzles (no further competition!), with this arithmetic one:

While n! cannot be a squared integer for n>1, does there exist 1<n<28 such that 28(n!) is a square integer? Does there exist 1<n,m<28 such that 28(n!)(m!) is a square integer? And what is the largest group of distinct integers between 2 and 27 such that the product of 28! by their factorials is a square?

The fact that n! cannot be a square follows from the occurrence of single prime numbers in the resulting prime number decomposition. When considering 28!, there are several single prime numbers like 17, 19, and 23, which means n is at least 23, but then the last prime in the decomposition of 28! being 7 means this prime remains alone in a product by any n! when n<28. However, to keep up with the R resolution tradition, I started by representing all integers between 2 and 28 in terms of their prime decomposition:

primz=c(2,3,5,7,11,13,17,19,23)
dcmpz=matrix(0,28,9)
for (i in 2:28){
 for (j in 1:9){
    k=i
    while (k%%primz[j]==0){ 
      k=k%/%primz[j];dcmpz[i,j]=dcmpz[i,j]+1}}
}

since the prime number factorisation of the factorials n! follows by cumulated sums (over the rows) of dcmpz, after which checking for one term products

fctorz=apply(dcmpz,2,cumsum)
for (i in 23:28)
  if (max((fctorz[28,]+fctorz[i,])%%2)==0) print(i)

and two term products

for (i in 2:28)
for (j in i:27)
 if (max((fctorz[28,]+fctorz[i,]+fctorz[j,])%%2)==0) 
  print(c(i,j))

is easy and produces i=28 [no solution!] in the first case and (i,j)=(10,27) in the second case. For the final question,  adding up to twelve terms together still produced solutions so I opted for the opposite end by removing one term at a time and

for (a in 2:28)
  if (max(apply(fctorz[-a,],2,sum)%%2)==0) print(a)

exhibited a solution for a=14. Meaning that

2! 3! …. 13! 15! …. 28!

is a square.