| 12823413011547414368862997525616691741041579688920794331363953564934456759066858494476606822552437442098640979 |
| 877512406035620068631903180662851572553488753575243048137500508983979170248733422547196905684808937723408093 |
The Pythagoras Tree is a fractal constructed by taking a unit square and then recursively constructing 2 copies of the Pythagoras tree each scaled by a factor of 1/√2 and rotated 45° so that the bases of the copies of the original square form a right-angled isosceles triangle with the top edge of the original square.
Let d0 be the transformation which rotates 45 degrees anticlockwise and scales by 1/√2 centered on (-1,1) and let d1 be the transformation which rotates 45 degrees clockwise and scales by 1/√2 centered on (2,1).
Define the depth 1 rendering of the Pythagoras tree to consist of an open unit square with corners at (0,0) and (1,1), and the depth n+1 rendering to consist of 2 copies of the depth n rendering transformed by d0 and d1 together with the unit square of the depth 1 rendering. This gives the arrangement described in the introduction. The Pythagoras tree is the union of the set of finite depth renderings.
Our goal is to find the exact area of the Pythagoras tree, which we will denote A. A is the limit of the sequence of the areas of the finite depth renderings. This sequence starts 1, 2, 3, 4, 5, 5 15/16, 6 53/64,... . The limit of this monotone sequence exists since it is bounded above by the area of a 7x4 rectangle which no part of the shape leaves.
Certain subsets of a unit square can be represented by dividing the square into 4 corners and describing what each quarter looks like. For shapes in which parts are copies of the whole, this can be done using a finite state automaton with the alphabet consisting of 4 symbols: tl (top left), tr (top right), bl (bottom left) and br (bottom right). For example, the triangle shown to the left can be described by the automaton below. The top left and bottom right corners are smaller copies of the triangle, while the bottom left and top right corners are full and empty respectively.
This representation lets us calculate the area of the triangle. Call the area of the triangle AT. Since the area of the triangle is the sum of the areas of each of the 4 corners, we have that AT = AF/4 + 2AT/4 + AE/4 where AF is the area of a full square and AE is the area of an empty square. As AF=1 and AE=0, the equation becomes AT = 1/4 + AT/2. This lets us conclude that AT = 1/2 i.e. the area of the triangle is exactly half that of the unit square.
Overlapping shapes can be described by non-deterministic automata where each node may have multiple (or zero) edges with a given label. In this case we don't need a separate state for empty squares - if a corner of a node is empty, it may simply have no outgoing edges with that label.
For our purposes, any given non-deterministic automaton may be converted to a deterministic automaton by having a node in the new one for every set of nodes in the old one. The node corresponding to the set S should have an edge labeled l to set of all nodes in the old automaton with edges labeled l from some element of S, and all sets containing the full node F may be collapsed into one, with edges to itself.
The tree may be divided into 28 squares in a 7x4 grid so that the largest square in the tree exactly fills one square of the grid. The 4 copies described above are nicely aligned to a subdivision of the grid, allowing each square of the grid to be described in terms of its 4 corners, each of which is either full, empty, a triangle, or an overlapping combination of squares of the original grid and their rotations. This lets us construct a non-deterministic automaton describing the shape. For example, the cell labeled B has tl-transitions to the cells C and W, tr-transitions to D and X, bl-transitions to E and Y and br-transitions to the cells F and Z. The transitions to C,D,E and F come from the yellow subtree and those labeled W,X,Y and Z come from the orange subtree.
As rotations can be multiples of 90°, we need 4 states for each of the 28 original cells. For example, the cell labeled Y has a tr-transition to a state corresponding to Z rotated 90° clockwise. The transitions from rotations are straightforward given the transitions from the originals. This gives a nondeterministic automaton with 4x28+4+1=117 states (the initial 28, their rotations, 4 triangles and 1 full square). This can be transformed into a deterministic automaton with 2116+1 states, but fortunately not all of them are needed. Instead we can start from the 28 singleton sets representing squares of the grid and discover that ~10000 states are reachable from those, which can be reduced to ~1000 by accounting for rotations and reflections.
This gives a system of linear equations for the area of the shape described by each state. This system of equations has exactly one solution.
Noting that the area of the closure of the Pythagoras tree would also be a solution to that system of linear equations, the fact that it has a unique solution implies that taking the closure does not change the area.
Firstly, here's the transition diagram, with the color of edges indicating which of the 4 subtrees the edge came from. The central nodes indicate the full node and the 4 triangles.
Now we show all the transitions, including ones from rotated copies of the original and with edges colored according to the label associated with that edge.We now turn this non-deterministic automaton into a deterministic one. Since it would take a bit too long to make the graph of all 2117 nodes, we'll do a depth-first search exploring the ones reachable from the starting 28. Because rotating and reflecting of a square doesn't change the area, we can reduce the number of states by choosing a canonical example from each set of equivalent nodes.
This representation is easy to convert into a system of linear equations, which then need to be solved.
Unfortuately, it takes a while (10-30 seconds on my machine) to solve this system of linear equations. If you want to confirm the result for yourself, change the first line of the script below from "if(false){" to "if(true){" and run it. The result is logged to the browser console. Alternatively, get the Python code from here, which uses SymPy for solving the system of linear equations and takes about a second to run.
This method can also be used to calculate the area of the Pythagoras Tree with the triangles between a node and the subtrees growing from it filled in:
| 80605706690966227797244468721167282379053 |
| 5025557197283613113718784555470007578789 |
With a few more changes, we can compute the area of the C dragon (9/4 if drawn to match the Pythagoras tree, 1/4 if scaled so that the ends are 1 unit apart). I assume the area of the C dragon has already been found by someone else (it would be very obvious from computing approximations).
Technically we're using ω-automata, which accept or reject infinte strings (F is the only accepting state, and every path that reaches it stays there forever, so we don't need a very fancy acceptance condition).
Some points have multiple representations as infinite strings, but almost all of them don't, so we don't need to worry about them when calculating the area - formally, we are describing the points of the shape such that neither the x nor the y coordinate can be expressed as a*2b where a and b are integers. The excluded subset has measure 0, so this does not affect calculation of the area.
An alternative would be to define the set described by an automaton as the set of points in the unit square such that all strings corresponding to the given point are accepted. The Pythagoras tree could be precisely described in this manner, although accounting for the open boundries of squares would require 8 additional states for partly open corners and edges
Whether the squares are open or closed has no effect on the area of a finite depth rendering, therefore has no effect on the limit of the sequence of areas. Even if closed squares were used rather than open ones, the Pythagoras tree would not be closed, since it approaches but nevver reaches the line x=4.
Whether the closure of the Pythagoras tree has a different area from the Pythagoras tree is a question that could be addressed directly, but the automaton we constructed also describes the closure of the Pythagoras tree (except for some lines of the form x±y=a*2b , for integers a and b which also have measure zero), so the areas of pieces of the closure of the Pythagoras tree satisfy the same system of linear equations. Since there is only one solution to that system, the area of the Pythagoras tree is equal to the area of its closure.
It was tempting to say (for convenience when dealing with automata) that the axis-aligned squares (added at odd depths) are closed while the other squares are open, but that smells a bit.