Project Euler

Four Representations Using Squares

We seek the positive integers n <= 2 x 10^9 that admit all four representations n &= a_1^2 + b_1^2, n &= a_2^2 + 2b_2^2, n &= a_3^2 + 3b_3^2, n &= a_7^2 + 7b_7^2, where every a_k and b_k is positiv...

Source sync May 21, 2026

Problem #0229

Level Level 12

Solved By 1,695

Languages C++, Python

Answer 11325263

Length 341 words

number_theoryalgebramodular_arithmetic

Consider the number $3600$. It is very special, because \begin {alignat*} {2} 3600 &= 48^2 + &&36^2\\ 3600 &= 20^2 + 2 \times &&40^2\\ 3600 &= 30^2 + 3 \times &&30^2\\ 3600 &= 45^2 + 7 \times &&15^2 \end {alignat*}

Similarly, we find that $88201 = 99^2 + 280^2 = 287^2 + 2 \times 54^2 = 283^2 + 3 \times 52^2 = 197^2 + 7 \times 84^2$. In 1747, Euler proved which numbers are representable as a sum of two squares. We are interested in the numbers $n$ which admit representations of all of the following four types: \begin {alignat*} {2} n &= a_1^2 + && b_1^2\\ n &= a_2^2 + 2 && b_2^2\\ n &= a_3^2 + 3 && b_3^2\\ n &= a_7^2 + 7 && b_7^2, \end {alignat*}

where the $a_k$ and $b_k$ are positive integers.

There are $75373$ such numbers that do not exceed $10^7$.

How many such numbers are there that do not exceed $2 \times 10^9$?

Problem 229: Four Representations Using Squares

Mathematical Development

For each coefficient $k \in \{1,2,3,7\}$ , define

R_k=\{a^2+k b^2 : a,b \ge 1\}.

The answer is the size of

R_1 \cap R_2 \cap R_3 \cap R_7

inside $[1,2\times 10^9]$ .

The direct issue is memory. A full Boolean table up to $2\times 10^9$ would be far too large, even before storing four copies. The key monotonicity observation is that for fixed $a$ and fixed $k$ , the values

a^2+k b^2

increase strictly with $b$ . Therefore, if we process the search interval in slices

[L,R),

then for each pair $(a,k)$ the admissible $b$ values inside that slice form one consecutive interval of integers. When we move to the next slice, the first relevant $b$ can never move backwards.

So it is enough to store four rolling pointers:

$b_1[a]$ for $a^2+b^2$ ,
$b_2[a]$ for $a^2+2b^2$ ,
$b_3[a]$ for $a^2+3b^2$ ,
$b_7[a]$ for $a^2+7b^2$ .

Inside one slice we mark every hit with a four-bit mask. At the end of the slice, a number belongs to the intersection exactly when all four bits are set.

This computes the intersection exactly, but only uses memory proportional to the slice size.

Editorial

The brute-force formulation is not actually the enemy here; global storage is. For each of the four quadratic forms, the set of represented values is sparse, but the search interval is enormous. The useful observation is that the curves

a^2 + k b^2

are monotone in $b$ , so once a certain $b$ has moved past the current slice, it never needs to be revisited.

That is why the implementation keeps the interval in rolling blocks of one million integers. For every $a$ , it remembers where each form last left off in $b$ , resumes from there, and marks only the values that land in the current block. A single byte per value is enough: four bits record which of the four forms hit that value. After all $(a,b)$ pairs that can reach the block have been processed, the bytes equal to 1111 are exactly the numbers represented in all four ways.

Pseudocode

Choose a block size B.
For every a up to sqrt(N), initialize four pointers:
    b1[a], b2[a], b3[a], b7[a] = 1.

For each block [L, R):
    clear a byte array of length R - L

    For a from 1 upward while a^2 + b1[a]^2 < R:
        continue the sequence a^2 + b^2 from b = b1[a]
            and set bit 0 for every hit inside the block
        continue the sequence a^2 + 2b^2 from b = b2[a]
            and set bit 1
        continue the sequence a^2 + 3b^2 from b = b3[a]
            and set bit 2
        continue the sequence a^2 + 7b^2 from b = b7[a]
            and set bit 3

        store the first unused b back into the corresponding pointer

    Count how many entries in the block have all four bits set.
Add those counts over all blocks.

Complexity Analysis

Time: Proportional to the total number of marked values $a^2 + k b^2 \le N$ across the four forms.
Space: $O(B + \sqrt N)$ for the current slice and the rolling $b$ pointers.

Answer

\boxed{11325263}

C++ project_euler/problem_229/solution.cpp

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

const unsigned int SliceSize = 1000 * 1000;
const unsigned char One = 1 << 0;
const unsigned char Two = 1 << 1;
const unsigned char Three = 1 << 2;
const unsigned char Seven = 1 << 3;
const unsigned char All = One | Two | Three | Seven;

int main() {
    const unsigned int limit = 2000000000U;
    const unsigned int exclusive = limit + 1;
    const unsigned int maxA = (unsigned int)sqrt((double)limit);

    vector<unsigned int> b1(maxA + 1, 1);
    vector<unsigned int> b2(maxA + 1, 1);
    vector<unsigned int> b3(maxA + 1, 1);
    vector<unsigned int> b7(maxA + 1, 1);

    unsigned int count = 0;
    unsigned int from = 0;

    while (from < exclusive) {
        unsigned int to = from + SliceSize;
        if (to > exclusive) {
            to = exclusive;
        }

        vector<unsigned char> used(to - from, 0);

        for (unsigned int a = 1; (uint64_t)a * a + (uint64_t)b1[a] * b1[a] < to; a++) {
            unsigned int aa = a * a;

            unsigned int b = b1[a];
            for (; aa + (uint64_t)b * b < to; b++) {
                used[aa + b * b - from] |= One;
            }
            b1[a] = b;

            b = b2[a];
            for (; aa + 2ULL * b * b < to; b++) {
                used[aa + 2U * b * b - from] |= Two;
            }
            b2[a] = b;

            b = b3[a];
            for (; aa + 3ULL * b * b < to; b++) {
                used[aa + 3U * b * b - from] |= Three;
            }
            b3[a] = b;

            b = b7[a];
            for (; aa + 7ULL * b * b < to; b++) {
                used[aa + 7U * b * b - from] |= Seven;
            }
            b7[a] = b;
        }

        for (unsigned char value : used) {
            if (value == All) {
                count++;
            }
        }

        from = to;
    }

    cout << count << '\n';
    return 0;
}

Python project_euler/problem_229/solution.py

"""
Problem 229: Four Representations Using Squares

For each slice [lo, hi), mark all values of

    a^2 + b^2,
    a^2 + 2b^2,
    a^2 + 3b^2,
    a^2 + 7b^2

that fall into the slice. The arrays b_k[a] remember where the previous slice
stopped, so every parabola continues from the correct b without restarting.
"""

from math import isqrt


SLICE_SIZE = 1_000_000
ONE = 1 << 0
TWO = 1 << 1
THREE = 1 << 2
SEVEN = 1 << 3
ALL = ONE | TWO | THREE | SEVEN


def solve():
    limit = 2_000_000_000
    exclusive = limit + 1
    max_a = isqrt(limit)

    b1 = [1] * (max_a + 1)
    b2 = [1] * (max_a + 1)
    b3 = [1] * (max_a + 1)
    b7 = [1] * (max_a + 1)

    count = 0
    block_start = 0

    while block_start < exclusive:
        block_end = min(block_start + SLICE_SIZE, exclusive)
        used = bytearray(block_end - block_start)

        a = 1
        while a * a + b1[a] * b1[a] < block_end:
            aa = a * a

            b = b1[a]
            while aa + b * b < block_end:
                used[aa + b * b - block_start] |= ONE
                b += 1
            b1[a] = b

            b = b2[a]
            while aa + 2 * b * b < block_end:
                used[aa + 2 * b * b - block_start] |= TWO
                b += 1
            b2[a] = b

            b = b3[a]
            while aa + 3 * b * b < block_end:
                used[aa + 3 * b * b - block_start] |= THREE
                b += 1
            b3[a] = b

            b = b7[a]
            while aa + 7 * b * b < block_end:
                used[aa + 7 * b * b - block_start] |= SEVEN
                b += 1
            b7[a] = b

            a += 1

        count += sum(1 for value in used if value == ALL)
        block_start = block_end

    print(count)


if __name__ == "__main__":
    solve()