Posts Tagged ‘prob26’

Problem 26 – Recurring Decimals

September 19, 2009

In problem 26, we are asked to find the integer less than a given bound whose reciprocal has the longest decimal period among such integers. That is, among all fractions 1/d where d is less than some bound, which fraction has the longest periodic part in its decimal representation?

According to Hardy and Wright, An Introduction to the Theory of Numbers (6th ed, Theorem 135),

The decimal for a rational number p/q between 0 and 1 is terminating or recurring, and any terminating or recurring decimal is equal to a rational number. If (p,q)=1, q=2^{\alpha}5^{\beta}, and \max(\alpha,\beta)=\mu, then the decimal terminates after \mu digits. If (p,q)=1, q=2^{\alpha}5^{\beta}Q, where Q>1, (Q,10)=1, and \nu is the order of 10 (mod Q), then the decimal contains \mu non-recurring and \nu recurring digits.

Let’s trim that down a bit. Our p=1, so automatically (p,q)=1 (this notation is for the greatest common divisor, as usual). If the denominator, q, is divisible by either 2 or 5, then either (1) the decimal terminates, or (2) the decimal repeats, with the same length recurring part as the reciprocal of a smaller integer. In either case, we will suppose that this q is not the answer. Either (1) its recurring part has length 1, being a string of 0s, or (2) we could return the smaller integer with the same length recurring part.

So, suppose our q is not divisible by 2 or 5. Then according to the theorem above, we may compute the length of the repeating part of the decimal for 1/q by finding the “order of 10 (mod q)”. That is, find the smallest p so that 10^p\equiv 1\pmod{q}. This is easy enough to find, just keep raising 10 to bigger powers, and taking the answer mod q, until you find 1.

Here’s my code

def solve(n):
    """ Return the d with largest decimal period, d<n """
    max_d, max_p = 2, 1
    for d in xrange(3,n,2):
        if(d % 5 != 0):
            # now find the order of 10 mod Q
            # that is, the smallest p for which 10^p == 1 mod Q
            p = 1
            tmd = 10 % d # tmd = 10 mod d
            while(tmd != 1):
                p += 1
                tmd = (tmd * 10) % d
            if (p > max_p):
                max_d, max_p = d, p
    return max_d

Pretty straightforward, I think. [Except, as of right now, WordPress doesn’t seem to be handling < and > correctly in that code. Grr]

There’s almost certainly more math we could do here. But this seems to work well enough for now.

Advertisements