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 where 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 between 0 and 1 is terminating or recurring, and any terminating or recurring decimal is equal to a rational number. If , , and , then the decimal terminates after digits. If , , where , , and is the order of 10 (mod ), then the decimal contains non-recurring and recurring digits.

Let’s trim that down a bit. Our , so automatically (this notation is for the greatest common divisor, as usual). If the denominator, , 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 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 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 by finding the “order of 10 (mod )”. That is, find the smallest so that . This is easy enough to find, just keep raising 10 to bigger powers, and taking the answer mod , 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_dPretty 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