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 Apr 19, 2026

Problem #0180

Level Level 11

Solved By 1,885

Languages C++, Python

Answer 285196020571078987

Length 212 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 Analysis

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.

Answer

\boxed{285196020571078987}

Complexity

The enumeration iterates over $O(R^2)$ pairs where $R = 383$ rationals, with $O(1)$ work per pair per case. Total: $O(R^2) \approx 1.5 \times 10^5$ operations. Negligible runtime.

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)