Project Euler 225: Tribonacci non-divisors
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.
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 SolutionRuns < 0.001 seconds in Python 2.7.
def prob225(n): c, i = 0, 27 while c < n: t1, t2, t3 = 1, 1, 3 while t3>0 and t1 * t2 * t3 != 1: t1, t2, t3 = t2, t3, (t1 + t2 + t3) % i if t3>0: c+=1 i+=2 return i-2 print 'Project Euler 225 Solution = ', prob225(124)Use this link to get the Project Euler 225 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- 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.