Problem 225: Tribonacci Non-divisors

Mathematical Foundation

Theorem 1 (All Tribonacci Numbers Are Odd). For all $n \geq 1$, $T_n$ is odd.

Proof. Base cases: $T_1 = T_2 = T_3 = 1$ are odd. Inductive step: assume $T_{n-3}, T_{n-2}, T_{n-1}$ are all odd. Then $T_n = T_{n-1} + T_{n-2} + T_{n-3} \equiv 1 + 1 + 1 \equiv 1 \pmod{2}$, which is odd. By strong induction, all $T_n$ are odd. $\square$

Theorem 2 (Pure Periodicity Modulo $m$). For any positive integer $m$, the Tribonacci sequence modulo $m$ is purely periodic.

Proof. Consider the sequence of triples $(T_n \bmod m, T_{n+1} \bmod m, T_{n+2} \bmod m)$. There are $m^3$ possible triples, so by the pigeonhole principle, some triple must repeat: there exist $i < j$ with

The recurrence is invertible: $T_{n-1} = T_{n+2} - T_{n+1} - T_n$. Therefore we can extend the sequence backwards uniquely. Applying the inverse recurrence $j - i$ times from the repeated triple shows that $(T_1, T_2, T_3) \equiv (T_{j-i+1}, T_{j-i+2}, T_{j-i+3}) \pmod{m}$. Hence the sequence is purely periodic with period dividing $j - i$. $\square$

Lemma 1 (Period Bound). The period of the Tribonacci sequence modulo $m$ is at most $m^3$.

Proof. There are $m^3$ possible triples of residues, so a repetition must occur within $m^3 + 1$ steps. $\square$

Theorem 3 (Divisibility Criterion). An odd number $m$ divides some Tribonacci number $T_n$ if and only if $0$ appears in one complete period of the sequence $(T_n \bmod m)$.

Proof. ($\Rightarrow$) If $m \mid T_n$, then $T_n \bmod m = 0$ appears in the sequence. ($\Leftarrow$) If $0$ appears in one period, then since the sequence is purely periodic, $T_k \equiv 0 \pmod{m}$ for some $k$. Conversely, if $0$ never appears in one full period, the pure periodicity guarantees it never appears at all. $\square$

Lemma 2 (Cycle Detection). To test whether $0$ appears in the period, compute $(T_n, T_{n+1}, T_{n+2}) \bmod m$ starting from $(1, 1, 1)$ until either $T_n \equiv 0$ (divisor found) or the triple returns to $(1, 1, 1)$ (non-divisor confirmed).

Proof. By Theorem 2, the sequence is purely periodic starting from $(1,1,1)$. If $(1,1,1)$ recurs, one full period has been traversed. If $0$ was not encountered, it never will be. $\square$

Editorial

T(1) = T(2) = T(3) = 1, T(n) = T(n-1) + T(n-2) + T(n-3). For each odd m, compute T(n) mod m. If 0 never appears in the cycle, then m is a non-divisor. We loop.

Pseudocode

while true
loop

Complexity Analysis

• Time: For each candidate $m$, the cycle detection runs for at most $m^3$ iterations, but in practice the period is much shorter (typically $O(m)$). We test odd numbers up to approximately 2009. Total work is bounded by $O\!\left(\sum_{m \text{ odd}} \pi(m)\right)$ where $\pi(m)$ is the actual period, empirically $O(m_{\max}^2)$.
• Space: $O(1)$ per candidate (only three residues stored).

Answer

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

int main(){
    // Find the 124th odd number that does not divide any Tribonacci number.
    // T(1) = T(2) = T(3) = 1, T(n) = T(n-1) + T(n-2) + T(n-3).
    // For each odd m, compute T(n) mod m until 0 is found or cycle detected.

    int target = 124;
    int count = 0;

    for(int m = 1; ; m += 2){
        // Check if m divides any Tribonacci number
        int a = 1 % m, b = 1 % m, c = 1 % m;
        bool divides = false;

        // Check if m = 1 (divides everything)
        if(m == 1){
            // T(1) = 1, and 1 divides 1. So 1 divides a tribonacci number.
            continue;
        }

        // Iterate through the cycle
        for(long long iter = 0; iter < (long long)m * m * m + 10; iter++){
            int next = (a + b + c) % m;
            a = b;
            b = c;
            c = next;
            if(c == 0){
                divides = true;
                break;
            }
            // Check if we've returned to (1, 1, 1)
            if(a == 1 % m && b == 1 % m && c == 1 % m){
                break;
            }
        }

        if(!divides){
            count++;
            if(count == target){
                cout << m << endl;
                return 0;
            }
        }
    }

    return 0;
}

"""
Problem 225: Tribonacci Non-divisors

Find the 124th odd number that does not divide any Tribonacci number.
T(1) = T(2) = T(3) = 1, T(n) = T(n-1) + T(n-2) + T(n-3).

For each odd m, compute T(n) mod m. If 0 never appears in the cycle,
then m is a non-divisor.
"""

def does_not_divide_any_tribonacci(m):
    """Return True if m does not divide any Tribonacci number."""
    if m == 1:
        return False  # 1 divides T(1) = 1

    a, b, c = 1 % m, 1 % m, 1 % m

    for _ in range(m * m * m + 10):
        nxt = (a + b + c) % m
        a, b, c = b, c, nxt
        if c == 0:
            return False  # m divides some T(n)
        if a == 1 and b == 1 and c == 1:
            return True  # cycle completed, 0 never appeared

    return True  # shouldn't reach here for reasonable m

def solve():
    target = 124
    count = 0
    m = 1

    while True:
        if does_not_divide_any_tribonacci(m):
            count += 1
            if count == target:
                print(m)
                return
        m += 2

if __name__ == "__main__":
    solve()