Detailed mathematical approach

Problem Summary

For a positive integer \(k\), the admissible numbers are the reduced proper fractions

$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$

Problem 180 fixes \(k=35\) and asks for all triples \((x,y,z)\in S_k^3\) for which the problem's function \(f_n(x,y,z)\) vanishes for at least one integer \(n\). For every such triple we form \(s=x+y+z\), keep only distinct rational values of \(s\), add them all together, reduce the total to lowest terms \(u/v\), and report \(u+v\).

The direct interpretation suggests searching all triples and all integers \(n\). The implementations do something much sharper: they factor the defining expression, prove that only four exponents can matter, and then scan pairs \((x,y)\) instead of triples \((x,y,z)\).

Mathematical Approach

The whole solution rests on one algebraic simplification. Once the original zero-condition is rewritten correctly, the search space collapses from an open-ended three-variable problem to four explicit formulas for \(z\).

The finite state space \(S_k\)

Every element of \(S_k\) is a positive rational smaller than 1, already stored in lowest terms. For each denominator \(b\), exactly \(\varphi(b)\) numerators are coprime to \(b\), so

$|S_k|=\sum_{b=2}^{k}\varphi(b).$

At the target order \(k=35\), this gives \(383\) admissible fractions. A naive triple search would therefore examine \(383^3\) candidates before even considering different exponents, so the algebraic reduction is the decisive step.

Factor the zero-condition

The implementations encode the original function as

$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$

If the second and third lines are expanded, the mixed terms \(yz\,x^{n-1}\), \(xz\,y^{n-1}\), and \(xy\,z^{n-1}\) cancel, and everything that remains factors cleanly:

$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$

Because \(x\), \(y\), and \(z\) are positive rationals, we always have \(x+y+z>0\). Therefore

$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$

This is the key invariant behind all three implementations.

Why only four exponents survive

If \(n=0\), the reduced equation becomes \(1+1=1\), which is impossible. If \(n>2\), any positive rational solution of \(x^n+y^n=z^n\) can be cleared of denominators to produce a positive integer solution, contradicting Fermat's Last Theorem. If \(n<-2\), write \(m=-n>2\); then

$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$

which is the same kind of forbidden equation after replacing \(x,y,z\) by their reciprocals.

So the only exponents that can possibly contribute are

$n\in\{-2,-1,1,2\}.$

The infinite search over all integers has collapsed to four explicit cases.

Turn each pair \((x,y)\) into at most four candidates for \(z\)

Once \(x\) and \(y\) are fixed, each admissible exponent gives a concrete formula:

$n=1:\quad z=x+y,$

$n=-1:\quad z=\frac{xy}{x+y},$

$n=2:\quad z=\sqrt{x^2+y^2},$

$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$

This is why the optimized solver loops over ordered pairs \((x,y)\) rather than triples. For the square-root branches, the implementations compute the reduced fraction for \(z^2\) and accept it only when both numerator and denominator are perfect squares. After reduction, a membership test against \(S_k\) simultaneously checks that \(0<z<1\) and that the reduced denominator is at most \(k\).

Worked examples and distinct sums

The arithmetic is easiest to see on small examples. In the \(n=-1\) branch, taking \(x=\tfrac12\) and \(y=\tfrac13\) gives

$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac{1/6}{5/6}=\frac15,$

so \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). In the \(n=2\) branch,

$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{9}{100}+\frac{16}{100}=\frac{25}{100}=\left(\frac12\right)^2,$

so \((x,y,z)=\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) is valid. For \(n=-2\), choosing \(x=\tfrac13\) and \(y=\tfrac14\) gives

$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$

hence \(z=\tfrac15\).

Different triples, and even different exponents, can lead to the same final value \(s=x+y+z\). The set of sums is therefore deduplicated at the rational-number level, not at the triple level.

How the Code Works

Enumerating the allowed fractions

The C++, Python, and Java implementations first generate every reduced fraction in \(S_{35}\). These fractions are also inserted into a hash-based membership structure so that a candidate \(z\) can be accepted or rejected in constant expected time.

Exact candidate generation

The main loop runs through every ordered pair \((x,y)\in S_k^2\). For each pair, the implementation constructs the four candidates listed above. All arithmetic is exact: the Python version relies on built-in rational arithmetic, while the C++ and Java versions keep reduced numerator-denominator pairs and normalize after each addition, multiplication, division, or reciprocal. The \(n=\pm2\) branches use integer square-root tests on the reduced numerator and denominator to detect whether the square root stays rational.

Membership filtering and deduplication

If a candidate \(z\) belongs to \(S_k\), the implementation forms \(s=x+y+z\) and inserts that reduced fraction into a set of distinct sums. The scan does not try to avoid the symmetry between \((x,y)\) and \((y,x)\); it simply allows duplicates to arise and lets the set remove them automatically.

Exact final accumulation

After the pair scan finishes, the distinct \(s\)-values are added exactly and reduced to a single fraction \(u/v\). The required output is then \(u+v\). The C++ implementation additionally contains small-order validation checkpoints: it compares the factored equation with the original definition, checks the optimized pair scan against brute-force triple enumeration on small \(k\), and verifies consistency between single-threaded and multithreaded execution.

Complexity Analysis

Let

$M=|S_k|=\sum_{b=2}^{k}\varphi(b).$

Building the admissible fraction list and the membership set costs \(O(M)\). The main solver then examines every ordered pair \((x,y)\), so the dominant work is \(O(M^2)\). Each pair performs four candidate constructions, a constant number of gcd reductions, a few hash lookups, and at most two perfect-square checks.

The memory usage is \(O(M+U)\), where \(U\) is the number of distinct sums retained. For the target \(k=35\), \(M=383\), so the optimized search examines only \(383^2=146{,}689\) ordered pairs instead of \(383^3\) triples. The brute-force \(O(M^3)\) method appears only in the C++ validation checkpoints for tiny orders.

Footnotes and References

1. Problem page: Project Euler 180
2. Rational number: Wikipedia - Rational number
3. Euler's totient function: Wikipedia - Euler's totient function
4. Fermat's Last Theorem: Wikipedia - Fermat's Last Theorem
5. Pythagorean triple: Wikipedia - Pythagorean triple