Archive for number theory

wet summer reads [book reviews]

Posted in Books, Kids, Mountains, pictures, Travel with tags , , , , , , , , , , , , , , , , , , , , on September 24, 2017 by xi'an

“‘Oh ye of little faith.’ Rebus picked up his lamb chop and bit into it.” Ian Rankin, Rather be the Devil

Rebus’ latest case, a stray cat, a tree that should not be there, psychological worries in Uppsala, maths formulas, these are the themes of some of my vacation books. I read more than usual because of the heavy rains we faced in Northern Italy (rather than Scotland!). Ian Rankin’s latest novel Rather be the Devil reunites most of the characters of past novels, from John Rebus to Siobhan Clarke, Malcolm Fox, Big Ger’ Cafferty, and others. The book is just as fun to read as the previous ones (but only if one has read those I presume!), not particularly innovative in its plot, which recalls some earlier ones, and a wee bit disappointing in the way Big Ger’ seems to get the upper hand against Rebus and the (actual) police. Nonetheless pleasant for the characters themselves, including the City of Edinburgh itself!, and the dialogues. Rebus is not dead yet (spoiler?!) so there should be more volumes to come as Rankin does not seem to manage without his trademark detective. (And the above quote comes in connection with the muttonesque puzzle I mention in my post about Skye.)

The second book is a short story by Takashi Hiraide called The Guest Cat (in French, The cat who came from Heaven, both differing from the Japanese Neko ko kyaku) and which reads more like a prose poem than like a novel. It is about a (Japanese) middle-aged childless couple living in a small rented house that is next to a beautiful and decaying Japanese garden. And starting a relation with the neighbours’ beautiful and mysterious cat. Until the cat dies, somewhat inexplicably, and the couple has to go over its sorrow, compounded by the need to leave the special place where they live. This does not sound much of a story but I appreciated the beautiful way it is written (and translated), as well as related to it because of the stray cat that also visits us on a regular basis! (I do not know how well the book has been translated from Japanese into English.)

The third book is called Debout les Morts (translated as The Three Evangelists) and is one of the first detective stories of Fred Vargas, written in 1995. It is funny with well-conceived characters (although they sometimes verge so much on the caricature as to make the novel neo-picaresque) and a fairly original scenario that has a Russian doll or onion structure, involving many (many) layers. I was definitely expecting anything but the shocking ending! The three main characters (hence the English translation title) in the novel are 35-ish jobless historians whose interests range from hunter-gatherers [shouldn’t then he be a pre-historian?!] to the Great [WWI] War, with a medieval expert in the middle. (The author herself is a medieval historian.) As written above, it is excessive in everything, from the characters to the plot, to the number of murders, but or maybe hence it is quite fun to read.

The fourth book is Kjell Eriksson‘s Jorden ma rämna that I would translate from the French version as The earth may well split (as it is not translated in English at this stage), the second volume of the Ann Lindell series, which takes place in Uppsala, and in the nearby Swede countryside. I quite enjoyed this book as the detective part was is almost irrelevant. To the point of having the killer known from the start. As in many Scandinavian noir novels, especially Swedish ones, the social and psychological aspects are predominant, from the multiple events leading a drug addict to commit a series of crimes, to the endless introspection of both the main character and her solitude-seeking boyfriend, from the failures of the social services to deal with the addict to a global yearning for the old and vanished countryside community spirit, to the replacement of genuine workers’ Unions by bureaucratic structures. Not the most comforting read for a dark and stormy night, but definitely a good and well-written book.

And the last book is yet again a Japanese novel by Yôko Ogawa, The Housekeeper and The Professor, which title in French is closer to the Japanese title, The professor’s favourite equation (博士の愛した数式), is about a invalid maths professor who has an 80 minutes memory span, following a car accident. His PhD thesis was about the Artin conjecture. And about his carer (rather than housekeeper) who looks after him and manages to communicate despite the 80 mn barrier. And about the carer’s son who is nicknamed Root for having a head like a square root symbol (!). The book is enjoyable enough to read, with a few basic explanations of number theory, but the whole construct is very contrived as why would the professor manage to solve mathematical puzzles and keep some memory of older baseball games despite the 80mn window. (I also found the naivety of the carer as represented throughout the book a wee bit on the heavy side.)

Not a bad summer for books, in the end!!!

Le Monde puzzle [#1013]

Posted in Books, Kids with tags , , , , , on June 23, 2017 by xi'an

A purely arithmetic Le Monde mathematical puzzle:

An operation þ applies to all pairs of natural integers with the properties

0 þ (a+1) = (0 þ a)+1, (a+1) þ (b+1)=(a þ b)+1, 271 þ 287 = 77777, 2018 þ 39 = 2018×39

Find the smallest integer d>287 such that there exists c<d leading to c þ d = c x d, the smallest integer f>2017 such that 2017 þ f = 2017×40. Is there any know integer f such that f þ 2017 = 40×2017?

The major appeal in this puzzle (where no R programming seems to help!) is that the “data” does not completely defines the operation  þ ! Indeed, when a<b, it is straightforward to deduce that a þ b = (0 þ 0)+b, hence solving the first two questions by deriving (0 þ 0)=270×287 [with d=315 and f=2017×40-270×287], but the opposed quantity b þ a is not defined, apart from (2018-39) þ 0. This however brings a resolution since

(2018-39) þ 0 = 2017×39 and (2018-39+2017) þ 2017 = 2017×39+2017 = 2017×40

leading to f=2018-39+2017=3996.

Le Monde puzzle [#960]

Posted in Kids, R with tags , , , , , on April 28, 2016 by xi'an

An arithmetic Le Monde mathematical puzzle:

Given an integer k>1, consider the sequence defined by F(1)=1+1 mod k, F²(1)=F(1)+2 mod k, F³(1)=F²(1)+3 mod k, &tc. [With this notation, F is not necessarily a function.] For which value of k is the sequence the entire {0,1,…,k-1} set?

This leads to an easy brute force resolution, for instance writing the R function

crkl<-function(k) return(unique(cumsum(1:(2*k))%%k))

where 2k is a sufficient substitute for ∞. Then the cases where the successive images of 1 visit the entire set {0,1,…,k-1} are given by

> for (i in 2:550) if (length(crkl(i))==i) print(i)
[1] 2
[1] 4
[1] 8
[1] 16
[1] 32
[1] 64
[1] 128
[1] 256
[1] 512

which suspiciously looks like the result that only the powers of 2 k=2,2²,2³,… lead to a complete exploration of the set {0,1,…,k-1}. Checking a few series in the plane back from Warwick, I quickly found that when k is odd, (1) the sequence is of period k and (2) there is symmetry in the sequence, which means it only takes (k-1)/2 values. For k even, there is a more complicated symmetry, with the sequence being of period 2k, symmetric around its two middle values, and taking the values 1,2,..,1+k(2k+1)/4,..,1+k(k+1)/2. Those values cannot cover the set {0,1,…,k-1} if two are equal, which means an i(i+1)/2 congruent to zero modulo k, hence equal to k. This is clearly impossible when k is a power of 2 because i and i+1 cannot both divide a power of 2. I waited for the published solution as of yesterday’s and the complete argument was to show that when N=2p, the corresponding sequence [for N] is made (modulo p) of the sequence for p plus the same sequence translated by p. The one for N is complete only if the one for p is complete, which by recursion eliminates all cases but the powers of 2…

Le Monde puzzle [#857]

Posted in Books, Kids, R with tags , , , , , , , on March 22, 2014 by xi'an

A rather bland case of Le Monde mathematical puzzle :

Two positive integers x and y are turned into s=x+y and p=xy. If Sarah and Primrose are given S and P, respectively, how can the following dialogue happen?

  • I am sure you cannot find my number
  • Now you told me that, I can, it is 46.

and what are the values of x and y?

In the original version, it was unclear whether or not each person knew she had the sum or the product. Anyway, the first person in the dialogue has to be Sarah, since a product p equal to a prime integer would lead Primrose to figure out x=1 and hence s=p+1. (Conversely, having observed the sum s cannot lead to deduce x and y.) This means x+y-1 is not a prime integer. Now the deduction of Primrose that the sum is 46 implies p can be decomposed only once in a product such that x+y-1 is not a prime integer. If p=45, this is the case since 45=15×3 and 45=5×9 lead to 15+3-1=17 and 5+9-1=13, while 45=45×1 leads to 45+1-1=45.  Other solutions fail, as demonstrated by the R code:

 > for (x in 1:23){
 + fact=c(1,prime.factor(x*(46-x)))
 + u=0;
 + for (i in 1:(length(fact)-1))
 + u=u+1-is.prim(prod(fact[1:i])+prod(fact[-(1:i)])-1)
 + if (u==1) print(x)}
 [1] 1
 

Busser and Cohen argue much more wisely in their solution that any non-prime product p other than 45 would lead to p+1 as an acceptable sum s, hence would prevent Primrose from guessing s.

Le Monde puzzle [#839]

Posted in Books, Kids, R with tags , , on November 16, 2013 by xi'an

A number theory Le Monde mathematical puzzle whose R coding is not really worth it (and which rings a bell of a similar puzzle in the past, puzzle I cannot trace…):

The set Ξ is made of pairs of integers (x,y) such that (i) both x and y are written as a sum of two squared integers (i.e., are bisquare numbers) and (ii) both xy and (x+y) are bisquare numbers. Why is the product condition superfluous?  For which values of (a,b) is the pair (13a,13b) in Ξ ?

In the first question, the property follows from the fact that the product of two bisquare numbers is again a bisquare number, thank to the remarkable identity

(a²+b²)(c²+d²) = (ac+bd)²+(ad-bc)²

(since the double products cancel). For the second question, once I realised that

13=2²+3²

it followed that any number 13a was the sum of two squares, hence a bisquare number, and thus that the only remaining constraint was that (b≥a)

13a+13b=13a(1+13b-a)

is also bisquare. If b-a is even, this sum is then the product of two bisquare numbers and hence a bisquare number. If b-a is odd, I do not have a general argument to bar the case (it certainly does not work for 13+13² and the four next ones).

Le Monde puzzle [#818]

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

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.

tak1ng sudoku ser1ously

Posted in Books, Statistics, University life with tags , , , , , on March 14, 2013 by xi'an

“There is something deeply satisfying in encountering opacity.” (p.9)

I think it was last summer at the Australasian Statistics conference in Adelaide that I saw this book by Jason Rosenhouse and Laura Taalman, Taking Sudoku seriously: The math behind the World’s most popular pencil puzzle. (Or was it in Kyoto at the ISBA meeting?!) In any case, I mentioned my long-term interest in this puzzle (as readers of the ‘Og will undoubtedly have noticed!) and proposed to write a review for Chance. A few weeks later the book arrived at home. Which was a mistake as my wife who is a much deeper Sudoku fanatic than I stole the book with a vague promise to write the review! It is only a few weeks ago that I was able to truly get the book (if not the review) back…

“This is surely the most trivial of pursuits.” (p.4)

In case you never tried to solve a Sudoku puzzle, open your favourite newspaper, news website or phone, and you should immediately find one of those 9×9 squares to fill with integers between 1 and 9, under three sets of constraints: row-wise, column-wise, and block-wise. (The book describes all kinds of variations with no particularly added value.) Depending on the number of integers already present on the grid and on their location, the resolution of the puzzle gets from obvious to close to impossible by hand. This range in the difficulty and the resulting challenges may explain for the popularity of the method, although it remains a mystery to many bystanders. There are many strategies for solving Sudokus, from the (Sherlock Holmes) elimination of obviously impossible values to branching processes carrying guesses until a binary conclusion. The book covers some of those: forced cells, twins, X-wings, and Ariadne’s thread (moving from Star Wars to The Lord of the Ring!). It however does not bring any novel technique to solve Sudokus, at least at the pencil level, so potential readers with this intent in mind should abstain!

“Sudoku is math in the small.” (p.171)

Now many may wonder about the connections between Sudokus and mathematics. Some mathematicians are clearly sceptical. For instance, I remember discussing solving Sudoku grids in the métro with a friend and Mathematics colleague from Paris-Dauphine and she was quite surprised by this fascination, as she did not see any mathematical appeal in the exercise. In my eyes, this is a logical puzzle at the very least (there is one way of setting all the entries and some obligatory paths for filling the grid that have to be exposed), which makes Sudoku vaguely mathematical. I am also attracted by the automated resolution of those puzzles, as shown by my simulated annealing attempt a (long) while ago, even though I am aware that the state-of-the-art codes are beyond my reach. (They are not detailed either in the book.) Reading this book actually made me think of potential alternatives for simulating annealing, from using additional integers during relaxation, to solving a set of algebraic equations under relaxed constraints. (I wonder if Gröbner bases are used by the fastest resolution codes.)

“We are unaware of any result about Sudoku puzzles provable using the techniques of graph-coloring that could not have been arrived at more easily by other means.” (p.133)

Taking Sudoku Seriously does exhibit some of those connections, it may however feel contrived for some readers (and unintelligible to others), as the mathematical objects have an existence of their own and do not appear to directly contribute to the resolution of the puzzle. An exception in the first case is the one of Latin and Greco-Latin squares in Chapters 2 and 4, which are Sudokus of sort, while an exception to the second is the mention of Gröbner bases in Chapter 8 for solving sets of algebraic equations providing the solution to Sudokus in the form of complex roots of unity. Some number theory gets introduced along the way, as well as algebra (permutation and symmetry groups, polynomials) and graph theory. Analysis is rather absent from this volume and so is probability (hence simulated annealing). Except for a rather artificial and unrelated entry about Newton’s cannonball and Archimede’s derivation of the area of a circle in Chapter 7.

“We have a number of different audiences in mind.” (p.xi)

A few days prior to finish reading the book, I received my copy of Significance with a review of Taking Sudoku Seriously by Nicola Tilt. Glancing quickly at it, I read she was wondering about the intended audience for the book, which also is an issue with me. Neophytes and mathematicians alike will learn little about maths from reading the book, since the difficult questions (like counting the number of Sudokus and of non-equivalent Sudokus, or creating Sudokus) are not answered. The most interesting input is, in my opinion, the discussion of computer-based mathematical proofs. From the four-colour theorem to counting the number of Sudokus, to counting the number of fundamentally different Sudoku squares [as 5,472,730,538]. Unfortunately, the book publication date (April 2011) means that it missed the “big news”, namely the resolution of what the authors call “The rock star problem”, which is the determination of “the minimum number of starting clues possible in a Sudoku puzzle with a unique solution” (p.164). On Jan. 1, 2012, Gary McGuire, Bastian Tugemann, and Gilles Civario from University College Dublin used a mix of mathematics and computer power to prove that the minimum is indeed 17, as posited by the authors. (A result to feature prominently in the revised edition, if any!)

“We are curious for a living.” (p.191)

To conclude, and to be fair with the authors, the book reads nicely (on high quality glossy paper), once you limit your expectations to see some links between maths and Sudokus, it offers a lot of Sudokus and related puzzles, with solutions at the back of the book, and, above all, it teaches to some degree mathematical reasoning by running complete arguments on 4×4 Shidokus and extrapolating the results to the 9×9 Sudokus (or not, as in the case of polynomials where the extrapolation does not work, Section 8.2). Worth perusing on your way to work, trying to complete the puzzle at hand before the next stop!

As a postultimate remark, a paper by Hiroshi Watanabe from the University of Tokyo was arXived a few days ago: it contains further links about the mathematical properties of Sudokus, incl. one with a nine-state Potts model, but mostly a simulated annealing algorithm to find a “difficult” Sudoku. Contrary to my early attempt, this algorithm explores the space of all Sudoku puzzles, thus moves from one Sudoku to another at each iteration (“with the Metropolis criterion with the Boltzmann weight”, I wonder why Boltzmann?!).The hardest sudoku found by this method is represented below: it has a depth of 10 and would require 50,000 backtracking attempts to solve! Just “impossible to solve by hand”. (It took the equivalent of 11 cpu-core-years to create it.) As pointed out to me by Anthony Leverrier, from INRIA, the author added in the second version of his arXiv preprint that the puzzle can be easily solved by hand… So you may give it a try.

The hardest Sudoku ever, by H. Watanabe