Project Euler: Problem 26

The task in Problem 26 of Project Euler is:

Find the value of d

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/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 xrange(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 xrange(1,9):
            self.assertEqual(getCycle(i,9), str(i))
        self.assertEqual(getCycle(1,7), "142857")

if __name__ == '__main__':
    #unittest.main()
    print euler26(1000)

Leave a Reply

comments powered by Disqus