Fibonacci Word Fractal

DEFINITION

w = fixed point of μ: 0→01, 1→0
letter k of w, 1-indexed, moving forward one step:
  0 → turn left if k even, right if k odd
  1 → straight

NOTES

Take the Fibonacci word — the infinite string 0100101001001… that never changes under the substitution 0→01, 1→0 — and walk it with a turtle: one step forward per letter, and let every ‘0’ turn the heading a right angle, alternating left and right by whether its position in the word is even or odd, while every ‘1’ goes straight. Monnerot-Dumaine published that rule in 2009 and found a curve that never crosses its own path and takes one of three distinct silhouettes depending on the generation, by its remainder mod 3. The word itself is far older than the drawing: Morse and Hedlund singled it out in 1940 as the simplest possible Sturmian sequence — the one whose long-run letter frequencies sit exactly at 1/φ and 1/φ², the golden ratio’s own continued-fraction limit. The turtle is new; the string it walks was already seventy years into being studied for a completely different reason.

PROVENANCE

Origin

A. Monnerot-Dumaine, “The Fibonacci Word fractal”, preprint, HAL open archive hal-00367972, first deposited 8 February 2009

Standing

Public domain — a drawing rule applied to an existing combinatorial sequence

The word

The Fibonacci word is the fixed point of 0→01, 1→0. M. Morse and G. A. Hedlund, “Symbolic Dynamics II: Sturmian Trajectories”, American Journal of Mathematics 62(1), 1940, 1–42, identified it as the extremal case of the Sturmian sequences their paper named — the letter density of 0s in it converges to 1/φ ≈ 0.618 and of 1s to 1/φ² ≈ 0.382

The three silhouettes

Checked here rather than taken on trust, by walking the rule and measuring: the bounding box of the curve is 41×28 at generation 12, 69×29 at 13 and 69×70 at 14 — an aspect of 1.46, 2.38 and 1.01, and the same three figures return at 15, 16 and 17. The generation’s remainder mod 3 is what selects them. The same walk visits 1,598 distinct lattice vertices in 1,598 steps at generation 15, which is the self-avoidance, confirmed rather than cited

Constants

Generations are locked from regenerate: the substitution multiplies the word length by very nearly φ ≈ 1.618 each time, and the length at generation g is exactly the Fibonacci number F(g+2) — a cost dial, not a look dial, the same reasoning as gosper’s and levyc’s own locked generation counts

Source

https://hal.science/hal-00367972

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 89 · FIBONACCI WORD FRACTAL — Alexis Monnerot-Dumaine, 2009 · after the Fibonacci word (Morse & Hedlund, 1940)
//   w = fixed point of μ: 0→01, 1→0
//   letter k of w, 1-indexed, moving forward one step:
//     0 → turn left if k even, right if k odd
//     1 → straight
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=fibword

float p_gens    = 12 + chf('gens_tweak');         // generations · live 8 .. 15
float p_bearing = 14 + chf('bearing_tweak');      // bearing (deg) · live 0 .. 90

// The plate's own colour: FORMA's FRACTALS accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.1389 + 0.151 * cos(6.28318530718 * (t + 0.05)),
    0.1912 + 0.2078 * cos(6.28318530718 * (t + 0.1)));
}

// The Fibonacci word — fixed point of 0 → 01, 1 → 0 — walked by
// Monnerot-Dumaine's odd–even rule: forward one step per letter, a '0'
// turning a right angle (left at an even 1-indexed position, right at an
// odd one), a '1' going straight. The heading is kept as an integer vector
// and rotated into the bearing only at the end: four right angles must
// return exactly, and VEX floats are 32-bit — the same reasoning the plate
// itself records. The plate folds a grid phase into the bearing; the port
// takes the published bearing alone. Steps are unit length.
int gens = int(rint(p_gens));

int w[] = {0};
for (int g = 0; g < gens; g++){
    int next[];
    foreach (int c; w){
        if (c == 0){ push(next, 0); push(next, 1); }
        else         push(next, 0);
    }
    w = next;
}

int x = 0, y = 0, hx = 1, hy = 0;
int xs[] = {0}, ys[] = {0};
for (int i = 0; i < len(w); i++){
    x += hx;  y += hy;
    push(xs, x);  push(ys, y);
    if (w[i] == 0){
        if ((i + 1) % 2 == 0){ int t = -hy; hy = hx; hx = t; }   // left
        else                 { int t =  hy; hy = -hx; hx = t; }  // right
    }
}

float br = p_bearing * 3.14159265359 / 180.0;
float co = cos(br), si = sin(br);
int n = len(xs);
int prim = addprim(0, "polyline");
for (int i = 0; i < n; i++){
    float rx = float(xs[i]) * co - float(ys[i]) * si;
    float ry = float(xs[i]) * si + float(ys[i]) * co;
    // canvas y runs down; negated so the curve sits as the plate shows it
    int pt = addpoint(0, set(rx, -ry, 0.0));
    // colour sweeps the bright lobe of the ramp along the walk
    float u = float(i) / float(n - 1);
    setpointattrib(0, "Cd", pt, forma_ramp(0.8 + 0.3 * u));
    addvertex(0, prim, pt);
}

AFTER EFFECTS · EXPRESSION

The same published mathematics as a Shape Layer path expression. Paste it onto a Path property; every constant is the published value plus a Slider Control named _tweak, so a bare paste already draws the figure and each slider moves one constant in its own units. Trim Paths is the comet.

// FORMA — PL. 89 · FIBONACCI WORD FRACTAL — Alexis Monnerot-Dumaine, 2009 · after the Fibonacci word (Morse & Hedlund, 1940)
//   w = fixed point of μ: 0→01, 1→0
//   letter k of w, 1-indexed, moving forward one step:
//     0 → turn left if k even, right if k odd
//     1 → straight
// After Effects port — paste onto a Shape Layer's Path property
// (Contents › Shape › Path). Written from the published mathematics, not
// adapted from any code. Constants arrive at their published values; add a
// Slider Control (Effect › Expression Controls) named <k>_tweak and that
// constant moves in its own units, starting at 0 — the published figure.
// The plate's comet and its reveal are Trim Paths; the stroke colour is
// FORMA's FRACTALS accent, #FF4D6A. Animation runs on time.
// https://forma-gen.com/#plate=fibword

// A missing slider reads 0, so a bare paste already draws the figure.
function forma_tweak(n){ try { return effect(n)("Slider"); } catch (e){ return 0; } }
var p_gens    = 12 + forma_tweak("gens_tweak");       // generations · live 8 .. 15
var p_bearing = 14 + forma_tweak("bearing_tweak");    // bearing (deg) · live 0 .. 90

// The frame: the plate's W × H canvas is this comp, with the origin at the
// layer's anchor; canvas y already runs down, as After Effects' does.
var forma_W = thisComp.width, forma_H = thisComp.height, forma_t = time;
var forma_phase = 0.5957580911926925;   // this plate's own fixed phase, as the page has it
function forma_pt(x, y){ return [x - forma_W / 2, y - forma_H / 2]; }

// The Fibonacci word — the fixed point of 0 → 01, 1 → 0 from the letter 0 —
// drawn by the odd–even rule (Monnerot-Dumaine, 2009): one unit per letter, a
// 0 turns (left at an even 1-indexed position, right at an odd one), a 1 goes
// straight. The heading is kept as an integer vector and rotated once at the
// end, so four right angles return exactly to the start direction and the
// curve stays on its own lattice over 1,500+ segments. The bearing joins this
// plate's own phase, as on the page. Fitted to 0.82 of the frame; the page
// grows it over 17 s — Trim Paths, End 0 → 100%.
var gens = Math.round(p_gens);
var w = '0';
for (var g = 0; g < gens; g++){
  var next = '';
  for (var c = 0; c < w.length; c++) next += w.charAt(c) === '0' ? '01' : '0';
  w = next;
}
var x = 0, y = 0, hx = 1, hy = 0;
var raw = [[0, 0]];
for (var i = 0; i < w.length; i++){
  x += hx; y += hy;
  raw.push([x, y]);
  if (w.charAt(i) === '0'){
    var k = i + 1;                                   // 1-indexed letter position
    if (k % 2 === 0){ var lx = -hy, ly = hx; hx = lx; hy = ly; }   // left
    else { var rx = hy, ry = -hx; hx = rx; hy = ry; }              // right
  }
}
var ang = (p_bearing + forma_phase * 90) * Math.PI / 180;
var co = Math.cos(ang), si = Math.sin(ang);
var minx = 1e9, maxx = -1e9, miny = 1e9, maxy = -1e9;
var rot = [];
for (var j = 0; j < raw.length; j++){
  var px = raw[j][0] * co - raw[j][1] * si, py = raw[j][0] * si + raw[j][1] * co;
  rot.push([px, py]);
  if (px < minx) minx = px; if (px > maxx) maxx = px;
  if (py < miny) miny = py; if (py > maxy) maxy = py;
}
var sc = Math.min(forma_W * 0.82 / ((maxx - minx) || 1), forma_H * 0.82 / ((maxy - miny) || 1));
var ox = (forma_W - (maxx - minx) * sc) / 2 - minx * sc;
var oy = (forma_H - (maxy - miny) * sc) / 2 - miny * sc;
var pts = [];
for (var m = 0; m < rot.length; m++) pts.push(forma_pt(ox + rot[m][0] * sc, oy + rot[m][1] * sc));
createPath(pts, [], [], false);