20070908

Three Parts of Division

I was going to update this blog at some point.

I'm back to solving problems on Project Euler. I've solved the easy ones, and now I'm getting around to the medium difficulty problems. I like #26.

Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

That's kinda interesting. Every time you divide two numbers, there are three parts: The integer part, the non-repeating decimal part, and the repeating decimal part.

I wrote up this little piece of Python to compute the three parts. It is a forced base-10 long division calculator, and it makes good use of Python's stings doubling as list, which is a feature that I always thought was nice about Python.

def division(num, den):
    ipart = str(num / den);
    fpart = ""
    rpart = ""
    seen  = [ num%den ]
    while num % den != 0:
        num        = (num%den) * 10
        multiple   = num / den
        fpart     += str(multiple)
        num        = num - (den * multiple)
        c = 0
        quit = False
        for i in seen:
            if num == i: # This number has been seen before.
                rpart = fpart[c:] # Make characters from c to end of list part of repeating part
                fpart = fpart[:c] # Truncate fpart
                quit = True
                break
            c = c + 1
        if quit:
            break
        seen += [num]
    return [ipart, fpart, rpart]

This method accepts two arguments: An integer numerator and an integer denominator. The return is a list with three items: The whole number part, the non-repeating decimal part, and the repeating decimal part. Each part is a string data type (because sometimes these parts can be excessively long for python's Integer type.)
>>> division(1,4)
['0', '25', '']
>>> division(1,6)
['0', '1', '6']
>>> division(1,7)
['0', '', '142857']

No comments: