MathJax

Syntax Highlighter CSS (shCore.css)

Syntax Highlighter CSS (shThemeDefault.css)

Syntax Highlighter JS (shCore.js)

Syntax Highlighter JS (shAutoloader)

Highlight CSS (default.css)

Highlight JS (highlight.pack.js)

Syntax Highlighter CSS (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