Problem 203: Squarefree Binomial Coefficients

Project Euler Problem 203 Solution

EulerSolve provides an optimized solution for Project Euler Problem 203, Squarefree Binomial Coefficients, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We work with the first 51 rows of Pascal's triangle, so the row index runs from $n=0$ through $n=50$. From those rows we collect all binomial coefficients $\binom{n}{k}$, keep only distinct values, and then add the ones that are squarefree. Define $$B=\left\{\binom{n}{k}:0\le n\le 50,\ 0\le k\le n\right\}.$$ Let $Q\subseteq B$ be the subset of squarefree values. The required quantity is $$A=\sum_{v\in Q} v.$$ The implementations avoid factorial formulas and avoid full prime factorizations. They generate each row multiplicatively, store coefficients in a set so duplicates disappear automatically, and then reject every value that has a square divisor greater than 1. Mathematical Approach The problem has only two real mathematical ingredients: how to enumerate binomial coefficients exactly, and how to recognize whether a positive integer is squarefree. Once those are clear, the final sum is just a filtered set sum. The distinct coefficient set Pascal's triangle contains many repeated numbers. Some repeats are internal to one row because of the symmetry $$\binom{n}{k}=\binom{n}{n-k}.$$ Other repeats occur across different rows, for example $$\binom{5}{2}=10=\binom{10}{1}.$$ Therefore the problem is not asking for a sum over positions $(n,k)$, but over the distinct numerical values that appear....

Detailed mathematical approach

Problem Summary

Row $n$ of Pascal's triangle consists of the binomial coefficients $\binom n0,\binom n1,\dots,\binom nn$, and the rows are numbered from $n=0$, so the first $51$ rows are the rows $n=0,1,\dots,50$. A positive integer is squarefree if no square of a prime divides it. We must find the sum of the distinct squarefree numbers in these rows; a value that occurs several times counts once. The statement checks this on the first eight rows: of their twelve distinct numbers $1,2,3,4,5,6,7,10,15,20,21$ and $35$, all except $4$ and $20$ are squarefree, and the squarefree ones add up to $105$. ^[1] ^[2]

The whole solution in one sentence: build each row from left to right by multiplying the previous entry by a simple fraction, keep each value once in a set, and add the values that no square greater than $1$ divides, a test that Legendre's formula for the prime factors of factorials reduces, in these rows, to the four squares $4$, $9$, $25$ and $49$.

Mathematical Approach

The task has three parts: produce every entry exactly, remove repeated values, and recognise squarefree numbers.

1. Repeated values

The first eight rows have $1+2+\dots+8=36$ entries but only $12$ distinct values. Values repeat for two reasons. Every row reads the same from both ends, $\binom nk=\binom n{n-k}$, because choosing the $k$ elements we keep is the same as choosing the $n-k$ we leave out. ^[3] And different rows share values: $6=\binom42=\binom61$ within the first eight rows, and $10=\binom52=\binom{10}1$ further down. In all, the first $51$ rows have $51\cdot52/2=1326$ entries but only $614$ distinct values, and the value $1$ alone fills $101$ places.

Among the twelve values of the first eight rows, $4=2^2$ and $20=2^2\cdot5$ are not squarefree. The others are $1$, which has no prime factor at all, the primes $2,3,5,7$ and the products $6=2\cdot3$, $10=2\cdot5$, $15=3\cdot5$, $21=3\cdot7$ and $35=5\cdot7$ of two different primes. Their sum is $1+2+3+5+6+7$${}+10+15+21+35=105$.

2. One row from left to right

Each row starts with $\binom n0=1$, and for $1\le k\le n$ every further entry follows from the one before it: ^[2] ^[3]

$$\binom nk=\binom n{k-1}\cdot\frac{n-k+1}{k}.$$

In row $7$ the fractions are $\tfrac71,\tfrac62,\tfrac53,\tfrac44$, $\tfrac35,\tfrac26,\tfrac17$, and the entries are $1,7,21,35,35,21,7,1$. With whole numbers the product must be formed before the division, and then the division is always exact:

$$\binom n{k-1}(n-k+1)=k\binom nk,$$

because $(n-k+1)!$ is $n-k+1$ times $(n-k)!$ and $k!$ is $k$ times $(k-1)!$, so the factorial formula turns both sides into $n!/\bigl((k-1)!\,(n-k)!\bigr)$. The product is exactly $k$ times the next entry. Dividing first would go wrong: $7$ divided by $2$ and rounded down is $3$, and $3\cdot6=18$, not $21$.

The numbers stay small. By Pascal's rule each entry of row $n+1$ is the sum of the two entries above it, so $\binom{n+1}k\ge\binom nk$; and within a row the fraction $(n-k+1)/k$ exceeds $1$ exactly when $k\lt(n+1)/2$, so the entries rise up to the middle and then fall. The largest entry is therefore $\binom{50}{25}=126410606437752$, below $2^{47}$, and the largest product formed is $k\binom nk=n\binom{n-1}{k-1}$, at most $50\binom{49}{24}=3160265160943800$, below $2^{52}$. Any sum of distinct entries is below the sum of all entries, $2^0+2^1+\dots+2^{50}=2^{51}-1$, since row $n$ adds up to $2^n$. ^[2] So 64-bit integers are more than enough.

3. Testing whether a number is squarefree

If a square $d^2$ with $d\gt1$ divides $v$, then so does $p^2$ for every prime $p$ that divides $d$. So $v$ is squarefree exactly when no square greater than $1$ divides it, ^[4] and since $p^2\mid v$ forces $p^2\le v$, only $p\le\sqrt v$ has to be tried. The programs test a value $v$ like this:

if $4$ divides $v$, then $v$ is not squarefree;
otherwise they try $p=3,5,7,9,\dots$ as long as $p^2\le v$, and $v$ is not squarefree as soon as $p^2$ divides $v$;
if no try succeeds, $v$ is squarefree.

The test rejects $v$ only after finding a square greater than $1$ that divides $v$. Conversely, if $q^2\mid v$ for a prime $q$, then $q=2$ is caught by the first step, and an odd $q$ has $q^2\le v$, so the loop reaches $q$ unless it has stopped before. Odd composite $p$ such as $9$ or $15$ can never be the first success, because a smaller prime factor of $p$ would have succeeded earlier; they only cost time. For example, $35$ is a multiple of none of $4$, $9$ and $25$, and $7^2=49\gt35$ ends the loop, so $35$ is squarefree; $20$ is rejected at once.

4. Legendre's formula

To see which squares can divide an entry, we count prime factors. Write $v_p(m)$ for the exponent of the prime $p$ in $m$, and $\lfloor x\rfloor$ for $x$ rounded down. Among $1,2,\dots,m$ there are $\lfloor m/p\rfloor$ multiples of $p$, $\lfloor m/p^2\rfloor$ multiples of $p^2$, and so on, and a number with exactly $i$ factors $p$ is counted in the first $i$ of these counts, once for each factor. This is Legendre's formula: ^[5]

$$v_p(m!)=\sum_{i\ge1}\left\lfloor\frac{m}{p^i}\right\rfloor.$$

For example, $v_2(6!)=3+1=4$, and indeed $6!=720=2^4\cdot45$. Applied to the three factorials in $\binom nk=n!/(k!\,(n-k)!)$, it gives

$$\begin{aligned}v_p\binom nk&=\sum_{i\ge1}t_i,\\ t_i&=\lfloor n/p^i\rfloor-\lfloor k/p^i\rfloor\\ &\qquad-\lfloor (n-k)/p^i\rfloor.\end{aligned}$$

Write $k=a\,p^i+r$ and $n-k=b\,p^i+s$ with remainders $0\le r,s\lt p^i$. Then $n=(a+b)\,p^i+(r+s)$ with $0\le r+s\lt2p^i$, so $t_i=1$ if $r+s\ge p^i$ and $t_i=0$ otherwise. If $p^i\gt n$, then $r+s=n\lt p^i$ and $t_i=0$. This proves the claim we need:

Claim. The exponent of a prime $p$ in $\binom nk$ is at most the number of powers $p,p^2,p^3,\dots$ that do not exceed $n$.

The condition $r+s\ge p^i$ means that adding $k$ and $n-k$ in base $p$ carries a digit out of the last $i$ places, so the exponent is the number of carries in this addition, which is Kummer's theorem. ^[6] For $\binom63=20$ and $p=2$ we get $t_1=3-1-1=1$ and $t_2=1-0-0=1$, the two carries of $11_2+11_2=110_2$; for $p=3$, $t_1=2-1-1=0$, and for $p=5$, $t_1=1-0-0=1$. Hence $20=2^2\cdot5$.

5. Only four squares matter

In the first $51$ rows we have $n\le50$. A prime $p\ge11$ has $p^2\ge121\gt50$, so by the claim it divides an entry at most once, and a prime $p\gt n$ does not divide $\binom nk$ at all, because it does not divide $n!$. Hence an entry of these rows is squarefree exactly when none of $4$, $9$, $25$ and $49$ divides it. In general, in rows $n\le N$ only the squares $p^2\le N$ of primes matter; in the first eight rows, where $n\le7$, only $4$ is left, which is why $4$ and $20$, the two multiples of $4$, are the values that fail.

All four squares are needed, since each of the entries $\binom41=4$, $\binom91=9$, $\binom{25}1=25$ and $\binom{49}1=49$ is divisible by only one of them. Testing the $614$ distinct values with $4$, $9$, $25$ and $49$ in this order, the first square that divides is $4$ for $328$ values, $9$ for $101$, $25$ for $23$ and $49$ for $4$, and the other $158$ values are squarefree. So the test of Section 3 rejects every entry that is not squarefree at the step with $4$ or at $p=3$, $5$ or $7$; only squarefree entries make the loop run up to $\sqrt v$. For the middle entries of the even rows there is a theorem: Granville and Ramaré proved in 1996, settling a conjecture of Erdős, that $\binom{2n}n$ is never squarefree for $n\gt4$. ^[4]

6. Worked example: the first ten rows

Rows $8$ and $9$ are $1,8,28,56,70,56,28,8,1$ and $1,9,36,84,126,126,84,36,9,1$. They add eight new values, $8,28,56,70$ and $9,36,84,126$. Here $n\le9$, and the only primes with $p^2\le9$ are $2$ and $3$, so by Section 5 only $4$ and $9$ have to be tried: $8$, $28$, $56$, $36$ and $84$ are multiples of $4$, $9$ and $126=2\cdot3^2\cdot7$ are multiples of $9$, and $70=2\cdot5\cdot7$ passes. The first ten rows therefore contain $20$ distinct values, $11$ of them squarefree, and the sum is $105+70=175$.

How the Code Works

The C++ program ^[7] accepts --skip-checkpoints and --rows= followed by digits, which parse_int_after_prefix reads into an int without an overflow check; parse_arguments answers anything else, or fewer than one row, with exit code $1$. Unless switched off, run_checkpoints requires solve(8) to return $105$, or the program exits with code $2$. Then main prints solve for the chosen number of rows, $51$ by default.

solve implements Sections 1 and 2 with a std::set of unsigned 64-bit integers, a sorted container that keeps one copy of each value. ^[8] In each row the variable c starts at $1$ and becomes c * (n - k + 1) / k for $k\ge1$, multiplication first, and every entry is inserted. Then the stored values accepted by is_squarefree, the test of Section 3 with an extra line that rejects $0$, are added up.

For $51$ rows the 64-bit arithmetic is safe by Section 2, but --rows= has no guard. Row $63$ is the first row in which a product $k\binom nk$ no longer fits into 64 bits; unsigned arithmetic then wraps around modulo $2^{64}$, ^[8] and from --rows=64 on some entries come out wrong: $\binom{63}{30}$, for instance, comes out as $139870765932034706$ instead of $860778005594247069$.

The Python program has no options and no checkpoint. Its nested is_squarefree is the same test, and its row loop stores c before moving on with c * (n - k) // (k + 1), the rule of Section 2 shifted by one place; the last update of a row yields $0$, which is never stored. Its integers have unlimited precision. ^[8] The Java program fixes $51$ rows in main: a TreeSet<Long> plays the part of the C++ set, the update is the Python one guarded by if (k < n), signed 64-bit long values are safe because every product stays below $2^{52}$, and isSquarefree is the C++ test.

Complexity and Verification

For $R$ rows the programs insert $R(R+1)/2$ entries, $1326$ here, each after at most one multiplication and one division; an insertion into a set of $U$ values, $U=614$ here, costs $O(\log U)$ steps in the sorted sets of C++ and Java and constant time on average in Python. ^[8] For the $51$ rows the squarefree tests dominate: a squarefree value needs about $\sqrt v/2$ passes of the loop, any other value at most three, by Section 5. In all, the loop runs $10421911$ times, only $159$ of them on values that are not squarefree, far below the worst-case bound $U\sqrt M/2\approx3.5\cdot10^9$ with $M=\binom{50}{25}$. The memory is $O(U)$, the set of $614$ numbers, and in tests on a desktop computer the C++, Java and Python programs took about $0.01$, $0.04$ and $0.6$ seconds. Since every entry of row $n$ is at most $2^n$, one value may need up to about $2^{n/2}/2$ passes, so for much larger $R$ the test of Section 5 would be the better choice.

The C++ program checks the value $105$ of the statement before it starts. For this article we also found that all three programs print the same number for $51$ rows, compared without displaying it, and that the C++ program with --rows= agrees for every $R\le50$ with a direct computation from Python's math.comb that tries every square $d^2\le v$, for example $175$ for $10$ rows and $15607$ for $16$. Two separately written programs, not part of the published solutions, give the same sum for $51$ rows: one decides for every place $(n,k)$ from Legendre's formula alone whether the entry is squarefree, the other tries only $4$, $9$, $25$ and $49$. The two tests agree on all $614$ values, and the exponent of every prime $p\le47$ in every entry equals the number of carries of Section 4.

Footnotes and References

The references below supply the background facts used above. The exactness of the row rule, the bound on the exponents and the reduction to the squares $4$, $9$, $25$ and $49$ are derived explicitly in this article.

Project Euler 203 — Squarefree Binomial Coefficients. The official statement defines squarefree numbers, notes that the first eight rows of Pascal's triangle contain twelve distinct numbers, of which all except 4 and 20 are squarefree and add up to 105, and asks for the sum of the distinct squarefree numbers in the first 51 rows.
Wikipedia — Pascal's triangle. The rows are numbered from n = 0, each number is the sum of the two above it, row n adds up to 2ⁿ, and a row can be computed by itself, each entry being the previous one times (n + 1 − k)/k.
Wikipedia — Binomial coefficient. The factorial formula, the symmetry C(n, k) = C(n, n − k), and the recursive form C(n, k) = C(n, k − 1) · (n − k + 1)/k of the multiplicative formula, starting from C(n, 0) = 1.
Wikipedia — Square-free integer. A square-free integer is divisible by no square other than 1. The Erdős squarefree conjecture, proved for large n by Sárközy in 1985 and for all n > 4 by Ramaré and Granville in 1996, says that C(2n, n) is never squarefree for n > 4.
Wikipedia — Legendre's formula. The exponent of a prime p in n! is the sum of ⌊n/pⁱ⌋ over i ≥ 1, and the formula can be used to prove Kummer's theorem.
Wikipedia — Kummer's theorem. Proved by Kummer in 1852: the exponent of p in C(n, m) is the number of carries when m is added to n − m in base p.
C++ — Euler203.cpp. The linked immutable C++ revision contains parse_arguments, is_squarefree, solve and run_checkpoints. It is the implementation record for this article.
cppreference — std::set: sorted unique keys, logarithmic insertion; arithmetic operators: unsigned arithmetic is performed modulo 2ⁿ for n bits; Java — TreeSet: log(n) cost for add, which ignores elements already present; Python — built-in types: integers of unlimited precision; Python — time complexity of built-in types: adding to a set costs O(1) on average.

Problem 203 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <string>

namespace {

using u64 = std::uint64_t;

struct Options {
    int rows = 51;
    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, "--rows=", options.rows)) {
            continue;
        }

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

bool is_squarefree(u64 v) {
    if (v == 0) {
        return false;
    }

    if ((v % 4ULL) == 0ULL) {
        return false;
    }
    for (u64 p = 3; p * p <= v; p += 2) {
        const u64 pp = p * p;
        if ((v % pp) == 0ULL) {
            return false;
        }
    }
    return true;
}

u64 solve(const int rows) {
    std::set<u64> values;

    for (int n = 0; n < rows; ++n) {
        u64 c = 1;
        for (int k = 0; k <= n; ++k) {
            if (k > 0) {
                c = c * static_cast<u64>(n - k + 1) / static_cast<u64>(k);
            }
            values.insert(c);
        }
    }

    u64 sum = 0;
    for (u64 v : values) {
        if (is_squarefree(v)) {
            sum += v;
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(8) != 105ULL) {
        std::cerr << "Checkpoint failed for first 8 rows" << '\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.rows) << '\n';
    return 0;
}

Python

# Problem 203: Squarefree Binomial Coefficients
# Sum of distinct squarefree values in the first 51 rows of Pascal's triangle.

def solve():
    def is_squarefree(v):
        if v == 0: return False
        if v % 4 == 0: return False
        p = 3
        while p * p <= v:
            if v % (p*p) == 0: return False
            p += 2
        return True

    rows = 51
    values = set()
    for n in range(rows):
        c = 1
        for k in range(n+1):
            values.add(c)
            c = c * (n - k) // (k + 1)

    print(sum(v for v in values if is_squarefree(v)))

solve()

Java

import java.util.TreeSet;

public class Euler203 {
    public static void main(String[] args) {
        int rows = 51;
        TreeSet<Long> values = new TreeSet<>();
        for (int n = 0; n < rows; n++) {
            long c = 1;
            for (int k = 0; k <= n; k++) {
                values.add(c);
                if (k < n)
                    c = c * (n - k) / (k + 1);
            }
        }
        long sum = 0;
        for (long v : values)
            if (isSquarefree(v))
                sum += v;
        System.out.println(sum);
    }

    static boolean isSquarefree(long v) {
        if (v == 0)
            return false;
        if (v % 4 == 0)
            return false;
        for (long p = 3; p * p <= v; p += 2)
            if (v % (p * p) == 0)
                return false;
        return true;
    }
}