Problem 802: Iterated Composition

Mathematical Foundation

Theorem 1 (Conjugacy to Standard Quadratic). The map $f(x) = x^2 - x + 1$ is conjugate to $F(u) = u^2 + c$ with $c = 3/4$ via the affine substitution $u = x - 1/2$. Explicitly, if $\varphi(x) = x - 1/2$, then $F = \varphi \circ f \circ \varphi^{-1}$ where $F(u) = u^2 + 3/4$.

Proof. We have $\varphi^{-1}(u) = u + 1/2$, so

Expanding: $(u+1/2)^2 - (u+1/2) + 1 = u^2 + u + 1/4 - u - 1/2 + 1 = u^2 + 3/4$. Then $\varphi(u^2 + 3/4) = u^2 + 3/4 - 1/2 = u^2 + 1/4$.

Correction: let us recompute. $f(x) = x^2 - x + 1$. Setting $x = u + 1/2$: $f(u + 1/2) = (u+1/2)^2 - (u+1/2) + 1 = u^2 + u + 1/4 - u - 1/2 + 1 = u^2 + 3/4$. Then $\varphi(u^2 + 3/4) = u^2 + 3/4 - 1/2 = u^2 + 1/4$.

So the conjugate map is $F(u) = u^2 + 1/4$, with $c = 1/4$. $\square$

Theorem 2 (No Real Periodic Points of Period $> 1$ for $c = 1/4$). For $F(u) = u^2 + 1/4$, the unique real fixed point is $u^* = 1/2$ (a parabolic fixed point with $F'(u^*) = 1$). There are no real periodic orbits of period $d > 1$.

Proof. The fixed points of $F$ satisfy $u^2 + 1/4 = u$, i.e., $(u - 1/2)^2 = 0$, giving the unique (double) fixed point $u^* = 1/2$ with $F'(1/2) = 2 \cdot (1/2) = 1$.

For period 2: $F_2(u) = u$ factors as $(F(u) - u) \cdot Q(u) = 0$ where $Q(u) = F(u) + u - ?$. Explicitly, $F_2(u) - u = (u^2 + 1/4)^2 + 1/4 - u$. Dividing by $(u - 1/2)^2$ (the fixed-point factor), the remaining quadratic $Q(u) = u^2 + u + 3/4$ has discriminant $1 - 3 = -2 < 0$, so no real 2-periodic points exist.

By induction, for each $d > 1$, the polynomial $\Phi_d(u) = \prod_{\zeta} (u - \zeta)$ collecting exact period-$d$ points of $F$ has no real roots. This follows because the critical point $u = 0$ satisfies $F(0) = 1/4$, $F_2(0) = 5/16 < 1/2$, and the orbit of the critical point converges monotonically to $1/2$ from below. Since $c = 1/4$ is the cusp of the main cardioid of the Mandelbrot set, all periodic orbits other than the fixed point lie in $\mathbb{C} \setminus \mathbb{R}$. $\square$

Corollary. $g(n) = 1$ for all $n \ge 1$, so $\displaystyle\sum_{n=1}^{30} g(n) = 30$.

Proof. The real solutions to $f_n(x) = x$ correspond bijectively (via $\varphi$) to real solutions of $F_n(u) = u$. By Theorem 2, the only such solution is $u = 1/2$, i.e., $x = 1$, for every $n$. $\square$

Editorial

Let $f(x) = x^2 - x + 1$. Define $f_1(x)=f(x)$ and $f_{n+1}(x)=f(f_n(x))$. Let $g(n)$ be the number of real solutions to $f_n(x)=x$. Find $\sum_{n=1}^{30} g(n)$. We by Theorem 2, g(n) = 1 for all n >= 1.

Pseudocode

    By Theorem 2, g(n) = 1 for all n >= 1
    Return 30

Complexity Analysis

• Time: $O(1)$ — the result follows from the closed-form analysis.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    // f(x) = x^2 - x + 1, parameter c=3/4 > 1/4
    // Only real periodic point is the fixed point x=1
    // g(n) = 1 for all n
    long long ans = 30; // sum of g(n) for n=1..30
    cout << ans << endl;
    return 0;
}

"""
Problem 802: Iterated Composition
Let $f(x) = x^2 - x + 1$. Define $f_1(x)=f(x)$ and $f_{n+1}(x)=f(f_n(x))$. Let $g(n)$ be the number of real solutions to $f_n(x)=x$. Find $\sum_{n=1}^{30} g(n)$.
"""

def solve():
    """Count real solutions of f_n(x) = x for f(x) = x^2 - x + 1."""
    # For c = 3/4 in the Mandelbrot set, the dynamics have limited real periodic orbits
    # f(x) = x^2 - x + 1, fixed point x=1 (double)
    # f_2(x) = x has the same fixed point; check for 2-cycles
    # f(x) = y, f(y) = x => system gives no real 2-cycles when c > 1/4

    # For this quadratic map, all periodic orbits beyond period 1 are complex
    # g(n) = 1 for all n (only the fixed point x=1)
    total = sum(1 for n in range(1, 31))  # g(n) = 1 for each n
    return total

answer = solve()
print(answer)