Problem 412: Gnomon Numbering

Project Euler Problem 412 Solution

EulerSolve provides an optimized solution for Project Euler Problem 412, Gnomon Numbering, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Start with an $m \times m$ square and remove an $n \times n$ square from the lower-right corner, where $0 \le n \lt m$. The remaining gnomon has $m^2-n^2$ cells. We must count the ways to place the integers $1,2,\dots,m^2-n^2$ so that every row increases from left to right and every column increases from top to bottom, then evaluate the count modulo $76543217$. Mathematical Approach Step 1: Write the Gnomon as a Partition Let $p=m-n$. As a Ferrers diagram, the gnomon is the partition $$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$ The first $p$ rows have length $m$, while the last $n$ rows have length $p$. Therefore the total number of cells is $$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$ A valid numbering of the gnomon is exactly a standard Young tableau of this shape. Step 2: Apply the Hook-Length Formula If $T(m,n)$ denotes the number of valid numberings, the Frame-Robinson-Thrall formula gives $$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$ where $h(u)$ is the hook length of cell $u$: the number of cells to its right, plus the number below it, plus the cell itself. So the problem reduces to evaluating the hook product for this particular gnomon shape....

Detailed mathematical approach

Problem Summary

Start with an $m \times m$ square and remove an $n \times n$ square from the lower-right corner, where $0 \le n \lt m$. The remaining gnomon has $m^2-n^2$ cells. We must count the ways to place the integers $1,2,\dots,m^2-n^2$ so that every row increases from left to right and every column increases from top to bottom, then evaluate the count modulo $76543217$.

Mathematical Approach

Step 1: Write the Gnomon as a Partition

Let $p=m-n$. As a Ferrers diagram, the gnomon is the partition

$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$

The first $p$ rows have length $m$, while the last $n$ rows have length $p$. Therefore the total number of cells is

$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$

A valid numbering of the gnomon is exactly a standard Young tableau of this shape.

Step 2: Apply the Hook-Length Formula

If $T(m,n)$ denotes the number of valid numberings, the Frame-Robinson-Thrall formula gives

$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$

where $h(u)$ is the hook length of cell $u$: the number of cells to its right, plus the number below it, plus the cell itself.

So the problem reduces to evaluating the hook product for this particular gnomon shape.

Step 3: Split the Shape into Three Regions

Using $1$-based coordinates $(i,j)$, the diagram naturally splits into a $p \times p$ corner square and two $p \times n$ arms.

In the top-left square, both the row length and column length are $m$. Hence

$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$

In the top-right arm, write $j=p+b$ with $1 \le b \le n$. The row still has length $m$, but the column length is only $p$, so

$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$

In the bottom-left arm, write $i=p+a$ with $1 \le a \le n$. Now the row length is $p$ and the column length is $m$, giving

$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$

The last two formulas describe the same multiset of hook lengths, so the two arms contribute identical factors.

Step 4: Convert the Hook Product into Factorial Ratios

Let $H$ be the product of all hook lengths. We write

$$H=P_A \cdot P_B^2,$$

where $P_A$ is the contribution of the $p \times p$ corner square and $P_B$ is the contribution of one arm.

For the corner square, fix a row $i$. As $j$ runs from $1$ to $p$, the hooks are consecutive integers, so

$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$

Multiplying over all $i=1,\dots,p$ gives

$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$

For one arm, fixing $i$ yields another consecutive block:

$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$

Therefore

$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$

The lower-left arm has the same hook multiset, so its contribution is another factor of $P_B$.

Step 5: Final Closed Formula

Substituting the factorization of $H$ into the hook-length formula yields

$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$

Here $p=m-n$. This is exactly the product decomposition used by the C++, Python, and Java implementations.

Worked Example: $(m,n)=(5,3)$

For $m=5$ and $n=3$, we have $p=2$ and $m^2-n^2=16$. The formulas above give

$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$

$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$

Hence

$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$

and therefore

$$T(5,3)=\frac{16!}{83607552}=250250.$$

This matches the exact checkpoint used by the implementation. A second consistency check is

$$T(10,5)\equiv 61251715 \pmod{76543217}.$$

How the Code Works

The implementation follows the formula directly. It computes $(m^2-n^2)!\bmod M$, precomputes factorials up to $2m-1$, evaluates the two short ratio blocks $P_A$ and $P_B$, multiplies them into the full hook product $H$, and then replaces division by a modular inverse.

Since $M=76543217$ is prime, Fermat's little theorem gives

$$x^{-1}\equiv x^{M-2}\pmod{M}.$$

So the final modular computation is

$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$

Complexity Analysis

The dominant cost is computing $(m^2-n^2)!\bmod M$, which takes $O(m^2-n^2)$ modular multiplications. Building the factorial table up to $2m-1$ and evaluating the two ratio blocks costs only $O(m)$ time. The memory usage is $O(m)$ because the implementation stores only the short factorial table.

References

Problem page: https://projecteuler.net/problem=412
Hook-length formula: Wikipedia — Hook-length formula
Standard Young tableaux: Wikipedia — Young tableau
Ferrers diagram: Wikipedia — Ferrers diagram
Frame, Robinson, Thrall (1954). The hook graphs of the symmetric group, Canadian Journal of Mathematics 6, 316-324.
Fermat's little theorem: Wikipedia — Fermat's little theorem

Problem 412 source code

C++

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

#include <boost/multiprecision/cpp_int.hpp>

namespace {

using i64 = long long;
using u64 = std::uint64_t;
using boost::multiprecision::cpp_int;

constexpr int MOD = 76543217;

struct Options {
    int m = 10000;
    int n = 5000;
    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;
    }
    try {
        value = std::stoi(tail);
    } catch (...) {
        return false;
    }
    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, "--m=", options.m) ||
            parse_int_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.m >= 1 && options.n >= 0 && options.n < options.m;
}

int mod_pow(i64 base, i64 exp) {
    i64 result = 1;
    i64 cur = base % MOD;
    i64 e = exp;
    while (e > 0) {
        if (e & 1LL) {
            result = result * cur % MOD;
        }
        cur = cur * cur % MOD;
        e >>= 1LL;
    }
    return static_cast<int>(result);
}

int LC_mod(const int m, const int n) {
    const int p = m - n;
    const i64 cells = 1LL * m * m - 1LL * n * n;

    const int max_small = 2 * m - 1;
    std::vector<int> fact_small(static_cast<std::size_t>(max_small + 1), 1);
    for (int i = 1; i <= max_small; ++i) {
        fact_small[static_cast<std::size_t>(i)] =
            static_cast<int>(1LL * fact_small[static_cast<std::size_t>(i - 1)] * i % MOD);
    }

    int fact_cells = 1;
    for (i64 i = 1; i <= cells; ++i) {
        fact_cells = static_cast<int>(1LL * fact_cells * (i % MOD) % MOD);
    }

    // Hook-product decomposition for shape λ = (m repeated p times, p repeated n times):
    // P = P_A * P_B^2, where
    // P_A = prod_{t=m+n}^{2m-1} t! / prod_{s=2n}^{m+n-1} s!
    // P_B = prod_{t=n}^{m-1} t! / prod_{u=0}^{p-1} u!
    int pa_num = 1;
    for (int t = m + n; t <= 2 * m - 1; ++t) {
        pa_num = static_cast<int>(1LL * pa_num * fact_small[static_cast<std::size_t>(t)] % MOD);
    }
    int pa_den = 1;
    for (int s = 2 * n; s <= m + n - 1; ++s) {
        pa_den = static_cast<int>(1LL * pa_den * fact_small[static_cast<std::size_t>(s)] % MOD);
    }
    const int pa = static_cast<int>(1LL * pa_num * mod_pow(pa_den, MOD - 2) % MOD);

    int pb_num = 1;
    for (int t = n; t <= m - 1; ++t) {
        pb_num = static_cast<int>(1LL * pb_num * fact_small[static_cast<std::size_t>(t)] % MOD);
    }
    int pb_den = 1;
    for (int u = 0; u <= p - 1; ++u) {
        pb_den = static_cast<int>(1LL * pb_den * fact_small[static_cast<std::size_t>(u)] % MOD);
    }
    const int pb = static_cast<int>(1LL * pb_num * mod_pow(pb_den, MOD - 2) % MOD);

    int hooks = pa;
    hooks = static_cast<int>(1LL * hooks * pb % MOD);
    hooks = static_cast<int>(1LL * hooks * pb % MOD);

    return static_cast<int>(1LL * fact_cells * mod_pow(hooks, MOD - 2) % MOD);
}

cpp_int LC_exact_small(const int m, const int n) {
    const int p = m - n;
    const int rows = m;
    std::vector<int> row_len(static_cast<std::size_t>(rows), p);
    for (int i = 0; i < p; ++i) {
        row_len[static_cast<std::size_t>(i)] = m;
    }

    std::vector<int> col_len(static_cast<std::size_t>(m), p);
    for (int j = 0; j < p; ++j) {
        col_len[static_cast<std::size_t>(j)] = m;
    }

    int cells = 0;
    for (int i = 0; i < rows; ++i) {
        cells += row_len[static_cast<std::size_t>(i)];
    }

    cpp_int numer = 1;
    for (int i = 1; i <= cells; ++i) {
        numer *= i;
    }

    cpp_int denom = 1;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < row_len[static_cast<std::size_t>(i)]; ++j) {
            const int hook =
                (row_len[static_cast<std::size_t>(i)] - j) + (col_len[static_cast<std::size_t>(j)] - i) - 1;
            denom *= hook;
        }
    }

    return numer / denom;
}

bool run_checkpoints() {
    if (LC_exact_small(3, 0) != 42) {
        std::cerr << "Checkpoint failed: LC(3,0)\n";
        return false;
    }
    if (LC_exact_small(5, 3) != cpp_int("250250")) {
        std::cerr << "Checkpoint failed: LC(5,3)\n";
        return false;
    }
    if (LC_exact_small(6, 3) != cpp_int("406029023400")) {
        std::cerr << "Checkpoint failed: LC(6,3)\n";
        return false;
    }
    if (LC_mod(10, 5) != 61251715) {
        std::cerr << "Checkpoint failed: LC(10,5) mod 76543217\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 << LC_mod(options.m, options.n) << '\n';
    return 0;
}

Python

def solve():
    MOD = 76543217
    m, n = 10000, 5000
    p = m - n
    cells = m * m - n * n

    def mod_pow(base, exp, mod=MOD):
        r = 1; base %= mod
        while exp > 0:
            if exp & 1: r = r * base % mod
            base = base * base % mod
            exp >>= 1
        return r

    max_small = 2 * m - 1
    fact_small = [1] * (max_small + 1)
    for i in range(1, max_small + 1):
        fact_small[i] = fact_small[i-1] * i % MOD

    fact_cells = 1
    for i in range(1, cells + 1):
        fact_cells = fact_cells * (i % MOD) % MOD

    pa_num = 1
    for t in range(m + n, 2 * m):
        pa_num = pa_num * fact_small[t] % MOD
    pa_den = 1
    for s in range(2 * n, m + n):
        pa_den = pa_den * fact_small[s] % MOD
    pa = pa_num * mod_pow(pa_den, MOD - 2) % MOD

    pb_num = 1
    for t in range(n, m):
        pb_num = pb_num * fact_small[t] % MOD
    pb_den = 1
    for u in range(p):
        pb_den = pb_den * fact_small[u] % MOD
    pb = pb_num * mod_pow(pb_den, MOD - 2) % MOD

    hooks = pa * pb % MOD * pb % MOD
    return str(fact_cells * mod_pow(hooks, MOD - 2) % MOD)

if __name__ == '__main__':
    print(solve())

Java

public class Euler412 {
    private static final int MOD = 76543217;

    private static int modPow(long base, long exp) {
        long result = 1;
        long cur = base % MOD;
        long e = exp;
        while (e > 0) {
            if ((e & 1L) != 0) {
                result = (result * cur) % MOD;
            }
            cur = (cur * cur) % MOD;
            e >>= 1L;
        }
        return (int) result;
    }

    public static String solve() {
        int m = 10000;
        int n = 5000;
        int p = m - n;
        long cells = 1L * m * m - 1L * n * n;

        int maxSmall = 2 * m - 1;
        int[] factSmall = new int[maxSmall + 1];
        factSmall[0] = 1;
        for (int i = 1; i <= maxSmall; ++i) {
            factSmall[i] = (int) (1L * factSmall[i - 1] * i % MOD);
        }

        int factCells = 1;
        for (long i = 1; i <= cells; ++i) {
            factCells = (int) (1L * factCells * (i % MOD) % MOD);
        }

        int paNum = 1;
        for (int t = m + n; t <= 2 * m - 1; ++t) {
            paNum = (int) (1L * paNum * factSmall[t] % MOD);
        }
        int paDen = 1;
        for (int s = 2 * n; s <= m + n - 1; ++s) {
            paDen = (int) (1L * paDen * factSmall[s] % MOD);
        }
        int pa = (int) (1L * paNum * modPow(paDen, MOD - 2) % MOD);

        int pbNum = 1;
        for (int t = n; t <= m - 1; ++t) {
            pbNum = (int) (1L * pbNum * factSmall[t] % MOD);
        }
        int pbDen = 1;
        for (int u = 0; u <= p - 1; ++u) {
            pbDen = (int) (1L * pbDen * factSmall[u] % MOD);
        }
        int pb = (int) (1L * pbNum * modPow(pbDen, MOD - 2) % MOD);

        int hooks = pa;
        hooks = (int) (1L * hooks * pb % MOD);
        hooks = (int) (1L * hooks * pb % MOD);

        long ans = 1L * factCells * modPow(hooks, MOD - 2) % MOD;
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}