Problem 225: Tribonacci Non-divisors

Project Euler Problem 225 Solution

EulerSolve provides an optimized solution for Project Euler Problem 225, Tribonacci Non-divisors, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The Tribonacci sequence is defined by $T_1=T_2=T_3=1$ and $$T_{k+3}=T_{k+2}+T_{k+1}+T_k.$$ For an odd integer $n$, we ask whether at least one Tribonacci term is divisible by $n$. The task is to scan the odd integers and find the 124th one for which this never happens. Trying to generate huge Tribonacci numbers directly is the wrong viewpoint. Divisibility by $n$ depends only on residues modulo $n$, so the real problem is to understand the orbit of a recurrence on residue triples. Mathematical Approach Tribonacci as a modular state machine For a fixed candidate $n$, group three consecutive terms into one state: $$S_k=(T_k,T_{k+1},T_{k+2})\bmod n.$$ The Tribonacci recurrence then becomes the deterministic transition $$F_n(a,b,c)=(b,c,(a+b+c)\bmod n),$$ so that $S_{k+1}=F_n(S_k)$ with starting state $S_1=(1,1,1)\bmod n$. This is the natural state space for the problem because the next term depends on exactly the previous three terms and on nothing else. When does $n$ divide a Tribonacci term? For every $m\ge 3$, the term $T_m$ appears as the third coordinate of a state: $$S_{m-2}=(T_{m-2},T_{m-1},T_m)\bmod n.$$ Therefore $$n\mid T_m \quad \Longleftrightarrow \quad \text{the orbit of } S_1 \text{ contains a state with third coordinate } 0.$$ This is why the implementations only inspect the newest residue in each triple....

Detailed mathematical approach

Problem Summary

The Tribonacci sequence is defined by $T_1=T_2=T_3=1$ and

$$T_{k+3}=T_{k+2}+T_{k+1}+T_k.$$

For an odd integer $n$, we ask whether at least one Tribonacci term is divisible by $n$. The task is to scan the odd integers and find the 124th one for which this never happens.

Trying to generate huge Tribonacci numbers directly is the wrong viewpoint. Divisibility by $n$ depends only on residues modulo $n$, so the real problem is to understand the orbit of a recurrence on residue triples.

Mathematical Approach

Tribonacci as a modular state machine

For a fixed candidate $n$, group three consecutive terms into one state:

$$S_k=(T_k,T_{k+1},T_{k+2})\bmod n.$$

The Tribonacci recurrence then becomes the deterministic transition

$$F_n(a,b,c)=(b,c,(a+b+c)\bmod n),$$

so that $S_{k+1}=F_n(S_k)$ with starting state $S_1=(1,1,1)\bmod n$. This is the natural state space for the problem because the next term depends on exactly the previous three terms and on nothing else.

When does $n$ divide a Tribonacci term?

For every $m\ge 3$, the term $T_m$ appears as the third coordinate of a state:

$$S_{m-2}=(T_{m-2},T_{m-1},T_m)\bmod n.$$

Therefore

$$n\mid T_m \quad \Longleftrightarrow \quad \text{the orbit of } S_1 \text{ contains a state with third coordinate } 0.$$

This is why the implementations only inspect the newest residue in each triple. A zero in the first or second coordinate would simply be a third coordinate from one or two steps earlier, and the initial state $(1,1,1)$ clearly contains no zero for the odd candidates being tested.

Why each candidate can be decided by a finite search

Modulo $n$, there are only $n^3$ possible residue triples. Since the transition $F_n$ is deterministic, once a state repeats, the entire future orbit repeats as well. That means the Tribonacci sequence modulo $n$ is periodic at the level of triples, and each odd candidate can be classified after exploring only a finite orbit.

If a zero third coordinate appears before the orbit closes, then $n$ divides some Tribonacci term. If the orbit closes first and no third coordinate was zero anywhere on that closed walk, then zero will never appear later either, so $n$ is a Tribonacci non-divisor.

Worked example: one divisor and one non-divisor

The state model makes small examples transparent. For $n=9$, the first few states are

$$ (1,1,1)\to(1,1,3)\to(1,3,5)\to(3,5,0). $$

The third coordinate becomes 0 in the state $(T_4,T_5,T_6)\bmod 9$, so $9\mid T_6$. Thus 9 is rejected immediately.

For $n=27$, the orbit begins

$$ (1,1,1)\to(1,1,3)\to(1,3,5)\to(3,5,9)\to(5,9,17)\to(9,17,4)\to\cdots $$

and the full modular orbit eventually returns to an earlier state without ever producing a third coordinate 0. So 27 is accepted. In fact, it is the first odd integer with the required non-divisibility property.

Why Floyd's cycle detection is the right tool

The orbit is generated by repeatedly applying the same transition $F_n$, so it is exactly the setting for Floyd's tortoise-hare cycle detection. One pointer advances by one state and the other by two. This finds a repeated state using constant memory instead of storing every triple encountered so far.

At the same time, the implementations watch the third coordinate of the visited states. If either pointer reaches a triple whose newest residue is 0, the candidate is immediately known to divide a Tribonacci term. If the two pointers meet first, the code has found a cycle and then checks that cycle once to confirm that no state on it has third coordinate 0.

How the Code Works

Testing one odd candidate

The C++, Python, and Java implementations all test a single odd $n$ in the same way. They represent the current residue triple $(a,b,c)$, advance it by the modular Tribonacci transition, and initialize Floyd's slow and fast pointers from the start state $(1,1,1)\bmod n$.

After initialization, the implementation loops until one of two events occurs. If the newest residue becomes 0, the candidate is classified as a divisor and the test stops immediately. Otherwise the slow and fast pointers eventually meet, which proves that the orbit has entered a cycle. The code then walks once around that cycle, checking every state's third coordinate before declaring the candidate a non-divisor.

That second pass is important. The meeting point only tells us that a cycle exists; it does not by itself guarantee that every state on the cycle has been inspected for a zero residue. The implementations therefore verify the entire loop explicitly.

Searching for the target odd non-divisor

Outside the single-candidate test, the algorithm simply scans the odd integers

$$3,5,7,9,\dots$$

because the problem asks specifically for odd $n$. Each odd number is tested independently. Whenever the Tribonacci orbit modulo that $n$ closes without hitting a third coordinate 0, the counter of successful candidates is increased by one.

The search ends as soon as the required count is reached. The three language versions differ only in syntax; they implement the same state transition, the same cycle detection, and the same outer scan over odd candidates.

Complexity Analysis

For one fixed $n$, the state space has at most $n^3$ triples. Let $p_n$ be the number of transitions examined before the orbit repeats. Then $p_n\le n^3$, and Floyd's method uses $O(p_n)$ state updates plus one additional traversal of the detected cycle. The worst-case time for one candidate is therefore $O(n^3)$.

The memory usage is $O(1)$: only a handful of residue triples and counters are stored. If $A_t$ denotes the $t$-th odd Tribonacci non-divisor, the total work of finding it is

$$ O\!\left(\sum_{\substack{3\le n\le A_t\\2\nmid n}} p_n\right), $$

with the crude upper bound $O(A_t^4)$ coming from $p_n\le n^3$. In practice the periods are much shorter than the full state-space bound, so the search is easily feasible for the required target.

Footnotes and References

Project Euler problem page: Project Euler 225
Tribonacci numbers: Wikipedia - Tribonacci number
Recurrence relations: Wikipedia - Recurrence relation
Cycle detection: Wikipedia - Cycle detection
Modular arithmetic: Wikipedia - Modular arithmetic

Problem 225 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Options {
    int target = 124;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--target=", options.target)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.target >= 1;
}

bool divides_tribonacci(const int n) {
    struct State {
        int a = 0;
        int b = 0;
        int c = 0;

        bool operator==(const State& other) const {
            return a == other.a && b == other.b && c == other.c;
        }
    };

    auto next = [&](const State& s) -> State {
        return {s.b, s.c, (s.a + s.b + s.c) % n};
    };

    const State start{1 % n, 1 % n, 1 % n};
    State tortoise = next(start);
    State hare = next(next(start));

    if (tortoise.c == 0 || hare.c == 0) {
        return true;
    }

    while (!(tortoise == hare)) {
        tortoise = next(tortoise);
        hare = next(next(hare));
        if (tortoise.c == 0 || hare.c == 0) {
            return true;
        }
    }

    State cur = tortoise;
    do {
        if (cur.c == 0) {
            return true;
        }
        cur = next(cur);
    } while (!(cur == tortoise));

    return false;
}

int solve(const int target) {
    int found = 0;
    int n = 1;

    while (found < target) {
        n += 2;
        if (!divides_tribonacci(n)) {
            ++found;
        }
    }

    return n;
}

bool run_checkpoints() {
    if (solve(1) != 27) {
        std::cerr << "Checkpoint failed for first odd non-divisor" << '\n';
        return false;
    }
    if (solve(10) != 221) {
        std::cerr << "Checkpoint failed for 10th odd non-divisor" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.target) << '\n';
    return 0;
}

Python

def divides_tribonacci(n):
    def next_state(a, b, c):
        return b, c, (a + b + c) % n

    start_a, start_b, start_c = 1 % n, 1 % n, 1 % n
    
    t_a, t_b, t_c = next_state(start_a, start_b, start_c)
    h_a, h_b, h_c = next_state(*next_state(start_a, start_b, start_c))

    if t_c == 0 or h_c == 0:
        return True

    while not (t_a == h_a and t_b == h_b and t_c == h_c):
        t_a, t_b, t_c = next_state(t_a, t_b, t_c)
        
        h_a, h_b, h_c = next_state(h_a, h_b, h_c)
        h_a, h_b, h_c = next_state(h_a, h_b, h_c)
        
        if t_c == 0 or h_c == 0:
            return True

    cur_a, cur_b, cur_c = t_a, t_b, t_c
    while True:
        if cur_c == 0:
            return True
        cur_a, cur_b, cur_c = next_state(cur_a, cur_b, cur_c)
        if cur_a == t_a and cur_b == t_b and cur_c == t_c:
            break

    return False

def solve():
    target = 124
    found = 0
    n = 1
    
    while found < target:
        n += 2
        if not divides_tribonacci(n):
            found += 1
            
    return str(n)

if __name__ == '__main__':
    print(solve())

Java

public class Euler225 {
    static class State {
        int a, b, c;

        State(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        boolean equals(State other) {
            return a == other.a && b == other.b && c == other.c;
        }
    }

    static State next(State s, int n) {
        return new State(s.b, s.c, (s.a + s.b + s.c) % n);
    }

    static boolean dividesTribonacci(int n) {
        State start = new State(1 % n, 1 % n, 1 % n);
        State tortoise = next(start, n);
        State hare = next(next(start, n), n);

        if (tortoise.c == 0 || hare.c == 0)
            return true;

        while (!tortoise.equals(hare)) {
            tortoise = next(tortoise, n);
            hare = next(next(hare, n), n);
            if (tortoise.c == 0 || hare.c == 0)
                return true;
        }

        State cur = new State(tortoise.a, tortoise.b, tortoise.c);
        do {
            if (cur.c == 0)
                return true;
            cur = next(cur, n);
        } while (!cur.equals(tortoise));

        return false;
    }

    public static String solve() {
        int target = 124;
        int found = 0;
        int n = 1;

        while (found < target) {
            n += 2;
            if (!dividesTribonacci(n)) {
                found++;
            }
        }

        return String.valueOf(n);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}