// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 225 Solution

Project Euler 225 Solution

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 T1 = T2 = T3 = 1 and Tn = Tn-1 + Tn-2 + Tn-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 124th 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

Runs < 0.001 seconds in Python 2.7.

download arrowUse this link to get the Project Euler 225 Solution Python 2.7 source.

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.
Project Euler 225 Solution last updated

Discussion

No comments yet.

Post a comment