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 sequence of the problem starts with $T_1=T_2=T_3=1$, and every later term is the sum of the three terms before it, $T_k=T_{k-1}+T_{k-2}+T_{k-3}$ for $k\ge4$; this gives the terms $1,1,1,3,5,9,17,31,57,105,193$ and so on. We call a number $n$ a divisor if it divides at least one term $T_k$, and a non-divisor if it divides none. The statement tells us that $27$ is a non-divisor and that it is the smallest odd one, and it asks for the $124$th odd non-divisor. ^[1]

The whole solution in one sentence: whether $n$ divides a term depends only on the remainders of the terms after division by $n$, and these remainders, taken three at a time, run around a closed loop, so for each odd $n=3,5,7,\dots$ the program walks around this loop, looks for a remainder $0$, and counts the odd numbers whose loop has none until it reaches the $124$th.

Mathematical Approach

We replace the terms by their remainders, prove that these remainders repeat in a closed loop from the first term on, and decide every candidate with one walk around its loop.

1. Small cases

For the odd numbers from $3$ to $25$, the first term that each of them divides is:

$n=3$: $T_4=3$; $n=5$: $T_5=5$; $n=9$: $T_6=9$; $n=17$: $T_7=17$;
$n=19$: $T_9=57=3\cdot19$; $n=7$, $15$ and $21$: $T_{10}=105=3\cdot5\cdot7$;
$n=11$ and $25$: $T_{21}=85525=5^2\cdot11\cdot311$;
$n=13$: $T_{35}=433695873=13\cdot33361221$;
$n=23$: $T_{76}$, a number with $20$ digits.

The number $1$ divides every term, so every odd number below $27$ is a divisor, as the statement says. The ratio of consecutive terms tends to the tribonacci constant $1.839286755\ldots$, the real root of $x^3=x^2+x+1$, ^[2] so the terms soon become huge, and no search through them, however long, could show that $27$ divides none of them.

2. Why the problem asks for odd numbers

Every term is odd: $T_1$, $T_2$ and $T_3$ are odd, and the sum of three odd numbers is odd, so by induction every $T_k$ is odd. Hence $2$ divides no term, and neither does any even number. This is why the problem counts only odd numbers.

Likewise, if $m$ is a non-divisor, so is every multiple $qm$, because $qm\mid T_k$ would give $m\mid T_k$. From $27$ we therefore get the non-divisors $81$, $135$, $189$, $243$ and all further odd multiples of $27$. The first $124$ of them end at $27\cdot247=6669$, so the $124$th odd non-divisor is at most $6669$, and the search of Section 9 is sure to stop.

3. Remainders instead of terms

Fix a candidate $n\ge2$ and let $r_k=T_k\bmod n$ be the remainder of $T_k$ after division by $n$, a number from $0$ to $n-1$. Congruences can be added: numbers that leave the same remainders have sums that leave the same remainder. ^[3] We may therefore add the previous three remainders and keep the remainder of their sum after division by $n$:

$$r_k=(r_{k-1}+r_{k-2}+r_{k-3})\bmod n,\qquad r_1=r_2=r_3=1.$$

The number $n$ divides $T_k$ exactly when $r_k=0$. For $n=9$ the remainders begin $1,1,1,3,5,0$, so $9$ divides $T_6=9$.

4. States and the step map

The next remainder depends on the last three, so we collect three consecutive remainders into a state $S_k=(r_k,r_{k+1},r_{k+2})$. One step of the sequence is the map

$$F(a,b,c)=\bigl(b,\;c,\;(a+b+c)\bmod n\bigr),$$

with $S_{k+1}=F(S_k)$ and $S_1=(1,1,1)$. For $n=9$ the states begin $S_1=(1,1,1)$, $S_2=(1,1,3)$, $S_3=(1,3,5)$ and $S_4=(3,5,0)$. The third entry of $S_k$ is $r_{k+2}$, so the third entries of $S_1,S_2,S_3,\dots$ are the remainders from $r_3$ on, and $r_1=r_2=1$ are not zero. Hence $n$ divides a term exactly when some state has third entry $0$. There are only $n^3$ possible states, so by the pigeonhole principle two of the $n^3+1$ states $S_1,\dots,S_{n^3+1}$ are equal, ^[4] and once a state repeats, everything after it repeats as well, because each state determines the next one.

5. The loop closes at the start

The step map can be run backwards: from $F(a,b,c)=(b,c,d)$ we recover $a=(d-b-c)\bmod n$, so every state has exactly one predecessor.

Claim. There is a number $\lambda\ge1$, the period, such that the states $S_1,\dots,S_\lambda$ are all different and $S_{k+\lambda}=S_k$ for every $k\ge1$. In particular $S_{\lambda+1}=S_1$: the sequence of states has no tail.

Proof. Let $S_j$ be the first state that equals an earlier one, $S_j=S_i$ with $i\lt j$; it exists by Section 4. If $i\ge2$, the equal states $S_i$ and $S_j$ have the same unique predecessor, so $S_{j-1}=S_{i-1}$, a repetition before $S_j$, which contradicts the choice of $j$. So $i=1$, and we put $\lambda=j-1$. Then $S_1,\dots,S_\lambda$ are different, $S_{1+\lambda}=S_1$, and applying $F$ to both sides $k-1$ times gives $S_{k+\lambda}=S_k$. $\square$

We write $\lambda(n)$ when the modulus matters. Consequently $S_i=S_j$ exactly when $i-j$ is a multiple of $\lambda$, the remainders repeat with period $\lambda$ from $r_1$ on, and $n$ divides a term exactly when one of $r_1,\dots,r_\lambda$ is $0$; any $\lambda$ consecutive remainders are the same values in a rotated order. The state $(0,0,0)$ is mapped to itself and so is not on the loop of $S_1$, hence $\lambda\le n^3-1$. The state before $S_1$ is $F^{-1}(1,1,1)=(n-1,1,1)$, so every period ends with $r_\lambda=n-1$.

6. Worked example: the loops modulo $3$ and $27$

Modulo $3$ a whole period can be checked by hand. The remainders $r_1,\dots,r_{13}$ are $1,1,1,0,2,0,2,1,0,0,1,1,2$, and the next three are $1,1,1$ again; no earlier three consecutive remainders are $1,1,1$, so $\lambda(3)=13$. The period ends with $r_{13}=2=n-1$, as Section 5 predicts, and its zeros $r_4$, $r_6$, $r_9$ and $r_{10}$ show that $3$ is a divisor.

For $n=27$ the remainders begin

$1, 1, 1, 3, 5, 9, 17, 4, 3, 24,$
$4, 4, 5, 13, 22, 13, 21, 2, 9, 5,\ \dots$

The state first returns to $(1,1,1)$ as $S_{118}$, so $\lambda(27)=117$, and again the period ends with $r_{117}=26=n-1$. The $117$ remainders of one period take only $23$ of the $27$ possible values: $0$, $6$, $15$ and $18$ never occur. By Section 5 no later remainder is new, so $27$ divides no term. Modulo $9$ the period is $39$ and still contains zeros; they disappear only at $3^3$, and by Section 2 they never return for higher powers of $3$.

7. A non-divisor made of two divisors

The third odd non-divisor is $91=7\cdot13$, although $7$ divides $T_{10}$ and $13$ divides $T_{35}$. Modulo $7$ the period is $48$ and the zeros of one period are $r_{10}$, $r_{26}$ and $r_{42}$; modulo $13$ the period is $168$ and the zeros are $r_{35}$, $r_{43}$, $r_{91}$, $r_{99}$, $r_{147}$ and $r_{155}$. Both periods are even, so every zero modulo $7$ has an even index and every zero modulo $13$ an odd one. Because $7$ and $13$ have no common factor, $91$ divides a number exactly when $7$ and $13$ both do, ^[6] and no index $k$ has a zero for both. So $91$ divides no term, although both of its prime factors are divisors: their zeros never fall on a common index.

The same splitting gives the periods of composite numbers. By the Chinese remainder theorem a state modulo $91$ amounts to a pair of states modulo $7$ and modulo $13$, and the pair is back at its start exactly when both parts are, so $\lambda(91)=\mathrm{lcm}(48,168)=336$. Likewise $\lambda(15)=\mathrm{lcm}(13,31)=403$, more than $15^2$. For the Fibonacci numbers, whose period modulo $n$ is called the Pisano period, both the closed loop and this rule are standard. ^[5]

8. Floyd's tortoise and hare

The program finds the loop with Floyd's cycle-finding method. A sequence $x_0$, $x_1=f(x_0)$, … in a finite set runs along a tail of some length $\mu$ into a loop of length $\lambda$. A slow pointer, the tortoise, moves one step at a time and a fast one, the hare, two steps; for $i\ge\mu$, $x_i=x_{2i}$ exactly when $i$ is a multiple of $\lambda$, so the pointers meet within $\mu+\lambda$ steps while only two values are stored. ^[7] Our states have no tail by Section 5.

The program starts the tortoise on $S_2$ and the hare on $S_3$, so after $k$ rounds they stand on $S_{2+k}$ and $S_{3+2k}$. Before the first round and after every round it checks whether the third entry of either pointer is $0$.

Claim. If no zero is found, the pointers meet for the first time after $\lambda-1$ rounds, both on $S_1$, and by then the tortoise has checked the third entries of $S_2,\dots,S_{\lambda+1}$, which are the $\lambda$ consecutive remainders $r_4,\dots,r_{\lambda+3}$.

Proof. By Section 5 the pointers are equal after $k$ rounds exactly when $(3+2k)-(2+k)=k+1$ is a multiple of $\lambda$. This happens first for $k=\lambda-1$, and the tortoise then stands on $S_{\lambda+1}=S_1$. $\square$

Since $\lambda$ consecutive remainders form a whole period, a meeting without a zero proves that $n$ is a non-divisor. For $n=27$ the meeting comes after $116$ rounds, on $(1,1,1)$.

The tortoise is what makes the test complete: the hare visits only the states $S_3,S_5,S_7,\dots$ with odd index, and when $\lambda$ is even these are only half of the loop. Modulo $7$ the zeros $r_{10}$, $r_{26}$ and $r_{42}$ are the third entries of $S_8$, $S_{24}$ and $S_{40}$; since $\lambda(7)=48$ is even, the hare never meets one, and the tortoise finds $S_8$ in round $6$.

After a meeting the program walks around the loop once more, checking every state again. This walk is needed for sequences with a tail, where the pointers can meet before every state of the loop has been checked; here it only repeats the tortoise's $\lambda$ checks.

9. Counting the non-divisors

The program tests $n=3,5,7,\dots$ in turn and counts the non-divisors until the count reaches $124$. The first ten are $27$, $81$, $91$, $103$, $135$, $163$, $189$, $199$, $203$ and $221$. Three of them, $81$, $135$ and $189$, are multiples of $27$ as in Section 2; $91$, $203=7\cdot29$ and $221=13\cdot17$ are products of two divisors as in Section 7; and $103$, $163$ and $199$ are primes.

How the Code Works

The C++ program ^[8] keeps its settings in Options: target is $124$ unless --target= with decimal digits gives another value, and --skip-checkpoints switches the self-check off. parse_int_after_prefix reads the digits into an int without an overflow check, so a target above $2^{31}-1$ causes undefined behaviour. parse_arguments rejects any other argument and a target below $1$, and main then returns exit code $1$. Unless switched off, run_checkpoints requires solve(1) to return $27$ and solve(10) to return $221$, as in Section 9; if one of them fails, main returns exit code $2$, and otherwise it prints solve(options.target).

solve starts with n = 1 and adds $2$ before every test, so the candidates are $3,5,7,\dots$; it increases found whenever divides_tribonacci(n) returns false and returns n when found reaches the target. divides_tribonacci is the test of Section 8. Its local State holds the remainders a, b, c of a state and compares states with operator==, and the lambda next is the step map $F$. The function puts start on $S_1$, tortoise on $S_2$ and hare on $S_3$, and returns true as soon as the third entry c of either pointer is $0$. The while loop moves the tortoise one step and the hare two steps until the states are equal; the final do–while loop walks once around the loop from the meeting point, checking c again, and only then does the function return false.

The Python and Java versions run the same test and the same scan with the target fixed at $124$, without options or checkpoints, and return the result as a string. Python keeps a state in three variables and steps it with the nested function next_state. Java uses a small static class State with a method equals(State). A sum $a+b+c$ of remainders is at most $3(n-1)$, and for the target $124$ no candidate exceeds $6669$ by Section 2, so the sums stay at most $20004$ and the 32-bit int of C++ and Java cannot overflow; Python's integers are unbounded anyway.

Complexity and Verification

For a non-divisor the test calls the step map exactly $4\lambda(n)$ times: three times to place the pointers, three times in each of the $\lambda-1$ rounds and $\lambda$ times in the final walk; for $n=27$ that is $3+3\cdot116+117=468$ calls. For a divisor it stops at the latest when the tortoise reaches the first zero state, which lies among $S_2,\dots,S_{\lambda+1}$, so after at most $3\lambda(n)$ calls. Counting an operation on these small integers as one step, one candidate costs $O(\lambda(n))$ time, and only a few states are stored. By Section 5, $\lambda(n)\le n^3-1$, so a scan up to $N$ costs $O(N^4)$ at worst, but the true periods are much shorter: for every odd $n\le5001$ we found $\lambda(n)\lt2n^2$, with the largest ratio $\lambda(n)/n^2\approx1.87$ at $n=345=3\cdot5\cdot23$, where Section 7 and $\lambda(23)=553$ give $\lambda=\mathrm{lcm}(13,31,553)$${}=222859$. Within this range the work of a scan up to $N$ therefore grows at most like $N^3$.

The search for the $124$th non-divisor, without the two checkpoint searches, calls the step map $15\,846\,722$ times; $13\,704\,644$ of these calls belong to the complete tests of the $124$ non-divisors. On an Apple M4 Max, start-up included, the C++ program with its checkpoints takes a few hundredths of a second, the Java program about a tenth and the Python program about one second. Since the loop always closes at $S_1$, walking from $S_1$ until the state returns would need only $\lambda$ calls instead of $4\lambda$; the published programs use Floyd's method, which does not need Section 5.

The C++ program checks before the main run that the first odd non-divisor is $27$ and the tenth is $221$. For this article we also ran checks that are not part of the published solutions:

A separate program that walks every loop from $S_1$ back to $S_1$ agrees with the published test for every odd $n\le5001$, where the test made exactly $4\lambda(n)$ calls for every non-divisor and at most $3\lambda(n)$ for every divisor.
In the same range every odd multiple of a non-divisor is a non-divisor, and for all $2939$ pairs of coprime odd numbers $3\le a\lt b$ with $ab\le5001$ the period of $ab$ is the least common multiple of $\lambda(a)$ and $\lambda(b)$; the periods for $n\le20$ agree with the OEIS. ^[2]
The three programs and the separate program print the same number, and an instrumented copy of the Python program confirms the number of calls.

Footnotes and References

The references below supply the background facts used above. The closed loop of Section 5, the parity argument for $91$ and the analysis of the tortoise-and-hare test are derived in this article.

Project Euler 225 — Tribonacci Non-divisors. The official statement defines the sequence 1, 1, 1, 3, 5, 9, 17, 31, … by T₁ = T₂ = T₃ = 1 and Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃, states that 27 divides no term and is the first odd number with this property, and asks for the 124th odd number that divides no term.
OEIS A000213 — Tribonacci numbers. The entry starts with a(0) = a(1) = a(2) = 1, so Tₖ = a(k − 1) here. It states that a(n)/a(n − 1) tends to the tribonacci constant 1.839286755…, a root of x³ − x² − x − 1 = 0, and lists the Pisano period lengths 1, 1, 13, 4, 31, 13, 48, 8, 39, … for the moduli 1, 2, 3, …
Wikipedia — Modular arithmetic. Congruence modulo m is compatible with addition: if a₁ ≡ b₁ and a₂ ≡ b₂ (mod m), then a₁ + a₂ ≡ b₁ + b₂ (mod m); and a ≡ b (mod m) holds exactly when a mod m = b mod m.
Wikipedia — Pigeonhole principle. If n items are put into m containers with n > m, at least one container holds more than one item; in Section 4 the containers are the n³ possible states.
Wikipedia — Pisano period. The Fibonacci numbers modulo n are periodic, the period π(n) is the order of the invertible Fibonacci matrix modulo n, and for coprime m and n, π(mn) is the least common multiple of π(m) and π(n) by the Chinese remainder theorem. Sections 5 and 7 prove the periodicity and the lcm rule for this sequence.
Wikipedia — Chinese remainder theorem. For pairwise coprime moduli, the remainders of an integer determine its remainder modulo their product uniquely, and x mod N ↦ (x mod n₁, …, x mod nₖ) is a ring isomorphism.
Wikipedia — Cycle detection. The iterated values of a map of a finite set to itself run into a loop of length λ that starts at index μ. Floyd's algorithm moves one pointer by one step and the other by two; for i ≥ μ, xᵢ = x₂ᵢ exactly when i is a multiple of λ, and it needs O(1) storage and time proportional to μ + λ.
C++ — Euler225.cpp. The linked immutable C++ revision contains parse_arguments, divides_tribonacci, solve and run_checkpoints. It is the implementation record for this article.

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