Project Euler 225: Tribonacci non-divisors

Problem Description

The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 …
is defined by T₁ = T₂ = T₃ = 1 and T_n = T_n-1 + T_n-2 + T_n-3.

It can be shown that 27 does not divide any terms of this sequence.
In fact, 27 is the first odd number with this property.

Find the 124^th odd number that does not divide any terms of the above sequence.

Analysis

Knowing this series is periodic we have to expand it modulo N until it begins to repeat again to (1,1,1) before having any zero calculation to accept it as not being able to divide our sequence. A zero calculation would indicate that N can divide a term and would be excluded from our list. This process is finite but could take many iterations.

Project Euler 225 Solution

Afterthoughts

• You could improve this solution by caching the terms found in the sequence and just increment the counter, c, and skip the calculations for each multiple of that term. For example, after finding 27 you could skip 81 (27 x 3) and add 1 to the counter.