Library · The Fiddler: Solutions · Chapter 77

Can You See Between the Trees?

Revised Report an error

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 0∘0^\circ and 45∘45^\circ, the largest angular gaps between visible trees sit near the axis and near 45∘45^\circ (the tree at (1,1)(1,1)). The next-largest pair of adjacent gaps straddles which angle?

The Fiddler, Zach Wissner-Gross, April 25, 2025(original post)

Visible trees are the primitive lattice points. The widest interior gap pair flanks the ray to (2,1) .
Visible trees are the primitive lattice points. The widest interior gap pair flanks the ray to (2,1)(2,1).

Solution

A tree at (a,b)(a,b) is visible exactly when aa and bb have no common factor, since otherwise the tree at (a/d,b/d)(a/d, b/d) stands in front of it. You can see a long way, to some large distance RR, and the question is about the gaps between neighbouring visible trees as you sweep your gaze from 0∘0^\circ to 45∘45^\circ.

The one idea: the gaps beside a tree are set by how close it is. Take a visible tree v=(a,b)v = (a,b) near you and let ww be the visible tree whose direction is next to it. The triangle with corners at the origin, vv and ww 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 12\tfrac12 (Pick’s theorem). The area is also 12∣v∣ ∣w∣sin⁡θ\tfrac12|v|\,|w|\sin\theta, where θ\theta is the angle between the two directions, so sin⁡θ  =  1∣v∣ ∣w∣.\sin\theta \;=\; \frac{1}{|v|\,|w|}. Which tree is the neighbour? The trees forming such a triangle with vv lie on two lines parallel to vv, one on each side, at spacing ∣v∣|v| along each line. The farther out along its line a tree is, the closer its direction is to vv’s, so the neighbour on each side is the last tree on that line before distance RR, at a distance between R−∣v∣R - |v| and RR. Both gaps beside vv are therefore close to 1/(∣v∣R)1/(|v|R), and their total is gap pair beside v  ≈  2∣v∣ R.\text{gap pair beside } v \;\approx\; \frac{2}{|v|\,R}. The nearer the tree, the wider the pair. Once RR is large, ranking the pairs means ranking the trees by distance from you.

Between 0∘0^\circ and 45∘45^\circ the visible trees nearest you, excluding (1,0)(1,0) and (1,1)(1,1) at the ends, are

tree (2,1)(2,1) (3,1)(3,1) (3,2)(3,2) (4,1)(4,1) (4,3)(4,3) (5,1)(5,1)
distance 5\sqrt5 10\sqrt{10} 13\sqrt{13} 17\sqrt{17} 55 26\sqrt{26}

The widest pair of gaps sits beside (2,1)(2,1), at arctan⁡12  ≈  26.565∘.\arctan\tfrac12 \;\approx\; \boxed{26.565^\circ}.

The computation

The check does not use the area argument. It lists every visible tree within distance 20002000 between 0∘0^\circ and 45∘45^\circ, 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 0∘0^\circ or just below 45∘45^\circ, 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 0∘0^\circ and the gap just below 45∘45^\circ.)

Solution

Continuing the list by distance, the fifth nearest tree is (4,3)(4,3), at distance exactly 55, just ahead of (5,1)(5,1) at 26\sqrt{26}. Its pair of gaps is about 2/(5R)2/(5R), and the angle is arctan⁡34  ≈  36.870∘.\arctan\tfrac34 \;\approx\; \boxed{36.870^\circ}.

There is a subtlety, and it explains why some solvers report a different answer. A tree far away, right next to (2,1)(2,1) in direction, has on one side the whole wide gap that belongs to (2,1)(2,1), about 1/(5R)≈0.447/R1/(\sqrt5 R) \approx 0.447/R, and on the other side only a tiny gap. That total beats the pair beside (4,3)(4,3), about 0.4/R0.4/R. So, read with complete literalness, the fifth and sixth widest pairs surround the two distant trees on either side of (2,1)(2,1), at angles a hair above and below 26.565∘26.565^\circ. But which distant trees those are, and their exact angles, change with the unknown viewing distance RR. The literal reading therefore has no definite answer. Its angle merely tends to the main answer, 26.565∘26.565^\circ, as RR grows. The puzzle’s own examples speak of gaps “on either side of the tree at (1,1)(1,1)”, a tree at a fixed position. Read that way, ranking only trees at fixed positions, the fifth is (4,3)(4,3), whatever RR 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, (4,3)(4,3) is fifth in both runs.

Report an error on this page

Reports are stored by Netlify. See the privacy note.