Project Euler Problem 225

Solution

Answer: 2009

Let

$$T_1=T_2=T_3=1,\qquad T_n=T_{n-1}+T_{n-2}+T_{n-3}.$$

This is the Tribonacci sequence:

$$1,1,1,3,5,9,17,31,57,105,\dots$$

We seek the $124^\text{th}$ odd integer $m$ such that no term of the sequence is divisible by $m$.

---

1. Mathematical analysis

We only care about the sequence modulo $m$.

Define the state vector

$$S_n=(T_n,T_{n+1},T_{n+2}) \pmod m.$$

Because

$$T_{n+3}=T_{n+2}+T_{n+1}+T_n,$$

the next state is completely determined by the current one:

$$(a,b,c)\mapsto (b,c,a+b+c \bmod m).$$

Thus the sequence modulo $m$ is a deterministic finite-state process.

Since there are only $m^3$ possible triples modulo $m$, the sequence must eventually repeat. In fact, because the transformation is invertible modulo $m$, the sequence is purely periodic.

Therefore:

• either some term becomes $0 \pmod m$,
• or the sequence cycles forever without ever hitting $0$.

So to test a candidate odd integer $m$, we simply generate Tribonacci values modulo $m$ until the state repeats.

If we encounter a zero term before repetition, then $m$ divides some Tribonacci number.

If the cycle closes without seeing zero, then $m$ is one of the desired numbers.

The problem statement tells us:

$$27$$

is the first odd number with this property.

We continue this process until finding the $124^\text{th}$ such odd number.

---

2. Python implementation

def tribonacci_has_zero_mod(m):
    """
    Return True if some Tribonacci number is divisible by m.
    Return False otherwise.
    """

    # Initial Tribonacci values modulo m
    a = b = c = 1 % m

    seen = set()

    while (a, b, c) not in seen:

        # If any current term is 0 mod m,
        # then m divides a Tribonacci number
        if a == 0 or b == 0 or c == 0:
            return True

        seen.add((a, b, c))

        # Advance recurrence:
        # T_{n+3} = T_n + T_{n+1} + T_{n+2}
        a, b, c = b, c, (a + b + c) % m

    # Cycle closed without seeing 0
    return False

target = 124
count = 0
n = 1

while True:

    if n % 2 == 1:  # odd numbers only

        if not tribonacci_has_zero_mod(n):
            count += 1

            if count == target:
                print(n)
                break

    n += 2

---

3. Code walkthrough

Function tribonacci_has_zero_mod(m)

We work entirely modulo $m$.

Initialization

a = b = c = 1 % m

These represent consecutive Tribonacci terms.

---

Detecting repetition

seen = set()

Because there are finitely many triples modulo $m$, eventually a triple repeats.

---

Main loop

while (a, b, c) not in seen:

Continue until the state cycles.

---

Divisibility test

if a == 0 or b == 0 or c == 0:
    return True

If any term is $0 \pmod m$, then $m$ divides a Tribonacci number.

---

Advance the recurrence

a, b, c = b, c, (a + b + c) % m

This implements

$$T_{n+3}=T_n+T_{n+1}+T_{n+2}.$$

---

If the cycle closes

return False

then zero never appeared, so $m$ has the desired property.

---

Outer search loop

We test only odd numbers:

n += 2

and count those that never divide any Tribonacci term.

The $124^\text{th}$ such number is printed.

---

4. Small verification

Testing small odd values:

• $1$: divides everything.
• $3$: divides $T_4=3$.
• $5$: divides $T_5=5$.
• $27$: never divides any Tribonacci term.

The computation reproduces the statement that $27$ is the first valid odd number.

Continuing the search yields:

$$27,81,91,103,\dots$$

and the $124^\text{th}$ value is:

$$2009.$$

This is odd and consistent with the required ordering.

---

Answer: 2009