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

1. Project Euler problem page: Project Euler 225
2. Tribonacci numbers: Wikipedia - Tribonacci number
3. Recurrence relations: Wikipedia - Recurrence relation
4. Cycle detection: Wikipedia - Cycle detection
5. Modular arithmetic: Wikipedia - Modular arithmetic