Complexity Analysis

Linear Complexity Dashboard

Explore how the linear complexity of the Gregorian leap-year count Λ(Y) = ⌊Y/4⌋ − ⌊Y/100⌋ + ⌊Y/400⌋ varies across different primes p and different calendar rules.

→ GitHub Repo

Gregorian Complexity

401

most primes p ∤ 400

Exceptional: p=3

305

p | c−1 condition

Exceptional: p=97

397

p | bc−c+1 condition

Bound

401

abc+1 for (4,25,4)

§1 Overview

Complexity Across Primes

The Gregorian leap-year count Λ(Y) has different linear complexity depending on the prime modulus p. This chart shows how L(Λ) mod p varies across the first 50 primes not dividing 400.

§2 Key Primes

Exceptions & Special Cases

Most primes p achieve the maximum complexity of 401. However, p=3 and p=97 are exceptions due to specific divisibility conditions in the formula.

Prime p	L(Λ) mod p	Condition	Notes
Most p ∤ 400	401	Generic case	p ∤ (3) and p ∤ (76)
p = 3	305	p \| c−1	Deficit: (ab−a) = 96
p = 97	397	p \| bc−c+1	Deficit: a = 4
p ∈ {2, 5}	—	p \| 400	Excluded

§3 Distribution

Histogram of Complexities

Among the first 50 primes p ∤ 400, most achieve complexity 401. The outliers p=3 and p=97 show the deficit structure predicted by Theorem C.

§4 Theory

Theoretical Foundations

The linear complexity is computed via generating functions and root-counting on rational functions.

Theorem	Formula / Result
A (Staircase)	g_n(Y) = ⌊Y/n⌋ mod p has complexity n+1
B (Upper Bound)	L(L_{a,b,c}) ≤ abc+1
C (Exact)	L(L_{a,b,c}) = abc+1 − (ab−a)·[p\|c−1] − a·[p\|bc−c+1]
D (General)	For arbitrary moduli: M+1 − Σ φ(d)·[σ_d=0] − ε