[math-fun] A different fun function
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. Let f(0) = 0/1, and f(1) = 1/0. Forgive me for playing fast and loose with infinities; you'll see what I'm about in a moment. I'm going to give a recipe for calculating f at dyadic rationals; then I'm pretty sure f can be "completed" continuously to all reals between 0 and 1. f is going to be strictly increasing, and its range is all positive reals. Suppose we have a dyadic rational p/2^n in lowest terms (so p is odd). p/2^n is bracketed by simpler dyadic rationals, L = (p-1)/2^n and R = (p+1)/2^n, which when reduced to lowest terms will have denominators less than 2^n. Suppose we know f(L) = a/b, f(R) = c/d; then define f(p/2^n) = f((L+R)/2) = (a+c)/(b+d). This is the standard Farey mediant between f(L) and f(R). Note that 1/0 works perfectly well as a "bookend" for these mediants, which are guaranteed to be in lowest terms. Example: Find f(3/8). First we must find f(1/4) and f(1/2). f(1/2) is the mediant of 0/1 and 1/0, or 1/1. Now f(1/4) = 1/2, and f(3/8) = (1+1)/(2+1) = 2/3. Exercise: show that f(2/3) = (sqrt(5) + 1)/2. The function f stretches the dyadic rationals to cover all the rationals; it stretches the rationals to cover all the quadratic rationals. I have never seen a graph of it, but I'm sure it's fractally delicious.
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
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
On Monday 05 April 2010 20:23:40 Mike Stay wrote:
http://en.wikipedia.org/wiki/Minkowski's_question_mark_function
... leading to http://en.wikipedia.org/wiki/De_Rham_curve which nicely answers Allan's remark about fractals. -- g
I've been doing my best to ignore this thread, but it's beginning to get to me ... The de Rham curve is defined in terms of a pair of contracting maps and binary expansion. Presumably k maps and expansion to base k would work in just the same way --- with even more mind-boggling options? WFL On 4/6/10, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On Monday 05 April 2010 20:23:40 Mike Stay wrote:
http://en.wikipedia.org/wiki/Minkowski's_question_mark_function
... leading to http://en.wikipedia.org/wiki/De_Rham_curve which nicely answers Allan's remark about fractals.
--
g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tuesday 06 April 2010 02:25:07 Fred lunnon wrote:
The de Rham curve is defined in terms of a pair of contracting maps and binary expansion. Presumably k maps and expansion to base k would work in just the same way --- with even more mind-boggling options?
You've almost certainly seen at least one example of this: base 3, let each map be contraction by a factor of 2 towards one corner of an equilateral triangle; the result is the Sierpinski gasket. More generally, taking all the maps to be linear gives you an IFS. -- g
This sounds like an enumeration of the nodes in a Stern-Brocot tree: http://www.cut-the-knot.org/blue/Stern.shtml http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree Tom Allan Wechsler writes:
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.
participants (5)
-
Allan Wechsler -
Fred lunnon -
Gareth McCaughan -
Mike Stay -
Tom Karzes