Library · The Fiddler: Solutions · Chapter 77
Can You See Between the Trees?
From the origin you look out at a forest with a (thin) tree at every point with nonnegative integer coordinates; a tree hides any tree directly behind it. Between and , the largest angular gaps between visible trees sit near the axis and near (the tree at ). The next-largest pair of adjacent gaps straddles which angle?
The Fiddler, Zach Wissner-Gross, April 25, 2025(original post)
Solution
A tree at is visible exactly when and have no common factor, since otherwise the tree at stands in front of it. You can see a long way, to some large distance , and the question is about the gaps between neighbouring visible trees as you sweep your gaze from to .
The one idea: the gaps beside a tree are set by how close it is. Take a visible tree near you and let be the visible tree whose direction is next to it. The triangle with corners at the origin, and contains no other lattice point, because any such point would be a tree in between the two directions or in front of one of them. A lattice triangle with no lattice points other than its corners has area (Pick’s theorem). The area is also , where is the angle between the two directions, so Which tree is the neighbour? The trees forming such a triangle with lie on two lines parallel to , one on each side, at spacing along each line. The farther out along its line a tree is, the closer its direction is to ’s, so the neighbour on each side is the last tree on that line before distance , at a distance between and . Both gaps beside are therefore close to , and their total is The nearer the tree, the wider the pair. Once is large, ranking the pairs means ranking the trees by distance from you.
Between and the visible trees nearest you, excluding and at the ends, are
| tree | ||||||
|---|---|---|---|---|---|---|
| distance |
The widest pair of gaps sits beside , at
The computation
The check does not use the area argument. It lists every visible tree within distance between and , sorts them by angle, measures the two gaps beside each tree directly, and ranks the trees by the total. It leaves out the two pairs that include the gap just above or just below , as the puzzle says.
import numpy as np
from math import degrees, atan2, hypot
def ranked_pairs(R):
"""Visible trees with 0 <= angle <= 45 degrees within distance R,
ranked by the total width of the two gaps beside each one."""
a, b = np.meshgrid(np.arange(1, R + 1), np.arange(0, R + 1))
seen = (b <= a) & (a*a + b*b <= R*R) & (np.gcd(a, b) == 1)
a, b = a[seen], b[seen]
order = np.argsort(np.arctan2(b, a))
a, b = a[order], b[order]
th = np.arctan2(b, a)
pair = th[2:] - th[:-2] # the two gaps beside tree i, skipping
trees = list(zip(a[1:-1], b[1:-1])) # (1,0) and (1,1) themselves
rank = np.argsort(-pair)
# leave out the two pairs that include the gap just above 0 or below 45
return [trees[i] for i in rank if i not in (0, len(trees) - 1)]
for x, y in ranked_pairs(2000)[:4]:
print("tree (%d, %d) angle %.3f" % (x, y, degrees(atan2(y, x))))
It prints
tree (2, 1) angle 26.565
tree (3, 1) angle 18.435
tree (3, 2) angle 33.690
tree (4, 1) angle 14.036
The top four follow the order of distance, as the argument predicts.
Extra Credit
The fifth largest pair of adjacent gaps in this range lies on either side of what angle? (Again, ignore the gap just above and the gap just below .)
Solution
Continuing the list by distance, the fifth nearest tree is , at distance exactly , just ahead of at . Its pair of gaps is about , and the angle is
There is a subtlety, and it explains why some solvers report a different answer. A tree far away, right next to in direction, has on one side the whole wide gap that belongs to , about , and on the other side only a tiny gap. That total beats the pair beside , about . So, read with complete literalness, the fifth and sixth widest pairs surround the two distant trees on either side of , at angles a hair above and below . But which distant trees those are, and their exact angles, change with the unknown viewing distance . The literal reading therefore has no definite answer. Its angle merely tends to the main answer, , as grows. The puzzle’s own examples speak of gaps “on either side of the tree at ”, a tree at a fixed position. Read that way, ranking only trees at fixed positions, the fifth is , whatever is. That is the answer given here. (The source’s value is behind its paywall; this is my own.)
The computation
The same ranking from The computation above, now printed seven deep with each tree’s distance, for two different viewing distances.
for R in (1000, 2000):
print("R =", R)
for x, y in ranked_pairs(R)[:7]:
print(" tree (%d, %d) distance %.1f angle %.3f" % (x, y, hypot(x, y), degrees(atan2(y, x))))
It prints
R = 1000
tree (2, 1) distance 2.2 angle 26.565
tree (3, 1) distance 3.2 angle 18.435
tree (3, 2) distance 3.6 angle 33.690
tree (4, 1) distance 4.1 angle 14.036
tree (893, 446) distance 998.2 angle 26.539
tree (893, 447) distance 998.6 angle 26.591
tree (4, 3) distance 5.0 angle 36.870
R = 2000
tree (2, 1) distance 2.2 angle 26.565
tree (3, 1) distance 3.2 angle 18.435
tree (3, 2) distance 3.6 angle 33.690
tree (4, 1) distance 4.1 angle 14.036
tree (1787, 894) distance 1998.2 angle 26.578
tree (1789, 894) distance 1999.9 angle 26.552
tree (4, 3) distance 5.0 angle 36.870
The two distant trees change with the viewing distance, as described above. Among trees at fixed positions, is fifth in both runs.