Options

Just For Fun 1

Hi! We've got an amazing crowd of interesting people here. We've got about 200 students registered, and I still have ten more applications to look at - they keep flooding in. I've been so busy registering people to the Azimuth Forum, saying hi, writing lectures and discussing the material that I'm a bit burnt out today.

A bunch of you have probably not had time to digest the material on Galois connections. The next lecture will be on Monday. I will spend more time explaining those, with more examples and applications.

But right now I'd like to pose a little puzzle, completely unrelated to the course material, to keep you entertained over the weekend.

Here's an interesting function:

$$ f(x) = \frac{1}{2\lfloor x \rfloor - x + 1} $$ \(\lfloor x \rfloor\) is the floor function: it's the largest integer less than or equal to \(x\). For example,

$$ \lfloor 1.999 \rfloor = 1, \qquad \lfloor 2 \rfloor = 2 $$ We're starting to see the floor function in our discussion of Galois connections, and we'll see more of it, but that's not the point here. Here I want you to take the number \(0\) and keep hitting it with this function \(f\). I'll start you off:

$$ 0 $$ $$ f(0) = \frac{1}{2\lfloor 0 \rfloor - 0 + 1} = 1 $$ $$ f(1) = \frac{1}{2\lfloor 1 \rfloor - 1 + 1} = \frac{1}{2} $$ $$ f(1/2) = \frac{1}{2\lfloor \frac{1}{2} \rfloor - \frac{1}{2} + 1} = 2 $$ $$ f(2) = \frac{1}{2\lfloor 2 \rfloor - 2 + 1} = \frac{1}{3} $$ $$ f(1/3) = \frac{1}{2\lfloor \frac{1}{3} \rfloor - \frac{1}{3} + 1} = \frac{3}{2} $$ $$ f(3/2) = \frac{1}{2\lfloor \frac{3}{2} \rfloor - \frac{3}{2} + 1} = \frac{2}{3} $$ $$ f(2/3) = \frac{1}{2\lfloor \frac{2}{3} \rfloor - \frac{2}{3}+ 1} = 3 $$ So far we're getting this sequence:

$$ \frac{0}{1}, \frac{1}{2}, \frac{2}{1} , \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1} , \dots $$ Here I'm writing all the numbers as fractions in lowest terms, because this will help you see some patterns. And my puzzle is quite open-ended:

Puzzle: What are the interesting properties of this sequence? What patterns can you find?

If you already know from your studies of math, please don't answer! Let others have the fun of discovering everything for themselves! One can discover a lot of amazing things by pondering this sequence.

Since a lot of you are programmers, the first step might be to compute the first hundred terms and show them to us! I urge you to show them in the way I just did, including writing numbers like \(3\) as \(\frac{3}{1}\).

Comments

  • 1.
    edited March 31

    This should be the first one hundred terms (if I got the LaTeX magic right):

    $$ \frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, $$ $$ \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, $$ $$ \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, \frac{1}{7}, \frac{7}{6}, \frac{6}{11}, \frac{11}{5}, \frac{5}{14}, \frac{14}{9}, \frac{9}{13}, \frac{13}{4}, \frac{4}{15}, \frac{15}{11}, \frac{11}{18}, \frac{18}{7}, $$ $$\frac{7}{17}, \frac{17}{10}, \frac{10}{13}, \frac{13}{3}, \frac{3}{14}, \frac{14}{11}, \frac{11}{19}, \frac{19}{8}, \frac{8}{21}, \frac{21}{13}, \frac{13}{18}, \frac{18}{5}, \frac{5}{17}, \frac{17}{12}, \frac{12}{19}, \frac{19}{7}, \frac{7}{16}, \frac{16}{9}, \frac{9}{11}, \frac{11}{2}, \frac{2}{11}, \frac{11}{9}, \frac{9}{16}, \frac{16}{7} $$

    Comment Source:This should be the first one hundred terms (if I got the LaTeX magic right): $$ \frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, $$ $$ \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, $$ $$ \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, \frac{1}{7}, \frac{7}{6}, \frac{6}{11}, \frac{11}{5}, \frac{5}{14}, \frac{14}{9}, \frac{9}{13}, \frac{13}{4}, \frac{4}{15}, \frac{15}{11}, \frac{11}{18}, \frac{18}{7}, $$ $$\frac{7}{17}, \frac{17}{10}, \frac{10}{13}, \frac{13}{3}, \frac{3}{14}, \frac{14}{11}, \frac{11}{19}, \frac{19}{8}, \frac{8}{21}, \frac{21}{13}, \frac{13}{18}, \frac{18}{5}, \frac{5}{17}, \frac{17}{12}, \frac{12}{19}, \frac{19}{7}, \frac{7}{16}, \frac{16}{9}, \frac{9}{11}, \frac{11}{2}, \frac{2}{11}, \frac{11}{9}, \frac{9}{16}, \frac{16}{7} $$
  • 2.
    edited March 31

    Great, Andre! I edited your LaTeX so the list doesn't shoot off the page.

    Now everyone can see how curious this sequence is! It becomes even more interesting if one leaves out the first term and writes the rest like this:

    $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$ $$ \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, $$ and so on.

    Comment Source:Great, Andre! I edited your LaTeX so the list doesn't shoot off the page. Now everyone can see how curious this sequence is! It becomes even more interesting if one leaves out the first term and writes the rest like this: $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$ $$ \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, $$ and so on.
  • 3.

    What a weird function! Here are a few scattered observations and curiosities that came to mind as I was playing around with it:

    If you plot the first few thousand terms, \(f^n(0)\) appears to be \(O(\log(n))\):

    image

    This is consilient with the arrangement of the terms John (#2) posted: in general, it takes 2^n terms to go from 1/n to n/1. The linearly increasing subsequence \(\frac{1}{1}, \frac{2}{1}, \frac{3}{1}\ldots\) occurs at times that are coming exponentially further apart, so you'd expect growth to be logarithmic in general.

    For convenience, let's define \(g(n) = f^n(0)\). So \(f\) is a function from \(\mathbb{Q}\) to \(\mathbb{Q}\), and \(g: \mathbb{N} \rightarrow \mathbb{Q}\) is a sequence of iterates starting at 0.

    One natural question to ask is: "is \(g\) surjective onto \(\mathbb{Q}\)?" I.e., for every \(\frac{p}{q} \in \mathbb{Q}\), is there an \(n \in \mathbb{N}\) such that \(g(n) = \frac{p}{q}\)? From numerical evidence, I conjecture "no". For example, here is a plot of the first ten thousand iterates, with the numerator along the x axis and the denominator along the y:

    image

    So not only do the iterates not appear to be filling in \(\mathbb{N}^2\) in any systematic way, but the plot appears to show some kind of fractal bifurcation structure. What's up with that? Considering each rational number \frac{p}{q}\) as a point \((p, q) \in \mathbb{N}^2\), what is the image of \(g\)? (NB we haven't shown yet that \(g(n) \geq 0\) for all \(n\), so it's slightly unsporting to even talk about \(\mathbb{N}^2\) at this point, but one gets the idea.)

    Comment Source:What a weird function! Here are a few scattered observations and curiosities that came to mind as I was playing around with it: If you plot the first few thousand terms, \\(f^n(0)\\) appears to be \\(O(\log(n))\\): <img src="https://i.imgur.com/QfemWuH.png"> This is consilient with the arrangement of the terms John (#2) posted: in general, it takes 2^n terms to go from 1/n to n/1. The linearly increasing subsequence \\(\frac{1}{1}, \frac{2}{1}, \frac{3}{1}\ldots\\) occurs at times that are coming exponentially further apart, so you'd expect growth to be logarithmic in general. For convenience, let's define \\(g(n) = f^n(0)\\). So \\(f\\) is a function from \\(\mathbb{Q}\\) to \\(\mathbb{Q}\\), and \\(g: \mathbb{N} \rightarrow \mathbb{Q}\\) is a sequence of iterates starting at 0. One natural question to ask is: "is \\(g\\) surjective onto \\(\mathbb{Q}\\)?" I.e., for every \\(\frac{p}{q} \in \mathbb{Q}\\), is there an \\(n \in \mathbb{N}\\) such that \\(g(n) = \frac{p}{q}\\)? From numerical evidence, I conjecture "no". For example, here is a plot of the first ten thousand iterates, with the numerator along the x axis and the denominator along the y: <img src="https://i.imgur.com/tQxJ8RA.png"> So not only do the iterates not appear to be filling in \\(\mathbb{N}^2\\) in any systematic way, but the plot appears to show some kind of fractal bifurcation structure. What's up with that? Considering each rational number \\frac{p}{q}\\) as a point \\((p, q) \in \mathbb{N}^2\\), what is the image of \\(g\\)? (NB we haven't shown yet that \\(g(n) \geq 0\\) for all \\(n\\), so it's slightly unsporting to even talk about \\(\mathbb{N}^2\\) at this point, but one gets the idea.)
  • 4.

    If this is what I think it is I learned about it two weeks ago but the math escaped me at the time and I haven't revisited it. But it looks ever so slightly different, so maybe the match here can help demystify.

    Comment Source:If this is what I think it is I learned about it two weeks ago but the math escaped me at the time and I haven't revisited it. But it looks ever so slightly different, so maybe the match here can help demystify.
  • 5.
    edited April 1

    Nice graphics, Patrick O'Neil!

    in general, it takes \(2^n\) terms to go from 1/n to n/1.

    It looks that way. Can anyone here prove this, who hasn't already read all about this stuff? I think attempting to prove this could lead to a lot of extra insights.

    One natural question to ask is: "is \(g\) surjective onto \(\mathbb{Q}\)?" I.e., for every \(\frac{p}{q} \in \mathbb{Q}\), is there an \(n \in \mathbb{N}\) such that \(g(n) = \frac{p}{q}\)?

    Of course you mean not \(\mathbb{Q}\) but the nonnegative rationals. This is a very interesting question.

    From numerical evidence, I conjecture "no".

    What's the simplest nonnegative rational you can find that appears not to be of the form \(g(n)\)?

    (Again, I think answering this would lead to a lot of extra insights.)

    Comment Source:Nice graphics, Patrick O'Neil! > in general, it takes \\(2^n\\) terms to go from 1/n to n/1. It looks that way. Can anyone here prove this, who hasn't already read all about this stuff? I think attempting to prove this could lead to a lot of extra insights. > One natural question to ask is: "is \\(g\\) surjective onto \\(\mathbb{Q}\\)?" I.e., for every \\(\frac{p}{q} \in \mathbb{Q}\\), is there an \\(n \in \mathbb{N}\\) such that \\(g(n) = \frac{p}{q}\\)? Of course you mean not \\(\mathbb{Q}\\) but the nonnegative rationals. This is a very interesting question. > From numerical evidence, I conjecture "no". What's the simplest nonnegative rational you can find that appears not to be of the form \\(g(n)\\)? (Again, I think answering this would lead to a lot of extra insights.)
  • 6.
    edited April 1

    I'm starting to think that \(g\) is in fact surjective onto \(\mathbb{Q}\). I tried to prove it using \( f^{-1}(x) = 2\lceil 1/x-1 \rceil - (1/x-1) \), which can be understood by noting that \( 2\lfloor x \rfloor - x \) "flips" \(x\) over it's floor (ex: flips \(\frac{5}{4}\) over \(\frac{4}{4}\) to \(\frac{3}{4}\)) so \( 2\lceil y \rceil - y \) reverses by "flipping" \(y\) over it's ceil, but haven't been successful without a good definition of "simplest nonnegative rational": https://www.wolframcloud.com/objects/14fd39f3-1c50-4361-8bf7-5957ad3c4686

    Comment Source:I'm starting to think that \\(g\\) is in fact surjective onto \\(\mathbb{Q}\\). I tried to prove it using \\( f^{-1}(x) = 2\lceil 1/x-1 \rceil - (1/x-1) \\), which can be understood by noting that \\( 2\lfloor x \rfloor - x \\) "flips" \\(x\\) over it's floor (ex: flips \\(\frac{5}{4}\\) over \\(\frac{4}{4}\\) to \\(\frac{3}{4}\\)) so \\( 2\lceil y \rceil - y \\) reverses by "flipping" \\(y\\) over it's ceil, but haven't been successful without a good definition of "simplest nonnegative rational": https://www.wolframcloud.com/objects/14fd39f3-1c50-4361-8bf7-5957ad3c4686
  • 7.

    Removing first row of the triangle.
    then..

    If I add elements of every row (again, except 1st), I get

    2/2

    47/2

    95/2


    Every row has 2^row_number elements.

    2 in some power, usually indicates the number of elements in a power set.

    Therefore, If I look at the 3rd row (where the sum is equal to 95/2). I can interpret this as, there was initially set of 5 elements. Its power set has 32 elements.

    --

    Now thinking, what these 5 elements can look like, (and how they relate to the 4 element-set of the previous row).

    --

    I cannot think, of a killer observation here, yet :-). Need to break at 3:21am.

    Comment Source:Removing first row of the triangle. then.. If I add elements of every row (again, except 1st), I get 2/2 47/2 95/2 --- Every row has 2^row_number elements. 2 in some power, usually indicates the number of elements in a power set. Therefore, If I look at the 3rd row (where the sum is equal to 95/2). I can interpret this as, there was initially set of 5 elements. Its power set has 32 elements. -- Now thinking, what these 5 elements can look like, (and how they relate to the 4 element-set of the previous row). -- I cannot think, of a killer observation here, yet :-). Need to break at 3:21am.
  • 8.

    Does this enumerate all rational numbers? If so it results in a mapping between the rational number and the natural numbers.

    Comment Source:Does this enumerate all rational numbers? If so it results in a mapping between the rational number and the natural numbers.
  • 9.

    Of course this sequence doesn't enumerate any negative numbers. So, the puzzles are:

    • Can you find a nonnegative rational number that's not in this sequence?

    and

    • Can you find a nonnegative rational number that shows up in this sequence twice?
    Comment Source:Of course this sequence doesn't enumerate any _negative_ numbers. So, the puzzles are: * Can you find a nonnegative rational number that's not in this sequence? and * Can you find a nonnegative rational number that shows up in this sequence twice?
  • 10.
    edited April 1

    Well we couldn't get the same nonnegative rational number twice. There would have to be a first such number (call it \(x\)), and it would have to be reachable from 2 different values \(f(y) = x, f(z) = x, y \neq z\) which is impossible because \(f\) is injective, with inverse \( f^{-1}(x) = 2\lceil 1/x-1 \rceil - (1/x-1) \), and \( f^{-1}(0) \) is undefined.

    Comment Source:Well we couldn't get the same nonnegative rational number twice. There would have to be a first such number (call it \\(x\\)), and it would have to be reachable from 2 different values \\(f(y) = x, f(z) = x, y \neq z\\) which is impossible because \\(f\\) is injective, with inverse \\( f^{-1}(x) = 2\lceil 1/x-1 \rceil - (1/x-1) \\), and \\( f^{-1}(0) \\) is undefined.
  • 11.
    edited April 1

    Nice, Alex. So, the only question is whether we get all the nonnegative rational numbers.

    This is one of those questions that's not good to attack directly. It's better to sneak up on it gradually, by noticing all the patterns here:

    $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$ $$ \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, $$ etcetera, and figuring out why these patterns work as they do.

    Comment Source:Nice, Alex. So, the only question is whether we get _all_ the nonnegative rational numbers. This is one of those questions that's not good to attack directly. It's better to sneak up on it gradually, by noticing all the patterns here: $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$ $$ \frac{1}{6}, \frac{6}{5}, \frac{5}{9}, \frac{9}{4}, \frac{4}{11}, \frac{11}{7}, \frac{7}{10}, \frac{10}{3}, \frac{3}{11}, \frac{11}{8}, \frac{8}{13}, \frac{13}{5}, \frac{5}{12}, \frac{12}{7}, \frac{7}{9}, \frac{9}{2}, \frac{2}{9}, \frac{9}{7}, \frac{7}{12}, \frac{12}{5}, \frac{5}{13}, \frac{13}{8}, \frac{8}{11}, \frac{11}{3}, \frac{3}{10}, \frac{10}{7}, \frac{7}{11}, \frac{11}{4}, \frac{4}{9}, \frac{9}{5}, \frac{5}{6}, \frac{6}{1}, $$ etcetera, and figuring out why these patterns work as they do.
  • 12.

    I'm not sure how I missed this before, but \(f(\frac{a}{b}) = \frac{b}{c}\) implies \(f(f(\frac{a}{a+b})) = \frac{b}{b+c}\). For example, in the 4th row \(\frac{1}{4}\) goes to \(\frac{4}{3}\) in one step, and in the next row \(\frac{1}{5}\) goes to \(\frac{4}{7}\) in 2 steps. Proving this would go a long way towards explaining the doubling behavior.

    Comment Source:I'm not sure how I missed this before, but \\(f(\frac{a}{b}) = \frac{b}{c}\\) implies \\(f(f(\frac{a}{a+b})) = \frac{b}{b+c}\\). For example, in the 4th row \\(\frac{1}{4}\\) goes to \\(\frac{4}{3}\\) in one step, and in the next row \\(\frac{1}{5}\\) goes to \\(\frac{4}{7}\\) in 2 steps. Proving this would go a long way towards explaining the doubling behavior.
  • 13.

    Alex - nice!!!

    I can't resist mentioning that there are lots of patterns in that list of numbers the way I keep drawing it, which nobody has mentioned yet. Many of them are easy to spot, even if not necessarily so easy to prove.

    Comment Source:Alex - nice!!! I can't resist mentioning that there are lots of patterns in that list of numbers the way I keep drawing it, which nobody has mentioned yet. Many of them are easy to spot, even if not necessarily so easy to prove.
  • 14.

    OK, here's a pattern I don't think has been noted explicitly: we can get the list of reciprocals of the sequence (rather than the sequence itself) by reading each row right to left instead of left to right.

    Comment Source:OK, here's a pattern I don't think has been noted explicitly: we can get the list of reciprocals of the sequence (rather than the sequence itself) by reading each row right to left instead of left to right.
  • 15.
    edited April 3

    So the generating formula creates the top-down left-right sequence of the Calkin-Wilf Tree, which is the binary tree sequence that Prof Baez has kindly noted for us. The general pattern for tree propagation is as follows :

    Pattern

    The left child is a fraction less than 1, and the right child is a fraction greater than 1.

    So there is an elegant solution to the question whether this every rational in the sequence is reduced found on this page.

    It relies on the fact that the gcd(p,q) = gcd(p,p+q) = gcd(p,p-q) if p>q. Its easy to see why that is since they both have common factors which can be factored out again. But since each generation of children is created via adding the numerator to the denominator, every child will have the same gcd as their parent. And it just so happens that the ultimate ancestor of the whole tree happens to be one so the whole tree has a gcd of 1! See the graphic below:

    Unique

    The question of whether the sequence covers the whole positive rationals is also elegantly explained on this page.

    Since we know how to propagate down the tree we can also go back up the tree as long as we differentiate if the rational is > or < 1 i.e. p>q, or q>p. Remember that the left child had a sum in its denominator and is <1. So if q>p then we find its parent simply by subtracting the numerator from the denominator and keeping the numerator. So we can repeat this process until we hit the ultimate ancestor 1/1. So we have found that a random p/q will have a unique path up the binary tree and therefore all positive rationals are covered in the tree. Check out the graphic below:

    Path

    The most interesting pattern I found on this sequence is that the Calkin-Wilf tree is the bit reversal permutation of the Stern Brocot tree, which is binary search tree of the positive rationals. It is sort like doing a discrete Fourier transform on Stern Brocot ordered time domain into its frequency domain separating out the even and odd components (in this case p/q>1, p/q<1). It essentially permutes the Stern Brocot tree that is ordered by ordinary metric (in each row) into equivalence classes based on their p-adic distances. So a linear order of 1,2,3,4,5,6,7,8, would get reordered to (((1,5),(3,7)),((2,6),(4,8))). But the neat thing about this is that when we rearrange the Stern Brocot tree, for some reason beyond my comprehension, the denominator gets passed on to the next numbers numerator creating a kind of baton pass wave dance.

    There are other nice patterns in this tree, one of which is that the maxima of each row is a Fibonacci number which always happens land on a certain path on the tree.

    Comment Source:So the generating formula creates the top-down left-right sequence of the Calkin-Wilf Tree, which is the binary tree sequence that Prof Baez has kindly noted for us. The general pattern for tree propagation is as follows : ![Pattern](http://aether.co.kr/wp-content/uploads/calkin-wilf1.jpg) The left child is a fraction less than 1, and the right child is a fraction greater than 1. So there is an elegant solution to the question whether this every rational in the sequence is reduced found on this [page](https://mathlesstraveled.com/2008/02/06/recounting-the-rationals-part-iv/). It relies on the fact that the gcd(p,q) = gcd(p,p+q) = gcd(p,p-q) if p>q. Its easy to see why that is since they both have common factors which can be factored out again. But since each generation of children is created via adding the numerator to the denominator, every child will have the same gcd as their parent. And it just so happens that the ultimate ancestor of the whole tree happens to be one so the whole tree has a gcd of 1! See the graphic below: ![Unique](http://aether.co.kr/wp-content/uploads/calkin-wilf3.jpg) The question of whether the sequence covers the whole positive rationals is also elegantly explained on this [page](https://mathlesstraveled.com/2008/01/24/recounting-the-rationals-part-iii/). Since we know how to propagate down the tree we can also go back up the tree as long as we differentiate if the rational is > or < 1 i.e. p>q, or q>p. Remember that the left child had a sum in its denominator and is <1. So if q>p then we find its parent simply by subtracting the numerator from the denominator and keeping the numerator. So we can repeat this process until we hit the ultimate ancestor 1/1. So we have found that a random p/q will have a unique path up the binary tree and therefore all positive rationals are covered in the tree. Check out the graphic below: ![Path](http://aether.co.kr/wp-content/uploads/calkin-wilf2.jpg) The most interesting pattern I found on this sequence is that the Calkin-Wilf tree is the bit reversal permutation of the Stern Brocot tree, which is binary search tree of the positive rationals. It is sort like doing a discrete Fourier transform on Stern Brocot ordered time domain into its frequency domain separating out the even and odd components (in this case p/q>1, p/q<1). It essentially permutes the Stern Brocot tree that is ordered by ordinary metric (in each row) into equivalence classes based on their p-adic distances. So a linear order of 1,2,3,4,5,6,7,8, would get reordered to (((1,5),(3,7)),((2,6),(4,8))). But the neat thing about this is that when we rearrange the Stern Brocot tree, for some reason beyond my comprehension, the denominator gets passed on to the next numbers numerator creating a kind of baton pass wave dance. There are other nice patterns in this tree, one of which is that the maxima of each row is a Fibonacci number which always happens land on a certain path on the tree.
  • 16.
    edited April 2

    That's really cool. It seems so obvious in retrospect: propagating up the tree corresponds to following the Euclidean Algorithm. Now to figure out how this emerges from the equation.

    Also Michael, you can in-line MathJax like \\( \frac{1}{2} \\) to get \( \frac{1}{2} \). You can also can also click the gear and "View Source" on any comment to steal syntax. Note that sometimes MathJax doesn't load properly, so check your browser console for errors if that still doesn't work.

    Comment Source:That's really cool. It seems so obvious in retrospect: propagating up the tree corresponds to following the Euclidean Algorithm. Now to figure out how this emerges from the equation. Also Michael, you can in-line MathJax like `\\( \frac{1}{2} \\)` to get \\( \frac{1}{2} \\). You can also can also click the gear and "View Source" on any comment to steal syntax. Note that sometimes MathJax doesn't load properly, so check your browser console for errors if that still doesn't work.
  • 17.
    edited April 2

    Building off of Alex's nice observation, I think I can prove: \( f(\frac{a}{b}) = \frac{b}{c} \Rightarrow f(f(\frac{a}{a + b})) = \frac{b}{b + c}\).

    First let's introduce an alternate definition of \(f\) that I think is a little easier to work with. Recall that \(f\) is originally defined as:

    $$f(x) = \frac{1}{2\lfloor x \rfloor - x + 1}.$$ The floor function in the denominator is kind of annoying, so let's see if we can replace it with something that's easier (for me, at least!) to reason about. The floor of x/y is just x/y minus its fractional part, or formally:

    $$\lfloor \frac{x}{y} \rfloor = \frac{x}{y} - \frac{x\mod y}{y}.$$ Plugging this in and rearranging, we get: $$f(\frac{x}{y}) = \frac{y}{x + y - 2(x \mod y)}.$$ Now let's prove the claim. Suppose: $$f(\frac{a}{b}) = \frac{b}{a + b - 2(a \mod b)} \equiv \frac{b}{c}.$$ Now $$\begin{align}f(\frac{a}{a + b}) &= \frac{a + b}{a + (a + b) - 2(a \mod (a + b))}\ &= \frac{a + b}{b},\end{align},$$

    and by applying \(f\) to both sides, we get:

    $$f(f(\frac{a}{a + b}) = f(\frac{a + b}{b}) = \frac{b}{a + b + b - 2 ((a + b) \mod b)} = \frac{b}{a + b + b - 2 (a \mod b)}.$$ But by assumption, \(c = a + b - 2(a \mod b)\). Plugging this in, we obtain: \(f(f(\frac{a}{a + b})) = \frac{b}{b + c}\) as desired.

    Comment Source:Building off of Alex's nice observation, I think I can prove: \\( f(\frac{a}{b}) = \frac{b}{c} \Rightarrow f(f(\frac{a}{a + b})) = \frac{b}{b + c}\\). First let's introduce an alternate definition of \\(f\\) that I think is a little easier to work with. Recall that \\(f\\) is originally defined as: $$f(x) = \frac{1}{2\lfloor x \rfloor - x + 1}.$$ The floor function in the denominator is kind of annoying, so let's see if we can replace it with something that's easier (for me, at least!) to reason about. The floor of x/y is just x/y minus its fractional part, or formally: $$\lfloor \frac{x}{y} \rfloor = \frac{x}{y} - \frac{x\mod y}{y}.$$ Plugging this in and rearranging, we get: $$f(\frac{x}{y}) = \frac{y}{x + y - 2(x \mod y)}.$$ Now let's prove the claim. Suppose: $$f(\frac{a}{b}) = \frac{b}{a + b - 2(a \mod b)} \equiv \frac{b}{c}.$$ Now $$\begin{align}f(\frac{a}{a + b}) &= \frac{a + b}{a + (a + b) - 2(a \mod (a + b))}\\ &= \frac{a + b}{b},\end{align},$$ and by applying \\(f\\) to both sides, we get: $$f(f(\frac{a}{a + b}) = f(\frac{a + b}{b}) = \frac{b}{a + b + b - 2 ((a + b) \mod b)} = \frac{b}{a + b + b - 2 (a \mod b)}.$$ But by assumption, \\(c = a + b - 2(a \mod b)\\). Plugging this in, we obtain: \\(f(f(\frac{a}{a + b})) = \frac{b}{b + c}\\) as desired.
  • 18.

    John wrote:

    Of course you mean not ℚ but the nonnegative rationals.

    Oops, sorry, I guess I was taking it as not having been proven yet that the sequence of iterates stays positive, although I suppose that's about as immediate as the fact that the sequence stays rational. My bad!

    Comment Source:John wrote: <blockquote>Of course you mean not ℚ but the nonnegative rationals.</blockquote> Oops, sorry, I guess I was taking it as not having been proven yet that the sequence of iterates stays positive, although I suppose that's about as immediate as the fact that the sequence stays rational. My bad!
  • 19.

    This may have been mensioned. A row seemed to be curiously imbedded in the next. Also there seems to be a straightforward way of obtaining a row from the one that follows it.

    Comment Source:This may have been mensioned. A row seemed to be curiously imbedded in the next. Also there seems to be a straightforward way of obtaining a row from the one that follows it.
  • 20.

    @Dennis Lomas

    Yes, if you have one row, you can get either the row prior or the next row fairly easily.

    Each row, \(i\), has \(2^i\) elements (with \(i\) starting at 0). Using a new function \(h(i,j) = g(2^i+j)\) where \(g\) is defined by Patrick above (#3), and \(j \in [0,2^i-1]\) is used to index into the row itself.

    We can get see that \(h(i,j) = h(i,2j)\cdot h(i,2j+1)\). This is the same tree structure mentioned by Michael Hong in #15 (see the wikipedia page on the Calkin-Wilf tree for a good visualization of this).

    To get the next row, we know that \(h(i,j) = \frac{a}{b}\) for some \(a,b\). \(h(i,2j) = \frac{a}{a+b}\) and \(h(i,2j+1) = \frac{a+b}{b}\).

    Comment Source:@Dennis Lomas Yes, if you have one row, you can get either the row prior or the next row fairly easily. Each row, \\(i\\), has \\(2^i\\) elements (with \\(i\\) starting at 0). Using a new function \\(h(i,j) = g(2^i+j)\\) where \\(g\\) is defined by Patrick above (#3), and \\(j \in [0,2^i-1]\\) is used to index into the row itself. We can get see that \\(h(i,j) = h(i,2j)\cdot h(i,2j+1)\\). This is the same tree structure mentioned by Michael Hong in #15 (see the wikipedia page on the Calkin-Wilf tree for a good visualization of this). To get the *next* row, we know that \\(h(i,j) = \frac{a}{b}\\) for some \\(a,b\\). \\(h(i,2j) = \frac{a}{a+b}\\) and \\(h(i,2j+1) = \frac{a+b}{b}\\).
  • 21.
    edited April 2

    Another general observation is that the product of each row is one. This follows from the observations that the rows are bookended by \(\frac{1}{n}\) and \(\frac{n}{1}\), and the fact that \(f(\frac{p}{q}) = \frac{q}{p + q - 2(p \mod q)}\). I suppose that to complete the proof, you'd need to show that the RHS is still in lowest terms whenever the LHS is. But if \((p, q) = 1\), then so is \( (q, p + q - 2r) \), where \(r = p \mod q\), so we're ok.

    Comment Source:Another general observation is that the product of each row is one. This follows from the observations that the rows are bookended by \\(\frac{1}{n}\\) and \\(\frac{n}{1}\\), and the fact that \\(f(\frac{p}{q}) = \frac{q}{p + q - 2(p \mod q)}\\). I suppose that to complete the proof, you'd need to show that the RHS is still in lowest terms whenever the LHS is. But if \\((p, q) = 1\\), then so is \\( (q, p + q - 2r) \\), where \\(r = p \mod q\\), so we're ok.
  • 22.
    edited April 2

    Building on Dennis #19's comment:

    Take a row, and split each fraction \(\frac{p}{q}\) up into two adjacent fractions in the following row:

    $$\frac{p}{q} \rightarrow \frac{p}{p + q},\frac{p + q}{q}$$ This procedure generates the next row.

    This gets us a little way, I think, towards understanding the doubling of the terms in each row.

    EDIT:

    Assume that sequence of iterates corresponds to the infinite tree generated by the root \(\frac{1}{1}\) and the production rule \(\frac{p}{q} \rightarrow \frac{p}{p + q}, \frac{p + q}{q}\). Then each positive rational number appears once in the tree.

    Existence: Fix \(\frac{p}{q} \in \mathbb{Q}_{+}\), and we will construct the path back to the root. If \(\frac{p}{q} = 1\), then we're done. If \(\frac{p}{q} > 1\), then we can write \(\frac{p}{q} = \frac{p' + q}{q}\) for some integer \(p' > 0\), and \(\frac{p' + q}{q}\) is the right descendant of \(\frac{p'}{q}\) . Similarly, If \(\frac{p}{q} < 1\), then we can write \(\frac{p}{q} = \frac{p}{p + q'}\) for some integer \(q' > 0\), and \(\frac{p}{p + q'}\) is the left descendant of \(\frac{p}{q'}\). In either recursive case, we will have either \(p'\) strictly less than \(p\), or \(q'\) strictly less than \(q\). Neither \(p'\) nor \(q'\) can be non-positive, so the process must terminate at the root \(\frac{1}{1}\).

    Uniqueness: To see that this construction guarantees uniqueness, notice that there is no choice in traversing up the tree. So if \(\frac{p}{q}\) occurs at (p)ositions \(\pi_1\) and \(\pi_2\) in the tree, then we can use the above construction to find p(a)ths \(A_1\) and \(A_2\) back to the root. But we must have \(A_1 = A_2\) by construction, and since the paths are invertible, we must have \(A_1^{-1} = A_2^{-2}\) as well, hence \(\pi_1 = A_1^{-1}(\frac{1}{1}) = A_2^{-2}(\frac{1}{1}) = \pi_2\). Therefore the position of \(\frac{p}{q}\) is unique.

    This all hangs, of course, upon some way of connecting the original definition of \(f\) to the tree construction.

    Comment Source:Building on Dennis #19's comment: Take a row, and split each fraction \\(\frac{p}{q}\\) up into two adjacent fractions in the following row: $$\frac{p}{q} \rightarrow \frac{p}{p + q},\frac{p + q}{q}$$ This procedure generates the next row. This gets us a little way, I think, towards understanding the doubling of the terms in each row. EDIT: Assume that sequence of iterates corresponds to the infinite tree generated by the root \\(\frac{1}{1}\\) and the production rule \\(\frac{p}{q} \rightarrow \frac{p}{p + q}, \frac{p + q}{q}\\). Then each positive rational number appears once in the tree. <b>Existence</b>: Fix \\(\frac{p}{q} \in \mathbb{Q}_{+}\\), and we will construct the path back to the root. If \\(\frac{p}{q} = 1\\), then we're done. If \\(\frac{p}{q} > 1\\), then we can write \\(\frac{p}{q} = \frac{p' + q}{q}\\) for some integer \\(p' > 0\\), and \\(\frac{p' + q}{q}\\) is the right descendant of \\(\frac{p'}{q}\\) . Similarly, If \\(\frac{p}{q} < 1\\), then we can write \\(\frac{p}{q} = \frac{p}{p + q'}\\) for some integer \\(q' > 0\\), and \\(\frac{p}{p + q'}\\) is the left descendant of \\(\frac{p}{q'}\\). In either recursive case, we will have either \\(p'\\) strictly less than \\(p\\), or \\(q'\\) strictly less than \\(q\\). Neither \\(p'\\) nor \\(q'\\) can be non-positive, so the process must terminate at the root \\(\frac{1}{1}\\). <b>Uniqueness</b>: To see that this construction guarantees uniqueness, notice that there is no choice in traversing up the tree. So if \\(\frac{p}{q}\\) occurs at (p)ositions \\(\pi_1\\) and \\(\pi_2\\) in the tree, then we can use the above construction to find p(a)ths \\(A_1\\) and \\(A_2\\) back to the root. But we must have \\(A_1 = A_2\\) by construction, and since the paths are invertible, we must have \\(A_1^{-1} = A_2^{-2}\\) as well, hence \\(\pi_1 = A_1^{-1}(\frac{1}{1}) = A_2^{-2}(\frac{1}{1}) = \pi_2\\). Therefore the position of \\(\frac{p}{q}\\) is unique. This all hangs, of course, upon some way of connecting the original definition of \\(f\\) to the tree construction.
  • 23.
    edited May 21

    This is a bit out of topic, but actually the sequence `sounds' really good! If, on each row, we consider the sequence of numerators and denominators and we interpret them as note durations for two performers respectively, we find that these lines are mirrored as in table canons. I'm sharing the link of a ``mathematical rhythm'' I made. You can find it here: http://www.mariamannone.com/estratti_audio/math_rhythm.mp3 or here: https://soundcloud.com/maria-mannone/mathematical-rhythm

    These are the lines I considered:

    $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$

    Comment Source:This is a bit out of topic, but actually the sequence `sounds' really good! If, on each row, we consider the sequence of numerators and denominators and we interpret them as note durations for two performers respectively, we find that these lines are mirrored as in table canons. I'm sharing the link of a ``mathematical rhythm'' I made. You can find it here: http://www.mariamannone.com/estratti_audio/math_rhythm.mp3 or here: https://soundcloud.com/maria-mannone/mathematical-rhythm These are the lines I considered: $$ \frac{1}{1}, $$ $$ \frac{1}{2}, \frac{2}{1}, $$ $$ \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, $$ $$ \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, $$ $$ \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7}, \frac{7}{5}, \frac{5}{8}, \frac{8}{3}, \frac{3}{7}, \frac{7}{4}, \frac{4}{5}, \frac{5}{1}, $$
  • 24.
    edited May 21

    @Maria, that works surprisingly well! Now I'm wondering what happens if we interpret these fractions as intervals in pitches. Simple fractions show up a lot in the musical scale. For example, a perfect fifth interval corresponds to a \(\frac{3}{2}\) frequency ratio and sounds "really good". If we call \(\frac{1}{1}\) middle C (\(C_4\)), I think we get the sequence \(C_4, C_3, C_5, F_2, G_4, F_3, C_6\),..., which probably sounds ridiculous on its own, but maybe modding over an octave would sound interesting.

    Comment Source:@Maria, that works surprisingly well! Now I'm wondering what happens if we interpret these fractions as intervals in pitches. Simple fractions show up a lot in the musical scale. For example, a perfect fifth interval corresponds to a \\(\frac{3}{2}\\) frequency ratio and sounds "really good". If we call \\(\frac{1}{1}\\) middle C (\\(C_4\\)), I think we get the sequence \\(C_4, C_3, C_5, F_2, G_4, F_3, C_6\\),..., which probably sounds ridiculous on its own, but maybe modding over an octave would sound interesting.
  • 25.

    Thank you so much! Considering pitch is a great idea. For example, if we consider pitch, we could write sequences of intervals: starting from a simple unison for the first row, we can have two octaves for the second row, a sequence with two fifths for the third row, with the perfect fourth (4/3) and major sixth (5/3) on the fourth column. This would remind of a progressive 'enrichment' of harmony. However, we should neglect the extreme elements of each row, because the ratios would be too small, and we should consider modulo one octave for the elements whose ratio would be larger than 2.

    Comment Source:Thank you so much! Considering pitch is a great idea. For example, if we consider pitch, we could write sequences of intervals: starting from a simple unison for the first row, we can have two octaves for the second row, a sequence with two fifths for the third row, with the perfect fourth (4/3) and major sixth (5/3) on the fourth column. This would remind of a progressive 'enrichment' of harmony. However, we should neglect the extreme elements of each row, because the ratios would be too small, and we should consider modulo one octave for the elements whose ratio would be larger than 2.
Sign In or Register to comment.