Problem 281: Pizza Toppings

Mathematical Development

Reformulation as a Necklace Counting Problem

The problem is equivalent to counting necklaces of $N = mn$ beads with $m$ distinct colors, each color appearing exactly $n$ times, under the cyclic group $C_N$ (rotations only).

Theorem 1 (Burnside Counting Formula)

Theorem. Let $N = mn$. Then

Proof. By Burnside’s lemma, the number of orbits of the cyclic group $C_N$ acting on the set of valid colorings is

where $r^k$ denotes the rotation by $k$ positions and $\operatorname{Fix}(r^k)$ is the set of colorings invariant under $r^k$.

Step 1 (Characterizing fixed points). A coloring is fixed by $r^k$ if and only if it is periodic with period dividing $g = \gcd(k, N)$. Such a coloring consists of $N/g$ identical copies of a block of length $g$. Each block must contain exactly $g/m$ copies of each of the $m$ colors. This requires $m \mid g$; when $m \nmid g$, the count $|\operatorname{Fix}(r^k)| = 0$.

Step 2 (Counting valid blocks). When $m \mid g$, the block of length $g$ contains $g/m$ copies of each of $m$ colors. The number of such arrangements is the multinomial coefficient

Step 3 (Grouping by gcd). For each divisor $g$ of $N$, the number of integers $k \in \{0, 1, \ldots, N-1\}$ satisfying $\gcd(k,N) = g$ is exactly $\phi(N/g)$, where $\phi$ is Euler’s totient function. Therefore

Step 4 (Substitution). Set $g = mt$ where $t$ is a positive integer. The condition $g \mid N = mn$ with $m \mid g$ is equivalent to $mt \mid mn$, i.e., $t \mid n$. Furthermore, $N/g = mn/(mt) = n/t$ and $(g/m)! = t!$. Thus

Lemma 1 (Verification of Given Values)

Lemma. The formula reproduces all four given values.

Proof. Direct computation:

• $f(2,1) = \frac{1}{2}\,\phi(1)\,\frac{2!}{(1!)^2} = \frac{1}{2}\cdot 1 \cdot 2 = 1$.
• $f(2,2) = \frac{1}{4}\bigl[\phi(2)\,\frac{2!}{(1!)^2} + \phi(1)\,\frac{4!}{(2!)^2}\bigr] = \frac{1}{4}[1 \cdot 2 + 1 \cdot 6] = 2$.
• $f(3,1) = \frac{1}{3}\,\phi(1)\,\frac{3!}{(1!)^3} = \frac{6}{3} = 2$.
• $f(3,2) = \frac{1}{6}\bigl[\phi(2)\,\frac{3!}{(1!)^3} + \phi(1)\,\frac{6!}{(2!)^3}\bigr] = \frac{1}{6}[6 + 90] = 16$. $\qquad \blacksquare$

Lemma 2 (Search Bounds)

Lemma. For $m \ge 19$ and $n \ge 1$, we have $f(m,1) = (m-1)! > 10^{15}$. For $m = 2$ and $n \ge 30$, we have $f(2,n) > 10^{15}$. Hence it suffices to search $2 \le m \le 18$ and $1 \le n \le 29$.

Proof. We have $f(m,1) = \frac{1}{m}\phi(1)\frac{m!}{(1!)^m} = (m-1)!$. Since $18! = 6402373705728000 > 10^{15}$, we need $m \le 18$. For fixed $m$, $f(m,n)$ is increasing in $n$ (the dominant term $(mn)!/(n!)^m$ grows super-exponentially), so once $f(m,n) > 10^{15}$ for some $n$, all larger $n$ also exceed the bound. Numerical evaluation confirms $n \le 29$ suffices. $\qquad \blacksquare$

Editorial

Burnside’s lemma applied to necklaces of mn beads with m colors, each appearing n times, under the cyclic group C_{mn}: f(m,n) = (1/(mn)) * sum_{t | n} phi(n/t) * (mt)! / (t!)^m Sum all f(m,n) <= 10^15 for m >= 2, n >= 1. We iterate over each divisor t of n.

Pseudocode

    total = 0
    for m = 2, 3, ..., 18:
        for n = 1, 2, ..., 29:
            val = f(m, n)
            If val <= 10^15 then
                total += val
    Return total

    result = 0
    for each divisor t of n:
        result += euler_phi(n / t) * (m*t)! / (t!)^m
    Return result / (m * n)

Complexity Analysis

• Time: The outer loops iterate over at most $17 \times 29 = 493$ pairs $(m,n)$. For each pair, the inner loop iterates over at most $d(n) \le d(29) = 2$ divisors of $n$ (in general, $d(n) \le 6$ for $n \le 29$). Each iteration performs $O(mn)$ arithmetic operations for the factorial computation. Since all parameters are bounded by small constants, the total running time is $O(1)$.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 lll;

ll phi(ll n) {
    ll result = n;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

double log_multinomial(int m, int t) {
    double result = 0;
    for (int i = 1; i <= m * t; i++) result += log((double)i);
    for (int i = 1; i <= t; i++) result -= m * log((double)i);
    return result;
}

// Compute (m*t)! / (t!)^m via iterated binomial coefficients
lll exact_multinomial(int m, int t) {
    lll result = 1;
    int total = m * t;
    for (int k = 0; k < m; k++) {
        int remaining = total - k * t;
        for (int i = 0; i < t; i++) {
            result *= (remaining - i);
            result /= (i + 1);
        }
    }
    return result;
}

ll f(int m, int n) {
    ll total_beads = (ll)m * n;
    lll result = 0;
    for (int t = 1; t <= n; t++) {
        if (n % t != 0) continue;
        double log_val = log_multinomial(m, t);
        if (log_val > 45) return -1;
        lll multi = exact_multinomial(m, t);
        result += (lll)phi(n / t) * multi;
    }
    result /= total_beads;
    if (result > (lll)1000000000000000LL) return -1;
    return (ll)result;
}

int main() {
    ll LIMIT = 1000000000000000LL;
    ll total = 0;
    for (int m = 2; m <= 18; m++) {
        for (int n = 1; n <= 29; n++) {
            ll val = f(m, n);
            if (val >= 0 && val <= LIMIT)
                total += val;
        }
    }
    cout << total << endl;
    return 0;
}

"""
Project Euler Problem 281: Pizza Toppings

Burnside's lemma applied to necklaces of m*n beads with m colors, each
appearing n times, under the cyclic group C_{m*n}:

    f(m,n) = (1/(m*n)) * sum_{t | n} phi(n/t) * (m*t)! / (t!)^m

Sum all f(m,n) <= 10^15 for m >= 2, n >= 1.
"""

from math import factorial
from sympy import totient

def f(m, n):
    N = m * n
    result = 0
    for t in range(1, n + 1):
        if n % t == 0:
            result += int(totient(n // t)) * factorial(m * t) // factorial(t) ** m
    return result // N

LIMIT = 10**15
total = 0
for m in range(2, 19):
    for n in range(1, 30):
        val = f(m, n)
        if val <= LIMIT:
            total += val

print(total)