28. Fibonacci Sequence
The forest south of Dorpat was quiet enough that Mihkel could hear his own thoughts. A pale autumn mist clung to the undergrowth, and the smell of resin hung in the air like something distilled. He had wandered out here to clear the stiffness left by long hours bent over gears and parchment.
On the path, a pine cone lay half-buried in needles. Its symmetry pulled his gaze. He crouched and brushed aside the damp bracts, counting the spirals the way he used to count gear teeth. Five rising one way. Eight curling the other. He had seen larger cones earlier in the summer with eight and thirteen.
These numbers did not repeat by chance. They followed a law that was neither mystical nor arbitrary: growth constrained by space, adding new structure only where the last two increments allowed. Nature did not choose the sequence; the sequence emerged from nature’s need to pack things tightly and grow without collision.
Walking back toward the city, Mihkel kept turning the idea in his mind. The Logic Mill had processed transformations, ciphers, classifications—but not this. Not a pattern that required each new value to be built from the memory of two before it. Recursion felt less like a procedure and more like an echo through time.
By the time he reached his workshop, the mist had turned the windowpanes opaque. He set the pine cone beside the Mill, as if to mark the problem’s origin. Then he prepared a short tape: a unary mark for the target index, nothing more.
His notes filled quickly with attempts: rules for stepping back, for summing, for advancing again. The Mill’s brass arms clicked in patient intervals, each pass adding to the last. The rhythm stretched longer than he expected, a slow accumulation—like the spirals on the cone, widening with every turn.
On the input tape, you’ll get a number n in unary format.
Your task is to compute the nth number in the Fibonacci sequence and output it in unary format.
The sequence starts as follows: 1, 1, 2, 3, ... The largest Fibonacci number you need to handle in this quest is the 15th number (which is 610).
For example, if the input tape is ||||||, your output tape should be |||||||| (6th number in the Fibonacci sequence is 8).
You can solve this quest by simply hard-coding the Fibonacci sequence in the transition rules. But that's not fun. So I suggest to solve it algorithmically, which is more challenging (and fun)!