Problem 952: Integer Points on Ellipses

Mathematical Foundation

Theorem 1 (Generalized Gauss Circle Problem). The number of lattice points $(x, y) \in \mathbb{Z}^2$ inside the ellipse $Ax^2 + By^2 \le N$ satisfies

for any $\varepsilon > 0$.

Proof. The leading term equals the area of the ellipse $Ax^2 + By^2 \le N$, which has semi-axes $a = \sqrt{N/A}$ and $b = \sqrt{N/B}$, giving area $\pi ab = \pi N/\sqrt{AB}$. Each lattice point $(x,y)$ can be associated with the unit square $[x, x+1) \times [y, y+1)$. The discrepancy between $L(N)$ and the area arises from unit squares that straddle the ellipse boundary. The boundary has arc length $O(\sqrt{N})$, and each boundary-straddling square contributes $O(1)$ error, so the total error is $O(\sqrt{N})$. Sharper bounds (e.g., $O(N^{131/416})$ via Huxley’s method) require deeper analytic techniques. $\square$

Lemma 1 (Slice Counting). For fixed $x$ with $3x^2 \le N$, the number of integers $y$ satisfying $3x^2 + 5y^2 \le N$ is

Proof. The constraint $5y^2 \le N - 3x^2$ yields $|y| \le \sqrt{(N - 3x^2)/5}$. The integer solutions are $y \in \{-M, -M+1, \ldots, M\}$ where $M = \lfloor\sqrt{(N-3x^2)/5}\rfloor$. This set has cardinality $2M + 1$. $\square$

Theorem 2 (Exact Count via Slicing). The total lattice point count is

Proof. For each integer $x$ with $|x| \le \lfloor\sqrt{N/3}\rfloor$, we have $3x^2 \le N$, so the slice is non-empty. Lemma 1 gives the count for each slice. Summing over all valid $x$ counts every lattice point $(x,y)$ with $3x^2 + 5y^2 \le N$ exactly once, since the slices partition the lattice points by their $x$-coordinate. $\square$

Lemma 2 (Symmetry Reduction). By the symmetry $(x, y) \mapsto (-x, y)$:

where $M_0 = \lfloor\sqrt{N/5}\rfloor$ is the $y$-range at $x = 0$.

Proof. The $x = 0$ slice contributes $2M_0 + 1$ points. For $x \ne 0$, the slices at $x$ and $-x$ have identical $y$-ranges (since $3x^2 = 3(-x)^2$), so each pair contributes twice the count of a single slice. $\square$

Editorial

Count integer (x, y) with 3x^2 + 5y^2 <= N, where N = 10^6. The lattice point count for ellipse Ax^2 + By^2 <= N is approximately pi*N/sqrt(AB), with error O(sqrt(N)). We compute exactly by slicing: for each valid x, count y-values satisfying y^2 <= (N - 3x^2) / 5. Complexity: O(sqrt(N)) time, O(1) space.

Pseudocode

    x_max = floor(sqrt(N / 3))
    count = 0
    For x from -x_max to x_max:
        R = N - 3 * x * x
        y_max = floor(sqrt(R / 5))
        count = count + 2 * y_max + 1
    Return count

Complexity Analysis

• Time: $O(\sqrt{N/3}) = O(\sqrt{N})$ iterations of the outer loop, each performing $O(1)$ work (one integer square root computation).
• Space: $O(1)$ beyond the loop variable and accumulator.

For $N = 10^6$: approximately $577$ iterations.

Answer

/*
 * Problem 952: Integer Points on Ellipses
 *
 * Count integer (x, y) with 3x^2 + 5y^2 <= N, N = 10^6.
 *
 * For each x in [-sqrt(N/3), sqrt(N/3)], count y in [-M, M] where
 * M = floor(sqrt((N - 3x^2) / 5)).
 *
 * Complexity: O(sqrt(N)) time, O(1) space.
 */

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

int main() {
    const long long N = 1000000;
    long long count = 0;

    int max_x = (int)sqrt((double)N / 3.0);
    // Adjust for floating-point imprecision
    while (3LL * (max_x + 1) * (max_x + 1) <= N) max_x++;
    while (3LL * max_x * max_x > N) max_x--;

    for (int x = -max_x; x <= max_x; x++) {
        long long rem = N - 3LL * x * x;
        if (rem < 0) continue;

        int max_y = (int)sqrt((double)rem / 5.0);
        // Correct floating-point floor
        while (5LL * (max_y + 1) * (max_y + 1) <= rem) max_y++;
        while (5LL * max_y * max_y > rem) max_y--;

        count += 2 * max_y + 1;
    }

    cout << count << endl;
    return 0;
}

"""
Problem 952: Integer Points on Ellipses

Count integer (x, y) with 3x^2 + 5y^2 <= N, where N = 10^6.

The lattice point count for ellipse Ax^2 + By^2 <= N is approximately
pi*N/sqrt(AB), with error O(sqrt(N)). We compute exactly by slicing:
for each valid x, count y-values satisfying y^2 <= (N - 3x^2) / 5.

Complexity: O(sqrt(N)) time, O(1) space.
"""

import numpy as np
from math import isqrt

def solve(N: int = 10**6) -> int:
    """Count integer points (x, y) with 3x^2 + 5y^2 <= N."""
    count = 0
    max_x = isqrt(N // 3)
    for x in range(-max_x, max_x + 1):
        rem = N - 3 * x * x
        if rem < 0:
            continue
        max_y = isqrt(rem // 5)
        # Verify floor correctness
        while 5 * max_y * max_y > rem:
            max_y -= 1
        count += 2 * max_y + 1
    return count

# --- Compute answer ---
N = 10**6
answer = solve(N)
area_approx = np.pi * N / np.sqrt(15)
print(f"Exact count:     {answer}")
print(f"Area estimate:   {area_approx:.1f}")
print(f"Relative error:  {abs(answer - area_approx) / area_approx:.4%}")
print(answer)