Iterating over members of Stern-Brocot trees

Apr 18, 07:57 AM

Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first n rows of a Stern-Brocot tree.

It’s surprisingly simple. To generate the first n+1 rows, take the values

d8dd58c3ead2c31031724395b0e15d294759e777

where

5d856de78a34b77a3037d9971f7a93a1189dd7ac

given

76ecd9dbf7cfb3668daad2a8873e829b751fe5c5

where

d47008b4c68515aa8c9ad235d95af457b91db777

for odd j and non-negative vi.

Put informally, vi is the number of trailing zeroes in the binary representation of i.

What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.

Comment

---

Lindenmayer Systems and the Logo Turtle

Sep 21, 09:22 PM

Lindenmayer Systems, or L-Systems are not complicated. Take a string as a set of instructions in turtle graphics. “L” means “turn left”, “R” means “turn right”, and “F” means “go forward”.

Now imagine starting with a string “A” and a set of rules. You replace the characters in this string according to the rule a fixed number of times. Then for every type of character, you can either replace it with one of “L“, “R“ or “F“, or ignore/remove it.

For example, suppose you have one rule,

ba5242969b56500427ee5931032e737b19cae42e

and a final rule

a19b5b477fad9373c23540c38e903a82d46650ed

In this example, it takes 12 d160e0986aca4714714a16f29ec605af90be704d or 12 06576556d1ad802f247cad11ae748be47b70cd9c turns to turn completely around.

We start with 6dcd4ce23d88e2ee9568ba546c007c63d9131c1b and apply the rule to get eb2626a337ecb1b4dce2ff92911b1ddba6bbc78a. We apply the rule again to get 2cbdbaba6b7e00b52a82c2bae22d96dad1b19e3c, and so forth. In my example, I stopped when I got a string that would have 5000 forward moves in it.

Here’s what it looks like:

That’s one continuously traced path, all thanks to string rewriting. I’ve also created a page with a large number of random rules. It takes a lot of memory because of all the thumbnails, but if you’re curious about the rules used to generate a shape, simply follow the link to the SVG and “view source” to see what generated that shape.

---

Project Euler Level 5

Sep 2, 04:57 PM

I finally made to to 200 problems! Better yet, I picked two of the problems that had been pestering me for a while:

As I was working on “Robot Walks”, I figured out that I’d come very close to the solution last year. I had a lookup table, but it had an incorrect value for orientation in cases where the robot moved in a complete circle right or left.

Comment

---

the javascript module pattern

Aug 1, 04:13 PM

This is definitely my favorite javascript pattern, since it allows for clean, modular libraries. If you’re writing your own javascript library, it’s an approach worth considering, even if you don’t use the YUI wrappers.

Comment

---

Another SVG Animation

Jul 29, 10:55 PM

Based on the same space-filling curve, but with a little more variety in the parameters.

Comment

---

« Older Newer »