## Le Monde puzzle [#956]

Posted in Kids, R with tags , , , on April 5, 2016 by xi'an A Le Monde mathematical puzzle with little need of R programming but ending up being rather fascinating:

Does there exist a function f from N to N such that (i) f is (strictly) increasing, (ii) f(n)≥n, and (iii) f²(n)=f(f(n))=3n?

Indeed, the three constraints imply (a) f²(0)=0, hence that that f(0)=0, (b) f(1)=2 as it can be neither 1 (else f²(1) would be equal to 1, not to 3) nor 3 (else f(3)=f²(1)=3 would contradict both f(3)>f(1) and f²(3)=9), and thus (c) f(2)=f²(1)=3. Those three two initial values are actually sufficient to determine all subsequent values of f(n) as there are exactly three possible values between f²(n)=3n and f²(n+1)=3(n+1)=3n+3. (Kind of shaky argument, I must say, but each time an integer n has no antecedent in the previous f(m)’s, there are exactly two possible and successive values for two indeterminate f(n)’s… The resolution in Le Monde [published this afternoon] starts from the observation that f(3p)=2 3p and thus that f(2 3p)=3p+1, which leaves a single possible image for the values in between 3p and 2 3p.) It however provides no discussion whatsoever on the maths behind this freak function. To plot the above function, I used the R code below:

```fillin&lt;-function(N=100){
vals=rep(0,N)
vals=2
for (i in 2:N){
#anc for antecedent, f(anc)=i
u=0;anc=which(vals==i)
#no antecedent
if (length(anc)==0){
u=1; anc=which(vals==i-1)}
if (length(anc)==0){
u=2; anc=which(vals==i-2)}
vals[i]=3*anc*(u==0)+(u&gt;0)*(vals[i-u]+u)}
} ```

The graph has many interesting features, one of which that explains why I did not plot the axes, namely that it is somewhat self-reproducing, in that the plot for N=10³ has the same pattern as the plot for N=10⁵, with a few long linear parts around the line y=√3x (since f is essentially an integer-valued version of √3x). Each linear part is about 3 times longer than the earlier one, with slopes of b=1 and b=3 alternating.

While the resolution is obvious for f²(n)=4n, since f(n)=√4n=2n, there is no single resolution when f²(n)=5n. (Maybe there is one if instead the third condition is that f⁴(n)=5n… A new puzzle for the reader.)

## Special Issue of ACM TOMACS on Monte Carlo Methods in Statistics

Posted in Books, R, Statistics, University life with tags , , , , , , , , , , , , on December 10, 2012 by xi'an

As posted here a long, long while ago, following a suggestion from the editor (and North America Cycling Champion!) Pierre Lécuyer (Université de Montréal), Arnaud Doucet (University of Oxford) and myself acted as guest editors for a special issue of ACM TOMACS on Monte Carlo Methods in Statistics. (Coincidentally, I am attending a board meeting for TOMACS tonight in Berlin!) The issue is now ready for publication (next February unless I am confused!) and made of the following papers:

 * Massive parallelization of serial inference algorithms for a complex generalized linear model MARC A. SUCHARD, IVAN ZORYCH, PATRICK RYAN, DAVID MADIGAN Abstract *Convergence of a Particle-based Approximation of the Block Online Expectation Maximization Algorithm SYLVAIN LE CORFF and GERSENDE FORT Abstract * Efficient MCMC for Binomial Logit Models AGNES FUSSL, SYLVIA FRÜHWIRTH-SCHNATTER, RUDOLF FRÜHWIRTH Abstract * Adaptive Equi-Energy Sampler: Convergence and Illustration AMANDINE SCHRECK and GERSENDE FORT and ERIC MOULINES Abstract * Particle algorithms for optimization on binary spaces CHRISTIAN SCHÄFER Abstract * Posterior expectation of regularly paved random histograms RAAZESH SAINUDIIN, GLORIA TENG, JENNIFER HARLOW, and DOMINIC LEE Abstract * Small variance estimators for rare event probabilities MICHEL BRONIATOWSKI and VIRGILE CARON Abstract * Self-Avoiding Random Dynamics on Integer Complex Systems FIRAS HAMZE, ZIYU WANG, and NANDO DE FREITAS Abstract * Bayesian learning of noisy Markov decision processes SUMEETPAL S. SINGH, NICOLAS CHOPIN, and NICK WHITELEY Abstract

Here is the draft of the editorial that will appear at the beginning of this special issue. (All faults are mine, of course!) Continue reading