It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

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

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} $$

`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} $$`

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.

`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.`

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))\):

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:

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.)

`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.)`

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.

`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.`

Nice graphics, Patrick O'Neil!

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.

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

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.)

`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.)`

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

`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`

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.

`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.`

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

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

Of course this sequence doesn't enumerate any

negativenumbers. So, the puzzles are:and

`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?`

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.

`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.`

Nice, Alex. So, the only question is whether we get

allthe 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.

`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.`

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.

`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.`

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.

`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.`

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.

`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.`

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 :

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:

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:

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.

`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.`

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.`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.`

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.

`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.`

John wrote:

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!

`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!`

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.

`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.`

@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

nextrow, 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}\).`@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}\\).`

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.

`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.`

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.

`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.`

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}, $$

`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}, $$`

@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.

`@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.`

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.

`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.`

Professor @JohnBaez, I would love to receive your comments about this little musical application with the 'mathematical rhythm' :)

`Professor @JohnBaez, I would love to receive your comments about this little musical application with the 'mathematical rhythm' :)`