Problem 908: Coprime Chains

Mathematical Analysis

Consecutive Integer Coprimality

Theorem. For any integer $n \ge 1$, $\gcd(n, n+1) = 1$.

Proof. Let $d = \gcd(n, n+1)$. Then $d \mid n$ and $d \mid (n+1)$, so $d \mid (n+1) - n = 1$. Hence $d = 1$. $\square$

Maximum Chain Length

Corollary. The sequence $2, 3, 4, \ldots, 100$ is a coprime chain of length 99, and this is optimal.

Proof. By the theorem, $\gcd(k, k+1) = 1$ for each consecutive pair, so the full sequence is a valid coprime chain. It has length 99 (= $|{2, 3, \ldots, 100}|$). Since the chain uses all available elements, no longer chain exists. $\square$

Graph-Theoretic Perspective

Define the coprime graph $G = (V, E)$ where $V = \{2, 3, \ldots, N\}$ and $(a,b) \in E$ iff $\gcd(a,b) = 1$ and $a < b$. The longest coprime chain is the longest path in this DAG.

Proposition. The coprime graph on $\{2, \ldots, N\}$ is dense: it has $\Theta(N^2)$ edges. The edge density approaches $6/\pi^2 \approx 0.608$.

Proof. The number of coprime pairs among $\{1, \ldots, N\}$ is $\sum_{d=1}^{N} \mu(d) \lfloor N/d \rfloor^2 \sim 6N^2/\pi^2$. Restricting to $\{2, \ldots, N\}$ gives essentially the same asymptotic. $\square$

The Non-Trivial Variant: Non-Consecutive Coprime Chains

A more challenging variant restricts to subsequences that skip elements. For example, find the longest coprime chain in $\{2, \ldots, N\}$ where consecutive elements differ by at least 2. In this case, DP is needed:

Coprime Chain DP Verification

For unrestricted chains (the original problem), the DP confirms:

Every DP solution equals $N - 1$, confirming that the consecutive-integer chain is always optimal.

Density of Coprime Pairs

The coprime graph has a rich structure related to the Mobius function. The number of edges involving vertex $n$ is:

where $\varphi$ is Euler’s totient. Highly composite numbers have lower relative degree $\varphi(n)/n$.

Extension: Coprime Chains Avoiding Consecutive Integers

A natural harder variant: find the longest coprime chain where $a_{i+1} - a_i \ge 2$ (no consecutive integers allowed). In this case, the chain must “jump” and the DP becomes non-trivial.

Example for $N = 20$: A valid non-consecutive coprime chain might be $\{2, 5, 7, 11, 13, 17, 19\}$ (all primes), length 7. But $\{2, 5, 9, 11, 16, 17\}$ fails since 16 and 17 are consecutive.

For prime-only chains, every pair of distinct odd primes $\ge 3$ is coprime (they share no factor). So the chain of all primes in $\{2, \ldots, N\}$ is always valid with the gap condition automatically satisfied when skipping composites. The length is $\pi(N)$. For $N = 100$: $\pi(100) = 25$.

Erdos-Straus Conjecture Connection

Coprime chains relate to the Erdos-Straus problem on unit fraction decompositions and to the theory of coprime graph Hamiltonicity. The coprime graph $G_N$ on $\{1, \ldots, N\}$ is known to be Hamiltonian for all $N \ge 2$ (Pomerance, 1983), which generalizes our result.

Complexity Analysis

• Observation: $O(1)$ once the consecutive coprimality theorem is established.
• DP verification: $O(N^2 \log N)$ using gcd per pair, or $O(N^2)$ with precomputed coprimality.
• Space: $O(N)$.

Answer

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

/*
 * Problem 908: Coprime Chains
 *
 * Find the longest coprime chain in {2, 3, ..., 100}.
 * A coprime chain has gcd(a_i, a_{i+1}) = 1 for consecutive elements.
 *
 * Key theorem: gcd(n, n+1) = 1 for all n, so the entire sequence
 * 2, 3, ..., 100 forms a valid chain of length 99.
 *
 * Two methods:
 *   1. Direct observation: answer = N - 1
 *   2. DP verification: dp[i] = max chain ending at i
 */

int main() {
    int N = 100;

    // Method 1: Direct
    int ans_direct = N - 1;

    // Method 2: DP verification
    vector<int> dp(N + 1, 0);
    for (int i = 2; i <= N; i++) {
        dp[i] = 1;
        for (int j = 2; j < i; j++) {
            if (__gcd(j, i) == 1) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int ans_dp = *max_element(dp.begin() + 2, dp.end());

    assert(ans_direct == ans_dp);

    // Verify consecutive coprimality
    for (int k = 2; k < N; k++) {
        assert(__gcd(k, k + 1) == 1);
    }

    cout << ans_direct << endl;
    return 0;
}

"""
Problem 908: Coprime Chains

Find the longest coprime chain in {2, 3, ..., 100}, where consecutive
elements must be coprime.

Key insight: gcd(n, n+1) = 1, so the full sequence 2,3,...,100 is valid.

Methods:
    1. Direct observation (consecutive integers are coprime)
    2. DP on the coprime graph (verification)
    3. Brute-force longest path (small N)
"""

from math import gcd

def solve_direct(N: int):
    """Consecutive integers are coprime, so max chain = N - 1."""
    return N - 1

def solve_dp(N: int):
    """Longest increasing coprime chain via DP.

    dp[i] = length of longest coprime chain ending at i.
    dp[i] = 1 + max{dp[j] : j < i, gcd(j, i) = 1}
    """
    dp = [0] * (N + 1)
    for i in range(2, N + 1):
        dp[i] = 1
        for j in range(2, i):
            if gcd(j, i) == 1:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp[2:])

def verify_consecutive(N: int) -> bool:
    """Check that gcd(k, k+1) = 1 for all k in [2, N-1]."""
    return all(gcd(k, k + 1) == 1 for k in range(2, N))

# Solve
N = 100
ans = solve_direct(N)

# Verify with DP for smaller N
for test_n in [5, 10, 20, 50]:
    dp_ans = solve_dp(test_n)
    direct_ans = solve_direct(test_n)
    assert dp_ans == direct_ans, f"N={test_n}: DP={dp_ans}, direct={direct_ans}"

# Verify consecutive coprimality
assert verify_consecutive(N)

print(ans)