Project Euler

Rational Zeros of a Function of Three Variables

For any integer n, consider three functions: f_(1,n)(x,y,z) = x^(n+1) + y^(n+1) - z^(n+1) f_(2,n)(x,y,z) = (xyz)^n(x+y-z) f_(3,n)(x,y,z) = xyz^n(x^(n-1)+y^(n-1)-z^(n-1)) for n!= 1 and f(x,y,z) = f_...

Source sync May 21, 2026

Problem #0180

Level Level 11

Solved By 1,885

Languages C++, Python

Answer 285196020571078987

Length 365 words

modular_arithmeticbrute_forcelinear_algebra

For any integer $n$, consider the three functions \begin{align*} f_{1, n}(x, y, z) &= x^{n + 1} + y^{n + 1} - z^{n + 1}\\ f_{2, n}(x, y, z) &= (xy + yz + zx) \cdot (x^{n - 1} + y^{n - 1} - z^{n - 1})\\ f_{3, n}(x, y, z) &= xyz \cdot (x^{n - 2} + y^{n - 2} - z^{n - 2}) \end{align*} and their combination $$f_n(x, y, z) = f_{1, n}(x, y, z) + f_{2, n}(x, y, z) - f_{3, n}(x, y, z)$$ We call $(x, y, z)$ a golden triple of order $k$ if $x$, $y$, and $z$ are all rational numbers of the form $a / b$ with $0 < a < b \le k$ and there is (at least) one integer $n$, so that $f_n(x, y, z) = 0$.

Let $s(x, y, z) = x + y + z$.

Let $t = u / v$ be the sum of all distinct $s(x, y, z)$ for all golden triples $(x, y, z)$ of order $35$.

All the $s(x, y, z)$ and $t$ must be in reduced form.

Find $u + v$.

Problem 180: Rational Zeros of a Function of Three Variables

Mathematical Development

Identifying the Zero Set

$f = 0$ when any factor vanishes. Since $x, y, z > 0$ :

$f_1 = 0$ : $x^{n+1} + y^{n+1} = z^{n+1}$ , giving exponent $m = n+1$
$f_2 = 0$ : $x + y = z$ (since $(xyz)^n \neq 0$ ), giving $m = 1$
$f_3 = 0$ : $x^{n-1} + y^{n-1} = z^{n-1}$ , giving exponent $m = n-1$

Fermat’s Last Theorem

For $|m| \geq 3$ , $x^m + y^m = z^m$ has no positive rational solutions (by FLT for $m > 0$ ; for $m < 0$ , clearing denominators converts to a positive-exponent FLT instance).

For $m = 0$ : $1 + 1 = 1$ is false.

Remaining Cases

Only four values of $m$ yield solutions:

$m$	Equation	Solution for $z$
1	$x + y = z$	$z = x + y$
2	$x^2 + y^2 = z^2$	$z = \sqrt{x^2 + y^2}$
$-1$	$1/x + 1/y = 1/z$	$z = xy/(x+y)$
$-2$	$1/x^2 + 1/y^2 = 1/z^2$	$z = xy/\sqrt{x^2+y^2}$

Enumeration

For $k = 35$ , generate all 383 proper fractions $a/b$ with $1 \leq a < b \leq 35$ . For each pair $(x, y)$ :

$m = 1$ : Check if $z = x + y$ is a valid proper fraction with denominator $\leq 35$ .
$m = -1$ : Check if $z = xy/(x+y)$ is valid.
$m = 2$ : Check if $x^2 + y^2$ is a perfect square of a rational, and if so, check $z$ .
$m = -2$ : If the square root exists, check if $z = xy/\sqrt{x^2+y^2}$ is valid.

Collect all distinct $s = x + y + z$ values and sum them.

Editorial

The mathematical reduction is what makes the brute-force search viable. Once Fermat’s theorem removes every exponent except $1$ , $2$ , $-1$ , and $-2$ , each ordered pair $(x,y)$ produces at most four candidate values of $z$ . So the problem becomes a finite search over proper fractions with denominator at most 35, followed by exact rational filtering.

The implementation first builds the full set of admissible fractions once. Then, for every pair $(x,y)$ , it checks the four surviving cases: direct addition, harmonic addition, the Pythagorean square-root case, and its reciprocal-square analogue. Whenever the resulting $z$ is again a valid proper fraction of order 35, the sum $x+y+z$ is inserted into a set. Distinct golden triples may lead to the same rational sum, so the set on these totals is essential before the final fraction sum is reduced and converted to $p+q$ .

Pseudocode

Generate every proper fraction with denominator at most 35 and store them in a sorted list.
Create an empty set of admissible sums.

For each ordered pair `(x, y)` from that list:
    Check the linear case `z = x + y`.
    Check the harmonic case `z = xy / (x + y)`.

    Compute `x^2 + y^2`.
    If this rational is a perfect square:
        let `z` be its square root and test the quadratic case.
        let `z = xy / sqrt(x^2 + y^2)` and test the inverse-quadratic case.

    Whenever a candidate `z` is a proper fraction with denominator at most 35,
    insert `x + y + z` into the set of sums.

Add all distinct sums in the set, reduce the resulting fraction to lowest terms,
and return numerator plus denominator.

Complexity Analysis

The fraction set has 383 elements, so the search examines $O(R^2)$ ordered pairs with $R=383$ . Each pair performs only constant-time rational arithmetic and a small amount of perfect-square checking, giving overall time $O(R^2)$ and negligible space beyond the set of distinct sums.

Answer

\boxed{285196020571078987}

C++ project_euler/problem_180/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Problem 180: Rational Zeros of a Function of Three Variables
// Find S(35) = sum of distinct s = x+y+z from golden triples.
// x, y, z are proper fractions a/b with 1 <= a < b <= 35.
// Equations: m=1 (x+y=z), m=-1 (z=xy/(x+y)), m=2 (z=sqrt(x^2+y^2)),
//            m=-2 (z=xy/sqrt(x^2+y^2)).

typedef long long ll;
typedef __int128 lll;

ll gcd_ll(ll a, ll b) {
    a = abs(a); b = abs(b);
    while (b) { a %= b; swap(a,b); }
    return a;
}

struct Frac {
    ll num, den; // always reduced, den > 0
    Frac(ll n = 0, ll d = 1) {
        if (d < 0) { n = -n; d = -d; }
        ll g = gcd_ll(abs(n), d);
        num = n / g; den = d / g;
    }
    bool operator<(const Frac& o) const {
        return (lll)num * o.den < (lll)o.num * den;
    }
    bool operator==(const Frac& o) const {
        return num == o.num && den == o.den;
    }
    bool operator<=(const Frac& o) const { return !(o < *this); }
    bool operator>(const Frac& o) const { return o < *this; }
    bool operator>=(const Frac& o) const { return !(*this < o); }
    Frac operator+(const Frac& o) const {
        return Frac(num * o.den + o.num * den, den * o.den);
    }
    Frac operator*(const Frac& o) const {
        return Frac(num * o.num, den * o.den);
    }
    Frac operator/(const Frac& o) const {
        return Frac(num * o.den, den * o.num);
    }
};

int main() {
    const int K = 35;

    // Generate all proper fractions a/b with 1 <= a < b <= K
    vector<Frac> rats;
    set<pair<ll,ll>> rat_set;
    for (int b = 2; b <= K; b++) {
        for (int a = 1; a < b; a++) {
            Frac f(a, b);
            if (rat_set.insert({f.num, f.den}).second) {
                rats.push_back(f);
            }
        }
    }

    auto is_valid = [&](const Frac& z) -> bool {
        if (z.num <= 0 || z.den <= 0) return false;
        if (z.num >= z.den) return false; // z >= 1
        return z.den <= K;
    };

    auto isqrt_ll = [](ll n) -> ll {
        if (n < 0) return -1;
        ll s = (ll)sqrt((double)n);
        while (s * s > n) s--;
        while ((s+1)*(s+1) <= n) s++;
        return s;
    };

    set<pair<ll,ll>> s_values;

    for (auto& x : rats) {
        for (auto& y : rats) {
            // m=1: z = x+y
            {
                Frac z = x + y;
                if (is_valid(z)) {
                    Frac s = x + y + z;
                    s_values.insert({s.num, s.den});
                }
            }

            // m=-1: z = xy/(x+y)
            {
                Frac xy = x * y;
                Frac xpy = x + y;
                Frac z = xy / xpy;
                if (is_valid(z)) {
                    Frac s = x + y + z;
                    s_values.insert({s.num, s.den});
                }
            }

            // m=2: z = sqrt(x^2+y^2)
            // x^2+y^2 = (x.num^2*y.den^2 + y.num^2*x.den^2) / (x.den^2*y.den^2)
            {
                ll num2 = x.num*x.num*y.den*y.den + y.num*y.num*x.den*x.den;
                ll den2 = x.den*x.den*y.den*y.den;
                ll g = gcd_ll(num2, den2);
                num2 /= g; den2 /= g;
                ll sn = isqrt_ll(num2);
                ll sd = isqrt_ll(den2);
                if (sn >= 0 && sd > 0 && sn*sn == num2 && sd*sd == den2) {
                    Frac z(sn, sd);
                    if (is_valid(z)) {
                        Frac s = x + y + z;
                        s_values.insert({s.num, s.den});
                    }

                    // m=-2: z = xy/sqrt(x^2+y^2)
                    Frac sqrt_sum(sn, sd);
                    Frac xy = x * y;
                    Frac z2 = xy / sqrt_sum;
                    if (is_valid(z2)) {
                        Frac s = x + y + z2;
                        s_values.insert({s.num, s.den});
                    }
                }
            }
        }
    }

    // Sum all distinct s values as a single fraction
    // Use __int128 to avoid overflow
    lll total_num = 0, total_den = 1;
    for (auto& [n, d] : s_values) {
        // total_num/total_den + n/d = (total_num*d + n*total_den) / (total_den*d)
        total_num = total_num * d + (lll)n * total_den;
        total_den = total_den * d;
        // Reduce periodically to prevent overflow
        lll g = 0;
        { lll a = total_num < 0 ? -total_num : total_num, b = total_den;
          while (b) { a %= b; swap(a,b); } g = a; }
        total_num /= g;
        total_den /= g;
    }

    if (total_den < 0) { total_num = -total_num; total_den = -total_den; }

    // Print total_num + total_den
    lll result = total_num + total_den;

    // Print __int128
    auto print128 = [](lll x) {
        if (x < 0) { putchar('-'); x = -x; }
        if (x == 0) { putchar('0'); return; }
        string s;
        while (x > 0) { s += '0' + (int)(x % 10); x /= 10; }
        reverse(s.begin(), s.end());
        printf("%s", s.c_str());
    };

    print128(result);
    putchar('\n');

    return 0;
}

Python project_euler/problem_180/solution.py

"""
Problem 180: Rational Zeros of a Function of Three Variables

Find S(35): sum of all distinct values s = x+y+z from golden triples of order 35.
x, y, z are rationals a/b with 1 <= a < b <= k (proper fractions, strictly less than 1).

The relevant equations (from FLT, only |m| <= 2 have solutions):
  m=1:  x + y = z
  m=2:  x^2 + y^2 = z^2
  m=-1: 1/x + 1/y = 1/z => z = xy/(x+y)
  m=-2: 1/x^2 + 1/y^2 = 1/z^2 => z = xy/sqrt(x^2+y^2)

Express S(35) as p/q in lowest terms, output p+q.
"""

from fractions import Fraction
from math import isqrt

K = 35

# Generate all valid rationals a/b with 1 <= a < b <= K (proper fractions)
rat_set = set()
for b in range(2, K + 1):
    for a in range(1, b):
        rat_set.add(Fraction(a, b))

rat_list = sorted(rat_set)

def is_valid(z):
    """Check if z is a valid proper fraction a/b with 1 <= a < b <= K."""
    if z <= 0 or z >= 1:
        return False
    return z.denominator <= K

s_values = set()

for x in rat_list:
    for y in rat_list:
        # Case m=1: x + y = z
        z = x + y
        if is_valid(z):
            s_values.add(x + y + z)

        # Case m=-1: z = xy/(x+y)
        z = (x * y) / (x + y)
        if is_valid(z):
            s_values.add(x + y + z)

        # Case m=2: z = sqrt(x^2 + y^2)
        z_sq = x * x + y * y
        num = z_sq.numerator
        den = z_sq.denominator
        sn = isqrt(num)
        sd = isqrt(den)
        if sn * sn == num and sd * sd == den:
            z = Fraction(sn, sd)
            if is_valid(z):
                s_values.add(x + y + z)

            # Case m=-2: z = xy/sqrt(x^2+y^2)
            sqrt_sum = Fraction(sn, sd)
            if sqrt_sum > 0:
                z2 = (x * y) / sqrt_sum
                if is_valid(z2):
                    s_values.add(x + y + z2)

total = sum(s_values)
p = total.numerator
q = total.denominator
print(p + q)