Detailed mathematical approach

Problem Summary

Take a convex quadrilateral \(ABCD\) and let its diagonals meet at \(X\). The diagonals split the four corner angles into eight smaller angles. Problem 177 asks for the number of such quadrilaterals for which all eight of those angles are integers measured in degrees, with shapes identified up to rotation and reflection.

The brute-force version of that question is very redundant. An arbitrary 8-tuple of positive integers does not automatically correspond to a real quadrilateral, and even when it does, the same geometric figure appears many times under different starting vertices or reversed orientations. The implementations solve the problem by finding the right five-parameter description, deriving one trigonometric closure condition, and then canonicalizing the surviving angle data under the dihedral symmetries of the quadrilateral.

Mathematical Approach

The useful viewpoint is to work with the diagonals and the four small triangles that they create. Once the angle data is organized correctly, the geometry separates into a linear part and a multiplicative sine-law part.

A Five-Parameter Description of the Eight Angles

Write the eight split angles in cyclic order as four vertex pairs:

$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$

Here the pair \((a,p)\) is the split of angle \(A\), \((q,r)\) is the split of angle \(B\), \((s,c)\) is the split of angle \(C\), and \((U-c,V-a)\) is the split of angle \(D\). The implementations set

$U=p+q,\qquad V=180-U,\qquad s=V-r.$

That choice is not arbitrary. In triangle \(ABX\), the angle at the intersection point is \(180-p-q=180-U\). In the opposite triangle \(CDX\), the angle at the intersection point is

$180-c-(U-c)=180-U,$

so those vertical angles already match. Likewise, in triangles \(BCX\) and \(DAX\) the intersection angles are both

$180-r-s=180-V=U.$

Thus, once \(p\), \(q\), and \(r\) are chosen, the relations \(U=p+q\), \(V=180-U\), and \(s=V-r\) enforce all linear angle constraints coming from the crossing diagonals and the fact that the four interior angles of a convex quadrilateral sum to \(360^\circ\). The remaining free angles are \(a\) and \(c\), with

$1\le a\le V-1,\qquad 1\le c\le U-1.$

The Law-of-Sines Closure Equation

Now look at the four small triangles adjacent to the sides \(AB\), \(BC\), \(CD\), and \(DA\). The law of sines gives

$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$

Multiplying the four equations makes the segment lengths telescope, so a necessary condition for the triangles to close up around \(X\) is

$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$

Rearranging gives the invariant used by every implementation:

$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$

Within this parameterization the condition is also sufficient. Once one segment such as \(AX\) is chosen, the four sine-law ratios determine \(BX\), \(CX\), and \(DX\). The product condition guarantees that the last ratio returns to the starting length, so the four triangles glue consistently into one convex quadrilateral with the prescribed integer angle data.

Separating the Search into a Target and a Table

The previous identity can be written as

$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$

For fixed \(U\), the left-hand side depends only on \((p,q,r)\), because \(s=V-r\) is then determined. The right-hand side depends only on \((a,c)\). That is the entire algorithmic idea.

Define

$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$

Then a valid integer-angled quadrilateral is exactly a match

$K(p,q,r)=R_U(a,c)$

with all angles positive. For each fixed \(U\), there are \((U-1)(V-1)\) possible pairs \((a,c)\). The implementations precompute all such \(R_U(a,c)\) values, sort them, and then use binary search to find the pairs that can match a given target \(K(p,q,r)\).

Worked Example

A concrete nontrivial example is

$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$

Then

$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$

The target value is

$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$

For the same \(U=90\), the table value at \((a,c)=(30,60)\) is

$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$

so the trigonometric condition is satisfied. The corresponding vertex pairs are

$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$

which give interior angles \(60^\circ,90^\circ,120^\circ,90^\circ\). This is exactly the kind of integer configuration the code stores and deduplicates.

Removing Rotations and Reflections

The problem counts shapes, not descriptions. The same quadrilateral can be listed starting from any of its four vertices, and it can also be traversed in the opposite orientation. Therefore the four vertex pairs above have 8 equivalent presentations: 4 cyclic rotations and 4 reflected rotations.

The implementations encode each candidate as the cyclic sequence

$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$

and choose the lexicographically smallest representative among those 8 symmetry images. Counting those canonical representatives is exactly what prevents duplicate quadrilaterals from being included more than once.

How the Code Works

The C++, Python, and Java implementations all follow the same three-phase structure.

Precompute Sines and Ratio Tables

First the implementation stores \(\sin(d^\circ)\) for every integer \(d\) from \(0\) to \(180\). It also precomputes the basic quotients

$\frac{\sin(n-k)}{\sin k}$

for all admissible \(n\) and \(k\). For each \(U\in\{2,\dots,178\}\), it then enumerates every legal pair \((a,c)\), forms \(R_U(a,c)\), tags it with the corresponding angles, and sorts the resulting list by ratio value.

Enumerate \((p,q,r)\) and Verify Candidates

The main loop runs over all positive \(p\), \(q\), and \(r\) with \(U=p+q \lt 180\) and \(1\le r\le V-1\). For each triple it computes \(s=V-r\) and the target \(K(p,q,r)\). A binary search in the precomputed list for the same \(U\) locates the short interval of \((a,c)\) pairs whose floating-point ratio is close enough to \(K\).

Those near matches are not accepted blindly. Each one is rechecked against the original product equation

$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$

with a stricter tolerance. This second test filters out candidates that are numerically nearby only because of rounding.

Canonicalize and Count

Whenever a candidate passes the verification step, the implementation forms the 8-angle description \((a,p,q,r,s,c,U-c,V-a)\), generates the 8 symmetry-equivalent presentations, keeps the lexicographically smallest one, and inserts it into a set. The final set size is the required number of distinct integer angled quadrilaterals.

Complexity Analysis

The angle range is small and fixed, so the search is finite. A useful exact count is

$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$

which is both the total number of precomputed \((a,c)\) entries across all ratio tables and the total number of primary \((p,q,r)\) states considered in the main enumeration.

If \(M_U=(U-1)(179-U)\) denotes the size of the table for one fixed \(U\), preprocessing costs \(\sum_U O(M_U\log M_U)\) because each bucket is sorted once. The search phase performs one binary search per \((p,q,r)\) state plus a very small local verification scan around the matching value. Memory usage is dominated by the stored ratio tables and the set of canonical representatives. In practice, the method is fast precisely because it turns geometric existence into a sorted table lookup instead of a naive search over all 8-tuples.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=177
2. Law of sines: Wikipedia - Law of sines
3. Convex quadrilateral: Wikipedia - Convex quadrilateral
4. Diagonal: Wikipedia - Diagonal
5. Dihedral group: Wikipedia - Dihedral group