Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

Given equally spaced points on a circle, we define an -star polygon as an -gon having those points as vertices. Two -star polygons differing by a rotation/reflection are considered different.

For example, there are twelve -star polygons shown below.

For an -star polygon , let be the number of its self intersection points.
Let be the sum of over all -star polygons .
For the example above because in total there are self intersection points.

Some star polygons may have intersection points made from more than two lines. These are only counted once. For example, , shown below is one of the sixty -star polygons. This one has .

You are also given that .

Find . Give your answer modulo .

Problem 842 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 842: Irregular Clocking

Mathematical Foundation

Theorem 1 (Hull—Dobell Full-Period Criterion). The LCG $x_{n+1} = (ax_n + c) \bmod m$ has full period $m$ if and only if:

1. $\gcd(c, m) = 1$,
2. $a \equiv 1 \pmod{p}$ for every prime $p \mid m$,
3. $a \equiv 1 \pmod{4}$ if $4 \mid m$.

Proof. Write $f(x) = ax + c \bmod m$. The sequence has period $m$ iff $f$ is a permutation of $\mathbb{Z}/m\mathbb{Z}$ with a single orbit.

Necessity of (1): If $d = \gcd(c,m) > 1$, then $f(x) \equiv ax \pmod{d}$ for all $x$, so the residues modulo $d$ visited by the sequence depend on $x_0 \bmod d$ and $a \bmod d$. In particular, $f$ cannot be a single-cycle permutation on all of $\mathbb{Z}/m\mathbb{Z}$.

Necessity of (2) and (3): The $n$-th iterate is $f^n(x_0) = a^n x_0 + c \frac{a^n - 1}{a - 1} \bmod m$ (when $a \ne 1$). Full period requires $f^m = \mathrm{id}$ and $f^d \ne \mathrm{id}$ for all proper divisors $d \mid m$. The condition $a^m \equiv 1 \pmod{m}$ with appropriate order constraints yields (2) and (3) via the Chinese Remainder Theorem.

Sufficiency: Under (1)—(3), one verifies by CRT that $f$ acts as a cyclic permutation on each $\mathbb{Z}/p^{e_i}\mathbb{Z}$ factor, and these cycles combine into a single cycle of length $m$. $\square$

Theorem 2 (Closed-Form Expression). For $a \ne 1$:

Proof. By induction on $n$. Base case ($n=0$): $x_0 = a^0 x_0 + c \cdot 0 = x_0$. Inductive step: assume $x_n = a^n x_0 + c \cdot \frac{a^n - 1}{a-1}$. Then

Lemma 1 (Matrix Representation). The LCG recurrence is captured by

whence $x_n$ can be computed in $O(\log n)$ arithmetic operations via binary matrix exponentiation.

Proof. Direct matrix multiplication yields $x_{n+1} = a x_n + c \cdot 1$ and $1 = 0 \cdot x_n + 1 \cdot 1$, matching the recurrence. Repeated application gives $\binom{x_n}{1} = M^n \binom{x_0}{1}$ where $M = \bigl(\begin{smallmatrix}a & c \\ 0 & 1\end{smallmatrix}\bigr)$. Computing $M^n \bmod m$ via repeated squaring uses $O(\log n)$ matrix multiplications, each costing $O(1)$ for $2 \times 2$ matrices. $\square$

Theorem 3 (Floyd’s Cycle Detection). Given any iterated function $f: S \to S$ on a finite set $S$ starting from $x_0$, Floyd’s algorithm finds the cycle length $\rho$ and tail length $\tau$ in $O(\tau + \rho)$ time and $O(1)$ space.

Proof. Maintain two pointers: $\text{slow} = f^i(x_0)$ and $\text{fast} = f^{2i}(x_0)$. They first meet at some step $\nu$ with $\nu \equiv 0 \pmod{\rho}$ and $\nu \ge \tau$. Then:

• To find $\tau$: reset slow to $x_0$, advance both at unit speed; they meet at position $\tau$.
• To find $\rho$: from any point in the cycle, advance one pointer until it returns; the number of steps is $\rho$.

Total work: $O(\nu) + O(\tau) + O(\rho) = O(\tau + \rho)$ since $\nu \le \tau + \rho$. Space is $O(1)$ (two pointers). $\square$

Editorial

LCG sequence analysis: x_{n+1} = (a*x_n + c) mod m. Cycle detection, closed-form evaluation, period finding. We matrix exponentiation approach. We then floyd’s algorithm. Finally, find tail length tau.

Pseudocode

Matrix exponentiation approach
if n is odd
Floyd's algorithm
Find tail length tau
Find period rho

Complexity Analysis

• Time (closed-form at index $n$): $O(\log n)$ via binary matrix exponentiation, with each step performing $O(1)$ modular multiplications.
• Space (closed-form): $O(1)$ (constant number of $2 \times 2$ matrices).
• Time (cycle detection): $O(\tau + \rho)$ where $\tau$ is the tail length and $\rho$ the period.
• Space (cycle detection): $O(1)$.

Answer

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

/*
 * Problem 842: Irregular Clocking
 *
 * LCG: x_{n+1} = (a*x_n + c) mod m
 * Implements Floyd and Brent cycle detection,
 * plus matrix exponentiation for x_n at large indices.
 */

typedef long long ll;
typedef vector<vector<ll>> Mat;

Mat mat_mul(const Mat& A, const Mat& B, ll mod) {
    int n = A.size();
    Mat C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) if (A[i][k])
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
    return C;
}

Mat mat_pow(Mat M, ll p, ll mod) {
    int n = M.size();
    Mat result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;
    while (p > 0) {
        if (p & 1) result = mat_mul(result, M, mod);
        M = mat_mul(M, M, mod);
        p >>= 1;
    }
    return result;
}

ll lcg_at(ll a, ll c, ll m, ll x0, ll n) {
    Mat M = {{a, c}, {0, 1}};
    Mat Mn = mat_pow(M, n, m);
    return (Mn[0][0] * x0 + Mn[0][1]) % m;
}

pair<ll, ll> brent_cycle(ll a, ll c, ll m, ll x0) {
    ll power = 1, lam = 1;
    ll tortoise = x0, hare = (a * x0 + c) % m;
    while (tortoise != hare) {
        if (power == lam) { tortoise = hare; power *= 2; lam = 0; }
        hare = (a * hare + c) % m;
        lam++;
    }
    tortoise = hare = x0;
    for (ll i = 0; i < lam; i++) hare = (a * hare + c) % m;
    ll tau = 0;
    while (tortoise != hare) {
        tortoise = (a * tortoise + c) % m;
        hare = (a * hare + c) % m;
        tau++;
    }
    return {tau, lam};
}

int main() {
    // Verify: a=2, c=0, m=7, x0=1 => period=3
    auto [t1, r1] = brent_cycle(2, 0, 7, 1);
    assert(r1 == 3);

    // Verify matrix exponentiation
    assert(lcg_at(2, 0, 7, 1, 0) == 1);
    assert(lcg_at(2, 0, 7, 1, 1) == 2);
    assert(lcg_at(2, 0, 7, 1, 3) == 1);

    // Full-period test: a=5,c=3,m=16
    auto [t2, r2] = brent_cycle(5, 3, 16, 0);
    assert(r2 == 16);

    ll ans = lcg_at(1103515245LL, 12345, 1LL << 31, 0, 1000000000000LL);
    cout << ans << endl;
    return 0;
}

"""
Problem 842: Irregular Clocking

LCG sequence analysis: x_{n+1} = (a*x_n + c) mod m.
Cycle detection, closed-form evaluation, period finding.
"""

from math import gcd

# --- Method 1: Floyd's cycle detection ---
def floyd_cycle(a, c, m, x0):
    """Return (tail_length, period) using Floyd's algorithm."""
    # Phase 1: Find meeting point
    slow = (a * x0 + c) % m
    fast = (a * slow + c) % m
    while slow != fast:
        slow = (a * slow + c) % m
        fast = (a * ((a * fast + c) % m) + c) % m

    # Phase 2: Find tail length
    tau = 0
    slow = x0
    while slow != fast:
        slow = (a * slow + c) % m
        fast = (a * fast + c) % m
        tau += 1

    # Phase 3: Find period
    rho = 1
    fast = (a * slow + c) % m
    while slow != fast:
        fast = (a * fast + c) % m
        rho += 1

    return tau, rho

# --- Method 2: Brent's cycle detection ---
def brent_cycle(a, c, m, x0):
    """Return (tail_length, period) using Brent's algorithm."""
    power = lam = 1
    tortoise = x0
    hare = (a * x0 + c) % m

    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = (a * hare + c) % m
        lam += 1

    # Find tail length
    tortoise = hare = x0
    for _ in range(lam):
        hare = (a * hare + c) % m
    tau = 0
    while tortoise != hare:
        tortoise = (a * tortoise + c) % m
        hare = (a * hare + c) % m
        tau += 1

    return tau, lam

# --- Method 3: Direct sequence enumeration ---
def find_cycle_direct(a, c, m, x0):
    """Brute force: store all visited states."""
    visited = {}
    x = x0
    for i in range(m + 1):
        if x in visited:
            tau = visited[x]
            rho = i - tau
            return tau, rho
        visited[x] = i
        x = (a * x + c) % m
    return 0, m

# --- Method 4: Closed-form x_n via matrix exponentiation ---
def lcg_value_at(a, c, m, x0, n):
    """Compute x_n using matrix exponentiation: [a c; 0 1]^n * [x0; 1]."""
    def mat_mul(A, B, mod):
        return [
            [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod,
             (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
            [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod,
             (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]
        ]

    def mat_pow(M, p, mod):
        result = [[1, 0], [0, 1]]  # identity
        while p > 0:
            if p & 1:
                result = mat_mul(result, M, mod)
            M = mat_mul(M, M, mod)
            p >>= 1
        return result

    M = [[a, c], [0, 1]]
    Mn = mat_pow(M, n, m)
    return (Mn[0][0] * x0 + Mn[0][1]) % m

# --- Verification ---
test_cases = [
    (2, 0, 7, 1),
    (5, 3, 16, 0),
    (1, 1, 10, 0),
    (3, 1, 8, 0),
    (6, 0, 10, 1),
]

for a, c, m, x0 in test_cases:
    t1, r1 = floyd_cycle(a, c, m, x0)
    t2, r2 = brent_cycle(a, c, m, x0)
    t3, r3 = find_cycle_direct(a, c, m, x0)
    assert (t1, r1) == (t2, r2) == (t3, r3), \
        f"Mismatch for ({a},{c},{m},{x0}): Floyd={t1,r1}, Brent={t2,r2}, Direct={t3,r3}"

    # Verify closed-form
    x = x0
    for i in range(20):
        assert lcg_value_at(a, c, m, x0, i) == x
        x = (a * x + c) % m

print("All verification passed!")

# Compute example
a, c, m, x0 = 1103515245, 12345, 2**31, 0
tau, rho = brent_cycle(a, c, m, x0)
x_big = lcg_value_at(a, c, m, x0, 10**12)
print(f"Period: {rho}, x(10^12) = {x_big}")
print(f"Answer: {(tau + rho) % (10**7 + 7)}")