Problem 225: Tribonacci Non-divisors

Mathematical Development

Modulo any positive integer $m$, the sequence is controlled by triples

There are only $m^3$ such triples, so some triple must repeat. The recurrence is invertible:

Therefore once a triple repeats, the whole sequence before and after that point repeats as well. In particular, the Tribonacci sequence modulo $m$ is purely periodic.

So to decide whether $m$ divides any Tribonacci number, it is enough to start from

and follow the sequence modulo $m$ until one of two things happens:

• a term becomes $0$, so $m$ is a divisor of some Tribonacci number;
• the triple returns to $(1,1,1)$, so one full period has been traversed without seeing $0$.

Because every Tribonacci number is odd, only odd candidates can possibly fail to divide the sequence.

Editorial

The key observation is that this is not a growth problem at all; it is a finite-state problem. Modulo $m$, the sequence never produces anything except triples of residues, and there are only $m^3$ of those. Once the initial triple comes back, the cycle is closed and nothing new can happen.

That means every candidate odd number can be tested independently with constant memory. The program walks the Tribonacci recurrence modulo $m$, stops immediately if it ever hits $0$, and otherwise declares success when the state returns to $(1,1,1)$. Counting such odd moduli in increasing order gives the required $124$th example.

Pseudocode

Set the target count to 124.
Initialize the current odd candidate m = 1.

Repeat forever:
    Skip m = 1 because it divides every integer.

    Start the Tribonacci state modulo m at (1, 1, 1).

    Advance the recurrence:
        next = (a + b + c) mod m
        shift (a, b, c) to (b, c, next)

        If c becomes 0:
            m divides some Tribonacci number
            stop testing this m

        If the state returns to (1, 1, 1):
            m is a Tribonacci non-divisor
            increase the running count
            if this is the 124th one, print m and stop

    Move on to the next odd number.

Complexity Analysis

• Time: For a fixed modulus $m$, at most one full period is explored. The crude bound is $O(m^3)$, though the actual periods are much shorter.
• Space: $O(1)$.

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()