Post without words #23

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
Image | This entry was posted in pattern, pictures, posts without words and tagged , , , . Bookmark the permalink.

11 Responses to Post without words #23

1. Denis says:

Clearly related to Euclid’s Orchard and PWW 20 ( https://mathlesstraveled.com/2017/07/08/post-without-words-20/ ) but the meaning of the steps is not clear. (Blue dots are those added since the last step.)

• macbi says:

Is a sort of reverse Euclid algorithm? If (a,b) are coprime then at the next step you can add (a+b,b) and (a,a+b), since those also must be coprime.

• Brent says:

Wow, that was fast! You got it. =) See also https://mathlesstraveled.com/2008/01/07/recounting-the-rationals-part-ii-fractions-grow-on-trees/ .

For some reason the Calkin-Wilf tree and the Euclidean Algorithm is one of my favorite topics. I keep coming back to it!

• Denis says:

Oh, nice. I was briefly wondering if it was something about only adding dots that are directly above or to the right of known dots, which was actually close since if you drew the lines of the tree on this map they’d be vertical and horizontal strokes.

You can even rephrase this graphically: start with a point at 1,1 and at every step, each point adds two points by taking two steps: a +y step equal in length to its x coordinate and the reverse.

• Brent says:

Yes, that’s a nice way to think of it.

2. macbi says:

So what causes the “fingers” we can see in the diagram? I don’t think they’re features of the orchard itself (which has a “uniform” density of $6/\pi^2$) so they must be to do with the order in which this algorithm plants the trees.

• Denis says:

Based on the graphical version of the algorithm, the biggest additions come from the farthest-out points so the (1,n) and (n,1) lines creep along while the more central points take large jumps at every step. The x=y line is excluded by the nature of the orchard, and likewise the other divisions between fingers. It might be interesting to see this colored by position of the tree, with the farthest left and farthest right branches in red and the rest in the appropriate hue.

• Brent says:

Interesting idea, but I’m not sure it turned out to be all that enlightening:

• Brent says:

The fingers are arranged along lines with slopes which are ratios of Fibonacci numbers, or sums of Fibonacci numbers. I think Denis has a good explanation of what causes this.
The “anti-fingers” (the radial “gaps” with no dots) are arranged along lines with slopes that are simple fractions like 1/2, 1/3, 2/3, etc.

3. Dana Ernst says:

Cool! This is related to Problems 43 and 44 from my problem solving course. The problems are here:

http://danaernst.com/teaching/mat220f18/220ProblemCollection.pdf

Note: This list of problems grows as the semester progresses.

• Brent says:

Yes, very nice! So what I have shown can be thought of as a graph of all the points you can reach with your hyperdrive after at most 10 jumps.

This site uses Akismet to reduce spam. Learn how your comment data is processed.