Project Euler

Frieze Patterns

A Conway-Coxeter frieze pattern of order n is an array of positive integers arranged in rows, where the top and bottom rows are all 1s, and every adjacent 2 x 2 submatrix a&b c&d satisfies the unim...

Source sync Apr 19, 2026

Problem #0850

Level Level 37

Solved By 160

Languages C++, Python

Answer 878255725

Length 327 words

modular_arithmeticgeometrysequence

Any positive real number $x$ can be decomposed into integer and fractional parts $\lfloor x \rfloor + \{x\}$, where $\lfloor x \rfloor$ (the floor function) is an integer, and $0\le \{x\} < 1$.

For positive integers $k$ and $n$, define the function \begin{align*} f_k(n) = \sum_{i=1}^{n}\left\{ \frac{i^k}{n} \right\} \end{align*} For example, $f_5(10)=4.5$ and $f_7(1234)=616.5$.

Let \begin{align*} S(N) = \sum_{\substack{k=1 \\ k\text{ odd}}}^{N} \sum_{n=1}^{N} f_k(n) \end{align*} You are given that $S(10)=100.5$ and $S(10^3)=123687804$.

Find $\lfloor S(33557799775533) \rfloor$. Give your answer modulo $977676779$.

Problem 850: Frieze Patterns

Mathematical Analysis

Frieze-Triangulation Correspondence

Theorem (Conway-Coxeter, 1973). There is a bijection between frieze patterns of order $n$ and triangulations of a convex $(n+1)$ -gon. Consequently:

F(n) = C_{n-1} = \frac{1}{n}\binom{2(n-1)}{n-1} \tag{1}

where $C_k = \frac{1}{k+1}\binom{2k}{k}$ is the $k$ -th Catalan number.

Proof sketch. Given a triangulation of an $(n+1)$ -gon, label edges with positive integers determined by the triangulation structure. The unimodular rule $ad - bc = 1$ corresponds to the adjacency condition in the triangulation. The bijection sends each triangle to a row of the frieze. $\square$

The Unimodular Rule

Lemma. The condition $ad - bc = 1$ for every $2 \times 2$ diamond is equivalent to saying the entries in row $r$ determine all subsequent rows via:

e = \frac{bd + 1}{a}

where $a, b, d$ are known neighbors and $e$ is the new entry. The integrality of $e$ is guaranteed by the unimodular condition.

Catalan Number Properties

Theorem. The Catalan numbers satisfy:

Recurrence: $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ , with $C_0 = 1$ .
Generating function: $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ .
Asymptotics: $C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$ .

Concrete Examples

$n$	Triangulations of $(n+1)$ -gon	$F(n) = C_{n-1}$
2	1 (triangle)	1
3	2 (square: 2 diagonals)	2
4	5 (pentagon)	5
5	14 (hexagon)	14
6	42	42
10	4862	4862

Verification for $n=3$ (square): The two triangulations of a square give frieze rows: $(1,1,1)$ and $(1,2,1)$ in the interior. Both satisfy $ad - bc = 1$ .

Quiddity Sequences

Definition. The quiddity sequence of a frieze pattern is the first non-trivial row $(q_1, q_2, \ldots, q_n)$ . A sequence is a valid quiddity sequence iff all entries generated by the unimodular rule are positive integers.

Theorem. Valid quiddity sequences of length $n$ with entries $\ge 1$ correspond bijectively to triangulations of the $(n+1)$ -gon, where $q_i$ equals the number of triangles incident to vertex $i$ .

Complexity Analysis

Direct Catalan computation: $O(n)$ using the formula $C_n = \binom{2n}{n}/(n+1)$ .
Catalan mod prime $p$ : $O(n)$ with factorial precomputation.
Enumerating frieze patterns: $O(C_n)$ via recursive triangulation generation.

Answer

\boxed{878255725}

C++ project_euler/problem_850/solution.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

ll power(ll b, ll e, ll m) { ll r=1; b%=m; while(e>0){if(e&1)r=r*b%m; b=b*b%m; e>>=1;} return r; }

ll catalan_mod(int n, ll mod) {
    ll num = 1, den = 1;
    for (int i = 2*n; i > n; i--) num = num * i % mod;
    for (int i = 1; i <= n; i++) den = den * i % mod;
    return num % mod * power(den, mod-2, mod) % mod * power(n+1, mod-2, mod) % mod;
}

int main() {
    // F(n) = C_{n-1}
    assert(catalan_mod(0, MOD) == 1);
    assert(catalan_mod(1, MOD) == 1);
    assert(catalan_mod(2, MOD) == 2);
    assert(catalan_mod(3, MOD) == 5);
    assert(catalan_mod(4, MOD) == 14);

    cout << catalan_mod(999, MOD) << endl;
    return 0;
}

Python project_euler/problem_850/solution.py

"""
Problem 850: Frieze Patterns

Count Conway-Coxeter frieze patterns of order n.
F(n) = C_{n-1} = Catalan number.
"""
from math import comb

MOD = 10**9 + 7

def catalan(n):
    """Compute n-th Catalan number."""
    return comb(2*n, n) // (n + 1)

def catalan_mod(n, mod):
    """Compute C_n mod p."""
    num = 1
    for i in range(2*n, n, -1):
        num = num * i % mod
    den = 1
    for i in range(1, n+1):
        den = den * i % mod
    return num * pow(den, mod-2, mod) % mod * pow(n+1, mod-2, mod) % mod

def frieze_count(n):
    return catalan(n - 1)

# Verify
assert catalan(0) == 1
assert catalan(1) == 1
assert catalan(2) == 2
assert catalan(3) == 5
assert catalan(4) == 14
for n in range(2, 12):
    assert frieze_count(n) == catalan(n-1)

# Enumerate triangulations of polygon (for verification)
def count_triangulations(n_vertices):
    """Count triangulations of convex n-gon via Catalan recurrence."""
    if n_vertices < 3: return 1 if n_vertices <= 2 else 0
    return catalan(n_vertices - 2)

for nv in range(3, 10):
    assert count_triangulations(nv) == catalan(nv - 2)

print("Verification passed!")
answer = catalan_mod(999, MOD)
print(f"Answer: {answer}")