The task in Problem 26 of Project Euler is:
Find the value of d < 1000 for which $\frac{1}{d}$ contains the longest recurring cycle in its decimal fraction part.
How to solve
Think about how you divide with pen and paper. How do you recognize that you have a cycle?
You look at the rest. If you've seen the rest before, you are just about to get into the cycle.
My solution
This brute force solution finds the solution instantly.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import unittest
def getCycle(p, q):
assert p >= 0
assert q > 0
while p >= q:
p -= q
if p == 0:
# p/q is an integer
return ""
digits = {} # map rest to digit number
# for 0.1234567, 1 is the digit #0, 2 digit #1, ...
i = 0
cycle = ""
rest = p
while True:
digits[rest] = i
rest *= 10
tmp = rest / q
rest -= tmp * q
cycle += str(tmp)
if rest in digits:
return cycle[digits[rest] :]
i += 1
def euler26(maximum=1000):
maxCycleLength = 0
number = 1
for i in range(1, maximum + 1):
tmp = len(getCycle(1, i))
if tmp > maxCycleLength:
maxCycleLength = tmp
number = i
return (number, maxCycleLength)
class TestSequenceFunctions(unittest.TestCase):
def setUp(self):
self.seq = range(10)
def test_simpleSequences(self):
self.assertEqual(getCycle(4, 2), "")
self.assertEqual(getCycle(1, 6), "6")
for i in range(1, 9):
self.assertEqual(getCycle(i, 9), str(i))
self.assertEqual(getCycle(1, 7), "142857")
if __name__ == "__main__":
# unittest.main()
print(euler26(1000))