## Le Monde puzzle [#1164]

Posted in Books, Kids, R with tags , , , , , , , , , , , , , on November 16, 2020 by xi'an 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))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.

## missing digit in a 114 digit number [a Riddler’s riddle]

Posted in R, Running, Statistics with tags , , , , , , , on January 31, 2019 by xi'an

A puzzling riddle from The Riddler (as Le Monde had a painful geometry riddle this week): this number with 114 digits

530,131,801,762,787,739,802,889,792,754,109,70?,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000

is missing one digit and is a product of some of the integers between 2 and 99. By comparison, 76! and 77! have 112 and 114 digits, respectively. While 99! has 156 digits. Using WolframAlpha on-line prime factor decomposition code, I found that only 6 is a possible solution, as any other integer between 0 and 9 included a large prime number in its prime decomposition: However, I thought anew about it when swimming the next early morning [my current substitute to morning runs] and reasoned that it was not necessary to call a formal calculator as it is reasonably easy to check that this humongous number has to be divisible by 9=3×3 (for else there are not enough terms left to reach 114 digits, checked by lfactorial()… More precisely, 3³³x33! has 53 digits and 99!/3³³x33! 104 digits, less than 114), which means the sum of all digits is divisible by 9, which leads to 6 as the unique solution.

## Randomness through computation

Posted in Books, Statistics, University life with tags , , , , , , , , , , , , , , on June 22, 2011 by xi'an A few months ago, I received a puzzling advertising for this book, Randomness through Computation, and I eventually ordered it, despite getting a rather negative impression from reading the chapter written by Tomasso Toffoli… The book as a whole is definitely perplexing (even when correcting for this initial bias) and I would not recommend it to readers interested in simulation, in computational statistics or even in the philosophy of randomness. My overall feeling is indeed that, while there are genuinely informative and innovative chapters in this book, some chapters read more like newspeak than scientific material (mixing the Second Law of Thermodynamics, Gödel’s incompleteness theorem, quantum physics, and NP completeness within the same sentence) and do not provide a useful entry on the issue of randomness. Hence, the book is not contributing in a significant manner to my understanding of the notion. (This post also appeared on the Statistics Forum.) Continue reading

## Spam books?!

Posted in Books, Statistics, University life with tags , , on February 3, 2011 by xi'an

Rather (too) frequently, I get those unsolicited (hence spam) emails from Worldscientific. The latest almost sounded like a bogus book, with some sentences clearly intriguing… I recognised some names in the list of authors so it cannot be a fake, however the way it is presented is rather puzzling. (And it includes a chapter on intrinsic randomness, by Stephen Wolfram, who showed with his bewildering New Kind of Science how far he could be from scientific writing!) So puzzling, actually, that I may order it…

RANDOMNESS THROUGH COMPUTATION

edited by Hector Zenil (Wolfram Research Inc., USA)

450pp (approx.)
978-981-4327-74-9: US\$90 / £56   US\$67.50 / £42

This review volume consists of a set of chapters written by leading scholars, most of them founders of their fields. It explores the connections of Randomness to other areas of scientific knowledge, especially its fruitful relationship to Computability and Complexity Theory, and also to areas such as Probability, Statistics, Information Theory, Biology, Physics, Quantum Mechanics, Learning Theory and Artificial Intelligence. The contributors cover these topics without neglecting important philosophical dimensions, sometimes going beyond the purely technical to formulate age old questions relating to matters such as determinism and free will.

The scope of Randomness Through Computation is novel. Each contributor shares their personal views and anecdotes on the various reasons and motivations which led them to the study of Randomness. Using a question and answer format, they share their visions from their several distinctive vantage points.

Contents:

*  Is Randomness Necessary? (R Graham)
Probability is a Lot of Logic at Once: If You Don’t Know Which One to Pick, Get’em All (T Toffoli) [available here]
*  Statistical Testing of Randomness: New and Old Procedures (A L Rukhin)
*  Scatter and Regularity Imply Benford’s Law… and More (N Gauvrit & J-P Delahaye)
*  Some Bridging Results and Challenges in Classical, Quantum and Computational Randomness (G Longo et al.)
*  Metaphysics, Metamathematics and Metabiology (G Chaitin)
*  Uncertainty in Physics and Computation (M A Stay)
*  Indeterminism and Randomness Through Physics (K Svozil)
*  The Martin-Löf-Chaitin Thesis: The Identification by Recursion Theory of the Mathematical Notion of Random Sequence (J-P Delahaye)
The Road to Intrinsic Randomness (S Wolfram)
*  Algorithmic Probability – Its Discovery – Its Properties and Application to Strong AI (R J Solomonoff)
*  Algorithmic Randomness as Foundation of Inductive Reasoning and Artificial Intelligence (M Hutter)
*  Randomness, Occam’s Razor, AI, Creativity and Digital Physics (J Schmidhuber)
*  Randomness Everywhere: My Path to Algorithmic Information Theory (C S Calude)
*  The Impact of Algorithmic Information Theory on Our Current Views on Complexity, Randomness, Information and Prediction (P Gács)
*  Randomness, Computability and Information (J S Miller)
*  Studying Randomness Through Computation (A Nies)
*  Computability, Algorithmic Randomness and Complexity (R G Downey)
*  Is Randomness Native to Computer Science? Ten Years After (M Ferbus-Zanda & S Grigorieff)
*  Randomness as Circuit Complexity (and the Connection to Pseudorandomness) (E Allender)
*  Randomness: A Tool for Constructing and Analyzing Computer Programs (A Kucera)
*  Connecting Randomness to Computation (M Li)
*  From Error-correcting Codes to Algorithmic Information Theory (L Staiger)
*  Randomness in Algorithms (O Watanabe)
*  Panel Discussion Transcription (University of Vermont, Burlington, 2007): Is the Universe Random? (C S Calude et al.)
*  What is Computation? (How) Does Nature Compute? (C S Calude et al.)

## A ridiculous email

Posted in Books, R, Statistics with tags , , , on May 11, 2010 by xi'an Wolfram Research presumably has a robot that sends automated email following postings on arXiv:

Your article, “Evidence and Evolution: A review”, caught the attention of one of my colleagues, who thought that it could be developed into an interesting Demonstration to add to the Wolfram Demonstrations Project.

The Demonstrations Project, launched alongside Mathematica 6 in May 2007, is a collection of over 5,000 interactive Demonstrations that cover myriad subjects, interests, and skill levels. The Demonstrations are free to download and manipulate thanks to Mathematica Player, which is also free. Building a Demonstration is a simple and straightforward process. If you have little or no experience with Mathematica, you may want to attend one of our free online seminars. In our S14 seminar, “Creating Demonstrations,” members of the Demonstrations team guide you step-by-step through the authoring process.

Your published Demonstrations will appear on the Wolfram Demonstrations Project website, which averages over 50,000 hits a week. We welcome any questions you might have, and look forward to seeing a Demonstration submission from you soon.

but they definitely got it all wrong there! They picked my book review of a philosophy of science book, Evidence and Evolution, where I complain of the lack of a true experiment..!