P220
projecteuler.net

Heighway Dragon

ℹ️Published on Saturday, 6th December 2008, 09:00 am; Solved by 2409;
Difficulty rating: 55%

Let $D_0$ be the two-letter string "Fa". For $n\ge 1$, derive $D_n$ from $D_{n-1}$ by the string-rewriting rules:

"a" → "aRbFR"
"b" → "LFaLb"

Thus, $D_0 = $ "Fa", $D_1 = $ "FaRbFR", $D_2 = $ "FaRbFRRLFaLbFR", and so on.

These strings can be interpreted as instructions to a computer graphics program, with "F" meaning "draw forward one unit", "L" meaning "turn left $90$ degrees", "R" meaning "turn right $90$ degrees", and "a" and "b" being ignored. The initial position of the computer cursor is $(0,0)$, pointing up towards $(0,1)$.

Then $D_n$ is an exotic drawing known as the Heighway Dragon of order $n$. For example, $D_{10}$ is shown below; counting each "F" as one step, the highlighted spot at $(18,16)$ is the position reached after $500$ steps.

What is the position of the cursor after $10^{12}$ steps in $D_{50}$?
Give your answer in the form x,y with no spaces.



Soluzione

Last modified: August 21, 2025. Website built with Franklin.jl and the lovely Julia programming language.