Archive for integer valued functions

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.lemonde956To plot the above function, I used the R code below:

fillin<-function(N=100){
 vals=rep(0,N)
 vals[1]=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>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
*Convergence of a Particle-based Approximation of the Block Online Expectation Maximization Algorithm
SYLVAIN LE CORFF and GERSENDE FORT
* Efficient MCMC for Binomial Logit Models
AGNES FUSSL, SYLVIA FRÜHWIRTH-SCHNATTER, RUDOLF FRÜHWIRTH
* Adaptive Equi-Energy Sampler: Convergence and Illustration
AMANDINE SCHRECK and GERSENDE FORT and ERIC MOULINES
* Particle algorithms for optimization on binary spaces
CHRISTIAN SCHÄFER
* Posterior expectation of regularly paved random histograms
RAAZESH SAINUDIIN, GLORIA TENG, JENNIFER HARLOW, and DOMINIC LEE
* Small variance estimators for rare event probabilities
MICHEL BRONIATOWSKI and VIRGILE CARON
* Self-Avoiding Random Dynamics on Integer Complex Systems
FIRAS HAMZE, ZIYU WANG, and NANDO DE FREITAS
* Bayesian learning of noisy Markov decision processes
SUMEETPAL S. SINGH, NICOLAS CHOPIN, and NICK WHITELEY

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

Follow

Get every new post delivered to your Inbox.

Join 1,079 other followers