http://en.wikipedia.org/wiki/Minkowski's_question_mark_function On Mon, Apr 5, 2010 at 11:53 AM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On Monday 05 April 2010 18:37:41 Allan Wechsler wrote:
Steve Witham's function reminded me that I have never learned the name of the following function, similar in some ways to Steve's example, but closely related to Farey sequences and continued fractions.
This is almost exactly the same thing as the function Conway discusses under the heading of "Contorted fractions" in "On numbers and games". His version maps [0,1] to [0,1] instead of to [0,oo], and he then makes f(x+1)=f(x)+1 to extend it to all the reals. He introduces it as follows: consider a two-player game in which a position consists of some real numbers, and a move consists of replacing one of these numbers with another, whose denominator is strictly smaller (or, if the number is already an integer so that that's impossible, with another integer of strictly smaller absolute value). One player is allowed to do this only when it increases the number, the other only when it decreases it. Irrational numbers are deemed to have infinitely large denominator, of course.
His function -- mapping a game consisting of a single number to its combinatorial-game-theoretic value -- is almost the same thing as the inverse of your function. It maps (1+sqrt5)/2 to 5/3, for instance.
There's a not-so-obviously-inductive way to compute the function, in either direction. Runs of 1s and 0s in the binary expansion of the number correspond directly to the numbers in the continued fraction expansion, with some minor complications at the start.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com