MathJax

SyntaxHighlighter

Highlight

Custom CSS

Saturday, January 23, 2010

Project Euler #26: Reciprocal cycles

Here is problem #26:

Insight into some elementary number theory will help shorten this search for the longest cycle.

It's better to start computing cycle lengths starting from 999 down because a number 1/n cannot have more than n repeating digits in its decimal expansion. To convince yourself of this, think about what is happening when you do long division. Suppose you calculating 1/7:

First you divide 1.0 by 7 and find the remainder. Computationally, this is the same as dividing 10 by 7, then multiplying the remainder by 10, dividing by 7 again, and so on. See the sequence of computations for calculating 1/7 below, written in this manner:

$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$
$$(2 * 10) / 7 = (2) * 7 + 6$$
$$(6 * 10) / 7 = (8) * 7 + 4$$
$$(4 * 10) / 7 = (5) * 7 + 5$$
$$(5 * 10) / 7 = (7) * 7 + 1$$
$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$

Notice that the parenthesized numbers on the right hand side are precisely the first few digits in the decimal expansion of 1/7 = .14285714... and further notice that:

$$1 * 10 \pmod{7} \equiv 10^1 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^2 \pmod{7}$$
$$2 * 10 \pmod{7} \equiv 10^3 \pmod{7}$$
$$6 * 10 \pmod{7} \equiv 10^4 \pmod{7}$$
$$4 * 10 \pmod{7} \equiv 10^5 \pmod{7}$$
$$5 * 10 \pmod{7} \equiv 10^6 \pmod{7}$$
$$1 * 10 \pmod{7} \equiv 10^7 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^8 \pmod{7}$$

As you can see, at the next to last step, the digits start to repeat. In fact, the number of repeating digits is given by $$e = ord_{10}n$$, where $$e$$ is the smallest positive integer such that $$10^e \equiv 1 \pmod{n}$$. The preceding is not a proof of this fact, but hopefully is convincing enough.

I have written another blog post about calculating order, so please refer to that if needed. Finally, here is a Ruby program exploiting this info:

class Array
  def tail
    self.drop(1)
  end
end

def order(a, m)
  b = 1
  (1...m).each do |i|
    b = (a*b)%m
    return i if b == 1
  end
end

def max_period(best, numbers)
  return best if numbers.nil?
  n = numbers.first
  ord = order(10, n)
  return [n, ord] if ord == n - 1
  return max_period([n, ord], numbers.tail) if ord > best.last
  return max_period(best, numbers.tail)
end

numbers = 999.step(2, -1).select { |n| n % 2 != 0 && n % 5 != 0 }
result = max_period([0, 0], numbers)
puts result.first
Post a Comment