Project Euler

Square Subsets

Count subsets of {1,..., n} whose product is a perfect square.

Source sync Apr 19, 2026

Problem #0619

Level Level 23

Solved By 486

Languages C++, Python

Answer 857810883

Length 115 words

linear_algebramodular_arithmeticbrute_force

For a set of positive integers $\{a, a+1, a+2, \dots , b\}$, let $C(a,b)$ be the number of non-empty subsets in which the product of all elements is a perfect square.

For example $C(5,10)=3$, since the products of all elements of $\{5, 8, 10\}$, $\{5, 8, 9, 10\}$ and $\{9\}$ are perfect squares, and no other subsets of $\{5, 6, 7, 8, 9, 10\}$ have this property.

You are given that $C(40,55) =15$, and $C(1000,1234) \bmod 1000000007=975523611$.

Find $C(1000000,1234567) \bmod 1000000007$.

Problem 619: Square Subsets

Mathematical Analysis

Represent each number by its prime factorization mod 2 (vector in $\mathbb{F}_2^k$ ). Count subsets with zero sum in $\mathbb{F}_2^k$ .

Derivation

The solution follows from the mathematical analysis above.

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$

Complexity Analysis

Time: See implementation.
Space: See implementation.

Answer

\boxed{857810883}

C++ project_euler/problem_619/solution.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

int main() {
    int n = 50;
    // Sieve primes up to n
    vector<int> primes;
    vector<bool> sieve(n + 1, true);
    for (int i = 2; i <= n; i++) {
        if (sieve[i]) {
            primes.push_back(i);
            for (int j = 2*i; j <= n; j += i) sieve[j] = false;
        }
    }
    int m = primes.size();
    
    // Build GF(2) matrix
    vector<vector<int>> rows(n, vector<int>(m, 0));
    for (int k = 1; k <= n; k++) {
        int temp = k;
        for (int i = 0; i < m; i++)
            while (temp % primes[i] == 0) { rows[k-1][i] ^= 1; temp /= primes[i]; }
    }
    
    // Gaussian elimination
    int rank = 0;
    for (int col = 0; col < m; col++) {
        int pivot = -1;
        for (int row = rank; row < n; row++)
            if (rows[row][col]) { pivot = row; break; }
        if (pivot < 0) continue;
        swap(rows[rank], rows[pivot]);
        for (int row = 0; row < n; row++)
            if (row != rank && rows[row][col])
                for (int c = 0; c < m; c++)
                    rows[row][c] ^= rows[rank][c];
        rank++;
    }
    
    // 2^(n-rank) - 1
    lll result = 1;
    for (int i = 0; i < n - rank; i++) result *= 2;
    cout << (ll)(result - 1) << endl;
    return 0;
}

Python project_euler/problem_619/solution.py

"""
Problem 619: Square Subsets
Count subsets of {1,...,n} whose product is a perfect square.
"""
from math import isqrt

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

def count_square_subsets(n):
    """Count non-empty subsets of {1,...,n} whose product is a perfect square.
    
    Represent each number by its exponent vector mod 2 over primes <= n.
    A subset has square product iff the XOR (sum mod 2) of all vectors is zero.
    
    This is equivalent to counting elements of the kernel of a GF(2) matrix.
    If the rank of the matrix is r and we have n vectors, then the number
    of subsets with zero sum is 2^(n-r) - 1 (excluding empty set).
    """
    primes = sieve(n)
    # Build matrix: each row is the exponent vector of a number mod 2
    matrix = []
    for k in range(1, n + 1):
        vec = [0] * len(primes)
        temp = k
        for i, p in enumerate(primes):
            while temp % p == 0:
                vec[i] ^= 1
                temp //= p
        matrix.append(vec)
    
    # Gaussian elimination over GF(2) to find rank
    m = len(primes)
    rows = [row[:] for row in matrix]
    rank = 0
    for col in range(m):
        # Find pivot
        pivot = -1
        for row in range(rank, n):
            if rows[row][col] == 1:
                pivot = row
                break
        if pivot == -1:
            continue
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        for row in range(n):
            if row != rank and rows[row][col] == 1:
                for c in range(m):
                    rows[row][c] ^= rows[rank][c]
        rank += 1
    
    # Number of subsets with square product = 2^(n - rank) - 1
    return pow(2, n - rank) - 1

# Verify small cases
# {1}: product=1=1^2, square. So count includes {1}.
c3 = count_square_subsets(3)
print(f"Square subsets of {{1,2,3}}: {c3}")
# {1}, {1,2,...} let's see: {1}->1, ok. Any subset containing only 1 and squares.

c10 = count_square_subsets(10)
print(f"Square subsets of {{1,...,10}}: {c10}")

c20 = count_square_subsets(20)
print(f"Square subsets of {{1,...,20}}: {c20}")