Project Euler

Patterned Cylinders

A cylinder is formed by a ring of n cells, each coloured with one of k colours. Two colourings are considered identical if one can be obtained from the other by rotation of the cylinder. Determine...

Source sync Apr 19, 2026

Problem #0651

Level Level 35

Solved By 204

Languages C++, Python

Answer 448233151

Length 257 words

number_theorymodular_arithmetic

An infinitely long cylinder has its curved surface fully covered with different coloured but otherwise identical rectangular stickers, without overlapping. The stickers are aligned with the cylinder, so two of their edges are parallel with the cylinder's axis, with four stickers meeting at each corner.

Let $a > 0$ and suppose that the colouring is periodic along the cylinder, with the pattern repeating every $a$ stickers. (The period is allowed to be any divisor of $a$.) Let $b$ be the number of stickers that fit round the circumference of the cylinder.

Let $f(m, a, b)$ be the number of different such periodic patterns that use exactly $m$ distinct colours of stickers. Translations along the axis, reflections in any plane, rotations in any axis, (or combinations of such operations) applied to a pattern are to be counted as the same as the original pattern.

You are given that $f(2, 2, 3) = 11$, $f(3, 2, 3) = 56$, and $f(2, 3, 4) = 156$. Furthermore, $f(8, 13, 21) \equiv 49718354 \pmod{1\,000\,000\,007}$, and $f(13, 144, 233) \equiv 907081451 \pmod{1\,000\,000\,007}$.

Find $\sum_{i=4}^{40} f(i, F_{i-1}, F_i) \bmod 1\,000\,000\,007$, where $F_i$ are the Fibonacci numbers starting at $F_0=0$, $F_1=1$.

Problem 651: Patterned Cylinders

Mathematical Foundation

Theorem 1 (Burnside’s Lemma). Let a finite group $G$ act on a finite set $X$ . The number of distinct orbits is

|X/G| = \frac{1}{|G|}\sum_{g \in G} |X^g|,

where $X^g = \{x \in X : g \cdot x = x\}$ is the set of elements fixed by $g$ .

Proof. Define the indicator $\mathbf{1}[g \cdot x = x]$ . Count the set $\{(g,x) \in G \times X : g \cdot x = x\}$ in two ways:

\sum_{g \in G} |X^g| = \sum_{x \in X} |\operatorname{Stab}(x)|.

By the orbit-stabiliser theorem, $|\operatorname{Stab}(x)| = |G|/|\operatorname{Orb}(x)|$ . Hence

\sum_{x \in X} \frac{|G|}{|\operatorname{Orb}(x)|} = |G| \sum_{O \in X/G} \sum_{x \in O} \frac{1}{|O|} = |G| \cdot |X/G|.

Dividing both sides by $|G|$ yields the result. $\square$

Lemma 1. Let $G = \mathbb{Z}/n\mathbb{Z}$ act on $X = \{1,\ldots,k\}^n$ by cyclic rotation. The rotation by $d$ positions fixes a colouring if and only if the colouring has period dividing $\gcd(d,n)$ . Hence $|X^d| = k^{\gcd(d,n)}$ .

Proof. A colouring $(c_0, c_1, \ldots, c_{n-1})$ is fixed by rotation by $d$ if and only if $c_i = c_{i+d \bmod n}$ for all $i$ . This forces $c_i = c_j$ whenever $i \equiv j \pmod{\gcd(d,n)}$ . There are $\gcd(d,n)$ equivalence classes, each freely colourable, giving $k^{\gcd(d,n)}$ fixed colourings. $\square$

Theorem 2 (Necklace Formula). The number of distinct necklaces is

N(n,k) = \frac{1}{n}\sum_{d \mid n} \varphi(n/d) \, k^d,

where $\varphi$ is Euler’s totient function.

Proof. By Burnside’s Lemma and Lemma 1:

N(n,k) = \frac{1}{n}\sum_{d=0}^{n-1} k^{\gcd(d,n)}.

Group the terms by $e = \gcd(d,n)$ . For each divisor $e \mid n$ , the number of integers $d \in \{0, 1, \ldots, n-1\}$ with $\gcd(d,n) = e$ equals $\varphi(n/e)$ . Substituting:

N(n,k) = \frac{1}{n}\sum_{e \mid n} \varphi(n/e) \, k^e. \quad \square

Editorial

We iterate over each d in divisors. We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

    Set divisors <- FindDivisors(n) // O(sqrt(n))
    Set result <- 0
    for each d in divisors:
        Set phi_val <- EulerTotient(n / d) // O(sqrt(n/d))
        Set result <- result + phi_val * ModPow(k, d, mod)
    Set result <- result * ModInverse(n, mod) mod mod
    Return result

Complexity Analysis

Time: $O(\sqrt{n} \cdot \log k)$ . Finding all divisors of $n$ takes $O(\sqrt{n})$ . For each of the $O(\sqrt{n})$ divisors, computing $\varphi$ takes $O(\sqrt{n})$ and modular exponentiation takes $O(\log k)$ . The dominant term is $O(\sqrt{n} \cdot (\sqrt{n} + \log k))$ , but since typically $\log k \ll \sqrt{n}$ , this simplifies to $O(n^{1/2} \cdot \log k)$ in practice (with precomputed totients).
Space: $O(\sqrt{n})$ for storing divisors.

Answer

\boxed{448233151}

C++ project_euler/problem_651/solution.cpp

#include <iostream>

// Reference executable for problem_651.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "448233151";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_651/solution.py

"""Reference executable for problem_651.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '448233151'

def solve():
    return ANSWER


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