Problem 135: Same Differences

Project Euler Problem 135 Solution

EulerSolve provides an optimized solution for Project Euler Problem 135, Same Differences, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We want to count how many integers $n \lt 10^6$ have exactly ten representations of the form $$x^2-y^2-z^2=n,$$ where $x$, $y$, and $z$ are positive integers in arithmetic progression. Because the three numbers are consecutive terms of one progression, they are not independent: once the middle term and the common difference are known, the triple is fixed. The key step is to convert the quadratic expression into a constrained factorization of $n$. After that, the problem becomes a sieve over admissible factor pairs rather than a search over triples. Mathematical Approach The implementations are built around one exact reformulation: every valid triple corresponds to one ordered factor pair $(u,v)$ of $n$ satisfying a congruence condition and a positivity bound. Parameterizing the arithmetic progression If $x$, $y$, and $z$ are in arithmetic progression, we may write $$x=a+d,\qquad y=a,\qquad z=a-d,$$ with integers $a \ge 1$ and $d \ge 1$. The positivity of $z$ forces $a>d$. Substituting into the expression gives $$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$ So every solution is encoded by two positive integers: the middle term $a$ and the quantity $4d-a$....

Detailed mathematical approach

Problem Summary

Three positive integers $x$, $y$ and $z$ are consecutive terms of an arithmetic progression, so that $y$ is the middle term and $y-x=z-y$. For a positive integer $n$, a solution is such a triple with

$$x^2-y^2-z^2=n.$$

The least $n$ with exactly two solutions is $27$, with $34^2-27^2-20^2=27$ and $12^2-9^2-6^2=27$, and the least $n$ with exactly ten solutions is $1155$. We must find how many values of $n$ below one million have exactly ten distinct solutions. ^[1]

The whole solution in one sentence: writing the progression as $y+d$, $y$, $y-d$ turns the equation into $n=y(4d-y)$, so the solutions of $n$ are exactly its factorisations $n=uv$ in which $u+v$ is divisible by $4$ and $v\lt3u$, and one sweep over all such pairs with $uv$ below one million counts the solutions of every $n$ at once.

Mathematical Approach

We turn the equation into a statement about the divisors of $n$, check it on the numbers of the statement, find which $n$ can have solutions at all, and then count the solutions of all $n$ below the limit in one sweep.

1. The progression around its middle term

For example, $(5,3,1)$ has the middle term $3$ and steps of $2$, and $5^2-3^2-1^2=15$. Written as $(3+2,3,3-2)$, it suggests describing every progression by its middle term and one step. Let $d=x-y$. In an arithmetic progression the difference between neighbouring terms is constant, ^[2] so $y-z=d$ as well, and the triple is $x=y+d$, $y$, $z=y-d$. So far $d$ may be any integer, positive, zero or negative. The outer terms satisfy $x-z=2d$ and $x+z=2y$, so the difference of two squares ^[3] gives $x^2-z^2=(x-z)(x+z)=4yd$, and

$$\begin{aligned}n&=x^2-y^2-z^2\\&=4yd-y^2=y\,(4d-y).\end{aligned}$$

Since $y$ and $n$ are positive, the second factor is positive too: $4d\gt y\ge1$, so $d\ge1$. Every solution is therefore a decreasing progression; a constant or increasing one, with $d\le0$, makes the left-hand side negative. The last term $z=y-d$ is positive exactly when $d\lt y$. So the solutions of $n$ correspond one to one to the pairs of integers $(y,d)$ with

$$d\lt y\lt4d,\qquad y\,(4d-y)=n.$$

The example above is $(y,d)=(3,2)$, with $3\cdot(8-3)=15$. The two solutions of the statement are $(y,d)=(9,3)$, with $9\cdot(12-9)=27$, and $(y,d)=(27,7)$, with $27\cdot(28-27)=27$.

2. A factorisation in disguise

Put $u=y$ and $v=4d-y$. Then $uv=n$ and $u+v=4d$, and the conditions of Section 1 become $v\ge1$, divisibility of $u+v$ by $4$, and, from $d\lt y$, $u+v\lt4u$, that is, $v\lt3u$. We write $a\equiv b\pmod m$, read "$a$ is congruent to $b$ modulo $m$", when $m$ divides $a-b$. ^[4]

Claim. For every $n\ge1$, the solutions of $n$ correspond one to one to the ordered pairs of positive integers $(u,v)$ with

$$\begin{gathered}uv=n,\qquad v\lt3u,\\u+v\equiv0\pmod4.\end{gathered}$$

Proof. A solution gives such a pair, as just shown. Conversely, take such a pair and put $y=u$ and $d=(u+v)/4$, an integer because $4$ divides $u+v$. Then $x=y+d=(5u+v)/4$ and $z=y-d=(3u-v)/4$ are integers, and $z$ is positive because $v\lt3u$. The three numbers are consecutive terms of a progression with difference $-d$, and by Section 1, $x^2-y^2-z^2=y(4d-y)=uv=n$. The two constructions undo each other, because $(u,v)=(y,4d-y)$ and $(y,d)=(u,(u+v)/4)$ determine each other. This proves the claim.

Let $s(n)$ be the number of solutions of $n$. By the claim, $s(n)$ is the number of divisors $u$ of $n$ whose partner $v=n/u$ satisfies the two conditions. Multiplying $v\lt3u$ by $u$ gives the equivalent form $n\lt3u^2$, so only divisors larger than $\sqrt{n/3}$ can count.

3. The numbers of the statement by hand

For $n=27$ the ordered factor pairs are $(1,27)$, $(3,9)$, $(9,3)$ and $(27,1)$. Their sums $28$, $12$, $12$ and $28$ are all divisible by $4$, and $v\lt3u$ fails for $(1,27)$ and $(3,9)$. The pairs $(9,3)$ and $(27,1)$ remain; they give $d=3$ and $d=7$, and so the two solutions $(12,9,6)$ and $(34,27,20)$ of the statement.

The smaller number $15$ has even more solutions. Its pairs $(1,15)$, $(3,5)$, $(5,3)$ and $(15,1)$ have the sums $16$, $8$, $8$ and $16$, and only $(1,15)$ fails $v\lt3u$. So $s(15)=3$, with the solutions $(5,3,1)$, $(7,5,3)$ and $(19,15,11)$. Below $30$ exactly twelve numbers have a solution: $s(15)=3$, $s(27)=2$, and $s(n)=1$ for $n=3$, $4$, $7$, $11$, $12$, $16$, $19$, $20$, $23$ and $28$. The word "exactly" in the statement matters: $27$ is the least number with exactly two solutions, although $15$ already has three. For $k=1,2,\dots,10$ the least numbers with exactly $k$ solutions are $3$, $27$, $15$, $63$, $135$, $384$, $315$, $960$, $1995$ and $1155$, a sequence that goes up and down. ^[6]

4. Which numbers have solutions

The congruence already restricts which $n$ can have solutions. If $u+v\equiv0\pmod4$, then $u\equiv-v$, and since congruences may be multiplied, ^[4] $n=uv\equiv-v^2\pmod4$. A square leaves the remainder $0$ or $1$ after division by $4$, so $n\equiv0$ or $n\equiv3\pmod4$. More precisely:

If $n\equiv3\pmod4$, then $n$ is odd, so $u$ and $v$ are odd, and because $uv\equiv3\pmod4$, one of them is $\equiv1$ and the other $\equiv3\pmod4$. Every factor pair of $n$ satisfies the congruence.
If $n\equiv0\pmod4$, the congruence $u\equiv-v\pmod4$ makes $u$ and $v$ both odd or both even, and since $uv$ is even, both are even: $u=2u'$ and $v=2v'$ with $u'v'=n/4$ and $u'+v'$ even. If $n/4$ is odd, $u'$ and $v'$ are odd, so every factor pair of $n/4$, doubled, satisfies the congruence. If $n/4\equiv2\pmod4$, then $u'$ and $v'$ can be neither both odd nor both even, so there is no solution. If $16$ divides $n$, then $u'$ and $v'$ are both even, $u=4a$ and $v=4b$ with $ab=n/16$, and every factor pair of $n/16$, multiplied by $4$, satisfies the congruence.

In each case the condition $v\lt3u$ becomes the same condition for the smaller pair, $v'\lt3u'$ or $b\lt3a$. Let $D(m)$ be the number of divisors $a$ of $m$ with $3a^2\gt m$. Then:

$s(n)=D(n)$ if $n\equiv3\pmod4$;
$s(n)=D(n/4)$ if $n\equiv4\pmod8$;
$s(n)=D(n/16)$ if $n\equiv0\pmod{16}$;
$s(n)=0$ for all other $n$, that is, for $n\equiv1$ or $2\pmod4$ and for $n\equiv8\pmod{16}$.

Since $a=m$ always counts, $D(m)\ge1$, so the numbers with a solution are exactly those in the first three classes, $7$ of every $16$ consecutive integers, in agreement with the formula section of OEIS A334566. ^[5] For example, $1155=3\cdot5\cdot7\cdot11\equiv3\pmod4$ has $16$ divisors, and $3u^2\gt1155$ means $u^2\gt385$, that is $u\ge20$. Exactly ten divisors qualify, $21$, $33$, $35$, $55$, $77$, $105$, $165$, $231$, $385$ and $1155$, so $s(1155)=10$, as the statement says. The programs do not use this formula, but it gives an independent check of the sweep below.

5. One sweep for all numbers

Instead of factorising every $n$ below $N=10^6$ separately, we turn the claim of Section 2 around: we run through all admissible pairs $(u,v)$ with $uv\lt N$, the points of a region under the hyperbola $uv=N-1$, and add $1$ to a counter for the number $n=uv$. By the claim, the counter of $n$ ends at $s(n)$.

For a fixed $u$, the congruence says $v\equiv-u\pmod4$, so the admissible $v$ form an arithmetic progression with step $4$. It starts at the least positive member $r(u)$ of that residue class, which is $4$, $3$, $2$ or $1$ for $u\equiv0$, $1$, $2$ or $3\pmod4$, and it runs up to the bound

$$V(u)=\min\Bigl(3u-1,\ \Bigl\lfloor\frac{N-1}{u}\Bigr\rfloor\Bigr),$$

because $3u-1$ is the largest $v$ with $v\lt3u$ and $\lfloor(N-1)/u\rfloor$ is the largest $v$ with $uv\le N-1$. The first factor runs from $1$ to $N-1$, and it really can be that large: for $n\equiv3\pmod4$ the pair $(n,1)$ is admissible, and it gives the solution $\bigl((5n+1)/4,\,n,\,(3n-1)/4\bigr)$, which is $(34,27,20)$ for $n=27$. The two bounds cross near $u=\sqrt{N/3}$: for $N=10^6$ the bound $3u-1$ is the smaller one for $u\le577$, and the product bound for $u\ge578$. Every admissible pair with $uv\lt N$ is visited exactly once, because every $u$ is visited once and, for a fixed $u$, the visited $v$ are exactly the admissible ones. So after the sweep every counter is right, and the answer is the number of $n\lt N$ whose counter equals $10$.

6. Worked example: the sweep for $N=30$

For $N=30$ the sweep visits fifteen pairs:

$u=2$: $v=2$, so $n=4$;
$u=3$: $v=1$ and $v=5$, so $n=3$ and $n=15$;
$u=4,5,6,7$: $v=4,3,2,1$, so $n=16,15,12,7$;
$u=9,10,11$: $v=3,2,1$, so $n=27,20,11$;
$u=14$: $v=2$, so $n=28$;
$u=15,19,23,27$: $v=1$, so $n=u$.

For every other $u$ the start $r(u)$ already exceeds $V(u)$. For example, $V(1)=\min(2,29)=2$ is less than $r(1)=3$, and $V(8)=\min(23,3)=3$ is less than $r(8)=4$; from $u=15$ on $V(u)=1$, and only the $u\equiv3\pmod4$ have $r(u)=1$. The counters end at $3$ for $n=15$, at $2$ for $n=27$ and at $1$ for the ten other numbers listed in Section 3, exactly as found there by hand.

How the Code Works

The C++ program ^[9] starts in main, which reads its options with parse_arguments into a small Options structure with the defaults limit = 1000000, exact = 10 and run_checkpoints = true. The options --limit=N and --exact=K are read by parse_int_after_prefix, which accepts only a nonempty string of decimal digits but does not check that the value fits into an int, and --skip-checkpoints switches the checkpoint off. Any other argument, a limit below $2$ or an exact count below $1$ ends the program with exit status $1$. Unless it is switched off, run_checkpoints then verifies that solve(10000, 10) returns $45$, the number of $n\lt10^4$ with exactly ten solutions, and stops the program with exit status $2$ otherwise. Finally main prints solve(limit, exact).

solve is the sweep of Section 5. It creates a std::vector<int> named count with limit zeros, one counter for each $n\lt N$, where $N$ is limit. For every $u$ from $1$ to $N-1$ it computes vmax = (limit - 1) / u, which is $\lfloor(N-1)/u\rfloor$ because integer division of positive numbers rounds down, and upper, the smaller of vmax and 3 * u - 1, which is $V(u)$. The guard upper < 1 never fires, since both bounds are at least $1$ for $u\le N-1$. The start $r(u)$ comes from (-u) % 4: in C++ the remainder of a negative number is zero or negative, so the code adds $4$ to a negative remainder and replaces $0$ by $4$. The inner loop then increments count[u * v] for $v=r(u),\,r(u)+4,\dots$ up to upper. A last loop over $n=1,\dots,N-1$ counts the entries equal to exact. Plain int is enough for the default limit: 3 * u - 1 stays below $3\cdot10^6$, every product $uv$ is at most $N-1$, and no counter below one million exceeds $71$. For a limit above $715\,827\,883$, however, 3 * u would exceed the largest int, $2^{31}-1$.

The Python program calls solve() at module level, and the Java program runs the sweep directly in main; both use the fixed limit $N=10^6$ and the count $10$, without options or checkpoint, and print the result. Python's % already returns a remainder between $0$ and $3$ for the modulus $4$, so (-u) % 4 needs only the replacement of $0$ by $4$; Python keeps the counters in a list and runs the inner loop as a while loop. Java's % behaves like the C++ one, and ((-u) % 4 + 4) % 4 brings the remainder into the range from $0$ to $3$; the counters are an int[].

Complexity and Verification

The outer loop and the final scan each run $N-1$ times. For each $u$ the inner loop makes at most $\lfloor(N-1)/u\rfloor$ steps, and the harmonic sum $1+\frac12+\dots+\frac1{N-1}$ is at most $1+\ln N$, ^[8] so the time is $O(N\log N)$. The exact number of steps is $\sum_{n\lt N}s(n)$, one per admissible pair, and a finer count gives its size. Let $m=\lfloor\sqrt{N/3}\rfloor$. For $u\le m$ the bound $3u-1$ applies, and these $u$ contribute $\sum_{u\le m}3u/4+O(m)$, that is $N/8+O(\sqrt N)$ steps. For $u\gt m$ the product bound $q=\lfloor(N-1)/u\rfloor$ applies. Among consecutive $u$ with the same $q$, any four start in the four residue classes and together make exactly $q$ steps, and each of the at most three leftover $u$ makes fewer than one step more or less than $q/4$. Since $q\lt\sqrt{3N}$ there, $q$ takes only $O(\sqrt N)$ values, so these $u$ make a quarter of $T=\sum_{m\lt u\lt N}\lfloor(N-1)/u\rfloor$ steps, up to $O(\sqrt N)$. Dirichlet's formula for the divisor summatory function, ^[7]

$$\begin{aligned}\sum_{u\le x}\Bigl\lfloor\frac xu\Bigr\rfloor&=x\ln x+(2\gamma-1)\,x\\&\quad+O\bigl(\sqrt x\bigr),\end{aligned}$$

where $\gamma\approx0.5772$ is the Euler–Mascheroni constant, and $\sum_{u\le m}1/u=\ln m+\gamma+O(1/m)$ ^[8] give

$$\begin{aligned}T&=N\ln N+(2\gamma-1)N\\&\quad-N(\ln m+\gamma)+O\bigl(\sqrt N\bigr)\\&=\tfrac N2\ln(3N)+(\gamma-1)N\\&\quad+O\bigl(\sqrt N\bigr).\end{aligned}$$

Adding a quarter of $T$ to $N/8$ gives

$$\begin{aligned}\sum_{n\lt N}s(n)&=\tfrac N8\bigl(\ln(3N)+2\gamma-1\bigr)\\&\quad+O\bigl(\sqrt N\bigr).\end{aligned}$$

For $N=10^6$ the main term is about $1\,883\,569$, and the program makes exactly $1\,883\,345$ steps; for $N=10^4$ the two numbers are $13\,079$ and $13\,063$. The memory that grows with $N$ is the counter array: $10^6$ four-byte integers, about 4 MB, in C++ and Java, and a list of $10^6$ references, about 8 MB on a 64-bit machine, in Python. In tests on a desktop computer, the C++ program finished in a few milliseconds, the Java program in a few hundredths of a second and the Python program in about a fifth of a second.

Before the main run, the C++ program checks the value $45$ for $N=10^4$. The first of these $45$ numbers are $1155$, $1755$, $1920$, $2079$ and $2304$; $19$ of them are $\equiv3\pmod4$, $6$ are $\equiv4\pmod8$ and $20$ are multiples of $16$, so all three classes of Section 4 occur. For this article the following checks were also run; they are not part of the published solutions. A direct search over all triples $(x,y,2y-x)$ of positive integers with $x\le1502$ gives the same $s(n)$ as the sweep for every $n\lt1200$. It misses no solution: by Section 2, $4x=5u+v$, and $(v-1)(5u-1)\ge0$ gives $5u+v\le5uv+1=5n+1$, so $x\le1499$. An enumeration of the pairs $(y,d)$ with $d\lt y\lt4d$ agrees with the sweep for every $n\lt20000$. The formula of Section 4, evaluated with lists of divisors, agrees with the sweep for every $n\lt10^6$ and gives the same number of values with exactly ten solutions as the programs. The sweep reproduces the $88$ listed terms of OEIS A334566 and the least values of OEIS A334567 for every $k\le40$, among them $27$ for $k=2$ and $1155$ for $k=10$. The C++ program, built with Clang and with GCC, prints $1$ for --limit=1156 and $0$ for --limit=1155, and the C++, Java and Python programs print the same number for the full problem.

Footnotes and References

The references below supply the background facts used above. The correspondence between solutions and factor pairs, the formula for $s(n)$ by residue classes and the step count of the sweep are derived explicitly in this article.

Project Euler 135 — Same Differences. The official statement: x, y and z are positive integers that are consecutive terms of an arithmetic progression; the least positive n for which x² − y² − z² = n has exactly two solutions is 27, with 34² − 27² − 20² = 12² − 9² − 6² = 27, and the least n with exactly ten solutions is 1155. The task asks how many values of n below one million have exactly ten distinct solutions.
Wikipedia — Arithmetic progression. In an arithmetic progression the difference between each term and the term before it is the same throughout, the common difference d, and the n-th term is a₁ + (n − 1)d.
Wikipedia — Difference of two squares. The identity a² − b² = (a + b)(a − b), used in Section 1 with a = x and b = z.
Wikipedia — Modular arithmetic. Two integers are congruent modulo m when their difference is a multiple of m, and congruence modulo m is compatible with addition and multiplication; Sections 2, 4 and 5 use these facts.
OEIS A334566 — Solutions of z² − y² − x² = n > 0 for consecutive terms of an arithmetic progression. In the entry the largest term is called z, so its equation is ours with x and z exchanged. Its comments write n = y(4d − y) with the common difference d; its formula section states that a(n) = 0 exactly when n ≡ 1 or 2 (mod 4) or n ≡ 8 (mod 16), and its examples include a(15) = 3.
OEIS A334567 — Least value with exactly n solutions. The terms for n = 0, 1, 2, … begin 1, 3, 27, 15, 63, 135, 384, 315, 960, 1995, 1155, and the entry remarks that the sequence is not increasing, since a(2) = 27 is greater than a(3) = 15.
Wikipedia — Divisor summatory function. D(x), the sum of the numbers of divisors of all n ≤ x, equals the sum of ⌊x/k⌋ over k ≤ x and counts the lattice points under the hyperbola jk = x; Dirichlet showed that D(x) = x log x + x(2γ − 1) + O(√x).
Wikipedia — Harmonic number. The difference Hₙ − ln n decreases monotonically towards the Euler–Mascheroni constant γ ≈ 0.5772156649, starting from H₁ − ln 1 = 1, and the asymptotic expansion Hₙ = ln n + γ + 1/(2n) − … holds.
C++ — Euler135.cpp. The linked immutable C++ revision contains parse_arguments, solve and the checkpoint 45 for the limit 10 000 in run_checkpoints. It is the implementation record for this article.

Problem 135 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Options {
    int limit = 1000000;
    int exact = 10;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit) ||
            parse_int_after_prefix(arg, "--exact=", options.exact)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2 && options.exact >= 1;
}

int solve(const int limit, const int exact) {
    std::vector<int> count(static_cast<std::size_t>(limit), 0);

    for (int u = 1; u < limit; ++u) {
        const int vmax = (limit - 1) / u;
        const int upper = std::min(vmax, 3 * u - 1);
        if (upper < 1) {
            continue;
        }

        int v = (-u) % 4;
        if (v < 0) {
            v += 4;
        }
        if (v == 0) {
            v = 4;
        }

        for (; v <= upper; v += 4) {
            ++count[static_cast<std::size_t>(u * v)];
        }
    }

    int answer = 0;
    for (int n = 1; n < limit; ++n) {
        if (count[static_cast<std::size_t>(n)] == exact) {
            ++answer;
        }
    }
    return answer;
}

bool run_checkpoints() {
    if (solve(10000, 10) != 45) {
        std::cerr << "Checkpoint failed for limit=10000, exact=10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit, options.exact) << '\n';
    return 0;
}

Python

# Problem 135: Same differences
# x^2 - y^2 - z^2 = n, where x,y,z is AP. Count n < 10^6 with exactly 10 solutions.

def solve():
    limit = 1000000
    count = [0] * limit
    for u in range(1, limit):
        vmax = min((limit - 1) // u, 3 * u - 1)
        if vmax < 1: continue
        v = (-u) % 4
        if v == 0: v = 4
        while v <= vmax:
            count[u * v] += 1
            v += 4
    print(sum(1 for n in range(1, limit) if count[n] == 10))

solve()

Java

public class Euler135 {
    public static void main(String[] args) {
        int limit = 1000000;
        int[] count = new int[limit];
        for (int u = 1; u < limit; u++) {
            int vm = Math.min((limit - 1) / u, 3 * u - 1);
            if (vm < 1)
                continue;
            int v = ((-u) % 4 + 4) % 4;
            if (v == 0)
                v = 4;
            for (; v <= vm; v += 4)
                count[u * v]++;
        }
        int ans = 0;
        for (int n = 1; n < limit; n++)
            if (count[n] == 10)
                ans++;
        System.out.println(ans);
    }
}