MathJax

SyntaxHighlighter

Highlight

Custom CSS

Saturday, January 23, 2010

Project Euler #120: Square remainders

Here is the question:

Let r be the remainder when $$(a-1)^n + (a+1)^n$$ is divided by $$a^2$$.

For example, if $$a = 7$$ and $$n = 3$$, then $$r = 42$$: $$6^3 + 8^3 = 728 \equiv 42 \pmod{49}$$. And as $$n$$ varies, so too will $$r$$, but for $$a = 7$$ it turns out that $$r_{max} = 42$$.

For $$3 \leq a \leq 1000$$, find $$\sum r_{max}$$.

Actually this, is a very easy problem, solved using a formula you may have learned about in elementary school.

The formula mentioned is, of course, the binomial formula; the same one that forms Pascal's Triangle. If one simply expands $$(a-1)^n$$ and $$(a+1)^n$$ via the binomial formula, then adds them together, one sees that the odd terms cancel each other out.

Now:

When $$n = 1$$, the remainder modulo $$a^2$$ is just $$2a$$.

When $$n > 1$$, and $$n$$ even, it's easy to see that the remainder is $$2$$.

When $$n > 1$$, and $$n$$ odd, the remainder is $$2na$$.

It remains to do a search through values of n to find the maximum remainder. Here is a solution in Scala:

def f(a: Int) = {
  def g(n: Int) = n match {
    case 1 => 2 * a
    case _ if n % 2 == 0 => 2
    case _ => 2 * n * a
  }                 
  (1 to (2 * a)).map(g _)
          .map(_ % (a * a))
          .reduceLeft(_ max _)
}

println((3 to 1000).map(f _).reduceLeft(_ + _))
Post a Comment