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 #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