Project Euler

Project Euler Problem 397 -- Triangle on Parabola

On the parabola y = x^2 / k (for a positive integer k), three points A(a, a^2/k), B(b, b^2/k), C(c, c^2/k) are chosen with integer x-coordinates satisfying 0 < a < b < c <= k. The area of triangle...

Source sync Apr 19, 2026

Problem #0397

Level Level 29

Solved By 323

Languages C++, Python

Answer 141630459461893728

Length 256 words

geometryalgebrabrute_force

On the parabola $y = x^2/k$, three points $A(a, a^2/k)$, $B(b, b^2/k)$ and $C(c, c^2/k)$ are chosen.

Let $F(K, X)$ be the number of the integer quadruplets $(k, a, b, c)$ such that at least one angle of the triangle $ABC$ is $45$-degree, with $1 \le k \le K$ and $-X \le a < b < c \le X$.

For example, $F(1, 10) = 41$ and $F(10, 100) = 12492$.

Find $F(10^6, 10^9)$.

Project Euler Problem 397 — Triangle on Parabola

Derivation of the Area Formula

Place three points on $y = x^2/k$ with x-coordinates $a < b < c$ . Using the shoelace formula:

\text{Area} = \tfrac{1}{2}\left| a\!\left(\tfrac{b^2}{k} - \tfrac{c^2}{k}\right) + b\!\left(\tfrac{c^2}{k} - \tfrac{a^2}{k}\right) + c\!\left(\tfrac{a^2}{k} - \tfrac{b^2}{k}\right) \right|.

Expanding:

= \frac{1}{2k}\left|a(b^2-c^2) + b(c^2-a^2) + c(a^2-b^2)\right|.

Factor the expression inside the absolute value:

a(b^2-c^2) + b(c^2-a^2) + c(a^2-b^2) = (b-a)(c-a)(c-b).

Hence

\boxed{\text{Area} = \frac{(b-a)(c-b)(c-a)}{2k}}.

(All three factors are positive since $a < b < c$ .)

Key Constraint

The area condition $\text{Area} \le k$ becomes

(b - a)(c - b)(c - a) \le 2k^2.

Counting Strategy

Let $u = b - a \ge 1$ and $v = c - b \ge 1$ . Then $c - a = u + v$ and we need

u \cdot v \cdot (u + v) \le 2k^2

with the additional constraint $a \ge 1$ and $c = a + u + v \le k$ , so $a$ ranges from $1$ to $k - u - v$ , giving $k - u - v$ valid values of $a$ (when $u + v \le k - 1$ ).

Therefore

S(k) = \sum_{\substack{u \ge 1,\; v \ge 1 \\ u + v \le k - 1 \\ u\,v\,(u+v) \le 2k^2}} (k - u - v).

Algorithm (O(k) time)

For each fixed $u$ from $1$ upward, find the maximum $v$ satisfying both constraints:

Range constraint: $v \le k - 1 - u$
Area constraint: $u \cdot v \cdot (u + v) \le 2k^2$

The area constraint $u v(u+v) \le 2k^2$ rearranges to $u v^2 + u^2 v \le 2k^2$ , a quadratic in $v$ :

v \le \frac{-u + \sqrt{u^2 + 8k^2/u}}{2} \eqqcolon v_{\max}^{\text{area}}(u).

Set $v_{\max}(u) = \min\!\bigl(\lfloor v_{\max}^{\text{area}}(u)\rfloor,\; k-1-u\bigr)$ .

The inner sum telescopes:

\sum_{v=1}^{v_{\max}} (k - u - v) = v_{\max}(k - u) - \frac{v_{\max}(v_{\max}+1)}{2}.

The outer loop over $u$ terminates once even $v = 1$ violates the area constraint, i.e., when $u(u+1) > 2k^2$ , giving $u_{\max} \approx \sqrt{2}\,k$ .

Since $u_{\max} = O(k)$ and each iteration is $O(1)$ , the total time is $O(k)$ .

Sample Values

$k$	$S(k)$
$10$	$120$
$100$	$161{,}700$
$1{,}000$	$27{,}955{,}498$
$10^4$	$7{,}343{,}965{,}890$
$10^5$	$1{,}749{,}913{,}169{,}720$
$10^6$	$397{,}325{,}186{,}769{,}552$

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

\boxed{141630459461893728}

Complexity

Time: $O(k)$ — single pass over $u$ with $O(1)$ work per step.
Space: $O(1)$ .

C++ project_euler/problem_397/solution.cpp

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

/*
 * Project Euler Problem 397 -- Triangle on Parabola
 *
 * On parabola y = x^2/k, points with integer x-coords a < b < c
 * (0 < a < b < c <= k) form a triangle with area = (b-a)(c-b)(c-a)/(2k).
 *
 * S(k) = # triples with area <= k, i.e. (b-a)(c-b)(c-a) <= 2k^2.
 *
 * Substituting u = b-a, v = c-b:
 *   u*v*(u+v) <= 2k^2, u >= 1, v >= 1, u+v <= k-1
 *   Each valid (u,v) contributes (k - u - v) triples.
 *
 * For each u, find max v via quadratic formula on u*v^2 + u^2*v <= 2k^2.
 */

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

// Find max v >= 1 such that u*v*(u+v) <= bound
ll max_v_for_u(ll u, ll bound) {
    // Check if v=1 works
    if (u * 1LL * (u + 1) > bound) return 0;

    // u*v^2 + u^2*v <= bound
    // v^2 + u*v - bound/u <= 0
    // v <= (-u + sqrt(u^2 + 4*bound/u)) / 2
    double disc = (double)u * u + 4.0 * (double)bound / u;
    ll v_max = (ll)((-u + sqrt(disc)) / 2.0);

    // Adjust for floating point errors using 128-bit arithmetic
    while (v_max >= 1 && (lll)u * v_max * (u + v_max) > bound) v_max--;
    while ((lll)u * (v_max + 1) * (u + v_max + 1) <= bound) v_max++;

    return max(v_max, 0LL);
}

ll S(ll k) {
    ll bound = 2LL * k * k;
    ll total = 0;

    for (ll u = 1; u <= k - 2; u++) {
        ll vm_area = max_v_for_u(u, bound);
        if (vm_area < 1) break;  // monotone: larger u won't work either

        ll vm_range = k - 1 - u;
        if (vm_range < 1) break;

        ll vm = min(vm_area, vm_range);

        // Sum_{v=1}^{vm} (k - u - v) = vm*(k-u) - vm*(vm+1)/2
        total += vm * (k - u) - vm * (vm + 1) / 2;
    }

    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Verify small cases
    cout << "Small cases:" << endl;
    for (int k = 3; k <= 20; k++) {
        cout << "  S(" << k << ") = " << S(k) << endl;
    }

    // Compute moderate cases
    cout << endl;
    for (ll k : {100LL, 1000LL, 10000LL, 100000LL}) {
        auto t0 = chrono::high_resolution_clock::now();
        ll result = S(k);
        auto t1 = chrono::high_resolution_clock::now();
        double ms = chrono::duration<double, milli>(t1 - t0).count();
        cout << "S(" << k << ") = " << result << "  (" << ms << " ms)" << endl;
    }

    // Compute answer
    cout << endl << "Computing S(10^6)..." << endl;
    auto t0 = chrono::high_resolution_clock::now();
    ll answer = S(1000000LL);
    auto t1 = chrono::high_resolution_clock::now();
    double sec = chrono::duration<double>(t1 - t0).count();

    cout << "S(10^6) = " << answer << "  (" << sec << " s)" << endl;
    cout << endl << "Answer: " << answer << endl;

    return 0;
}

Python project_euler/problem_397/solution.py

"""
Project Euler Problem 397 -- Triangle on Parabola

On the parabola y = x^2/k, three points with integer x-coordinates
a < b < c (with 0 < a < b < c <= k) form a triangle with area:

    Area = (b-a)(c-b)(c-a) / (2k)

S(k) = number of such triples with Area <= k,
i.e., (b-a)(c-b)(c-a) <= 2k^2.

Substituting u = b-a, v = c-b:
    u*v*(u+v) <= 2k^2,  u >= 1, v >= 1,  u+v <= k-1
    number of valid a values = k - u - v

S(k) = sum over valid (u,v) of (k - u - v).

For each u, find max v via solving u*v^2 + u^2*v <= 2k^2 (quadratic in v).
"""

import math
import time

def max_v_for_u(u: int, bound: int):
    """
    Find largest integer v >= 1 such that u * v * (u + v) <= bound.
    Equivalent to u*v^2 + u^2*v <= bound.
    Quadratic formula: v <= (-u + sqrt(u^2 + 4*bound/u)) / 2.
    """
    if u * 1 * (u + 1) > bound:
        return 0
    disc = u * u + 4.0 * bound / u
    v_max = int((-u + math.sqrt(disc)) / 2.0)
    # Correct for floating point imprecision
    while v_max >= 1 and u * v_max * (u + v_max) > bound:
        v_max -= 1
    while u * (v_max + 1) * (u + v_max + 1) <= bound:
        v_max += 1
    return max(v_max, 0)

def S(k: int):
    """Compute S(k): count of triples (a,b,c) with 0 < a < b < c <= k
    such that (b-a)(c-b)(c-a) <= 2k^2."""
    bound = 2 * k * k
    total = 0
    for u in range(1, k - 1):
        # Max v from area constraint
        vm_area = max_v_for_u(u, bound)
        if vm_area < 1:
            break  # monotone: larger u won't help
        # Max v from c <= k constraint: u + v <= k - 1
        vm_range = k - 1 - u
        if vm_range < 1:
            break
        vm = min(vm_area, vm_range)
        # Sum_{v=1}^{vm} (k - u - v) = vm*(k - u) - vm*(vm+1)/2
        total += vm * (k - u) - vm * (vm + 1) // 2
    return total

def S_brute(k: int):
    """Brute force S(k) for verification."""
    bound = 2 * k * k
    count = 0
    for a in range(1, k - 1):
        for b in range(a + 1, k):
            for c in range(b + 1, k + 1):
                if (b - a) * (c - b) * (c - a) <= bound:
                    count += 1
    return count

def verify_small():
    """Verify optimized solution against brute force for small k."""
    print("Verifying against brute force...")
    all_ok = True
    for k in range(3, 30):
        s_opt = S(k)
        s_brute_val = S_brute(k)
        status = "OK" if s_opt == s_brute_val else "FAIL"
        if status == "FAIL":
            all_ok = False
        print(f"  S({k:3d}) = {s_opt:8d}  (brute: {s_brute_val:8d})  [{status}]")
    print(f"Verification: {'PASSED' if all_ok else 'FAILED'}\n")
    return all_ok

def create_visualization(k_values, s_values):
    """Create visualization and save to visualization.png."""