Project Euler problem 28

DISCLAIMER: This post contains a solution to Project Euler problem 28. Go away if you don't want to know. DISCLAIMER 2: I am not the most mathematically minded person, so this may/will seem slow for pro mathematicians.

See here for the problem description.

So I got around to solving problem 28 last night (14 more until I get to level 2!) and, like most problems, I quickly found out the reason why this problem is on Project Euler: there's a subtle and beautiful pattern hidden in the middle of what seems like a random math problem.

The first pattern is that as the pyramid builds, the top right corners are always perfect squares of 1, 3, 5, 7 etc...

43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20  7  8  9 10 27
40 19  6  1  2 11 28
39 18  5  4  3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31

So we start looping from 1 to 1001 by 2s.

The other subtle pattern is that the gap between the corners also increments by 1, 3, 5, 7 etc... with each new layer of the pyramid. Therefor if we are at the top right corner which is n², the top left corner is n² - n + 1, the bottom left corner is n² - 2n + 2, and the bottom right corner is n² - 3n + 3, which follows an easy summation pattern which we can represent with a simple Lisp function:

(defun sum-corners (n)
  (loop for x from 0 to 3
     sum (+ (- (* n n)
               (* x n))
            x)))

Note: That can be simplified further into one equation, rather than a loop, if you like.

And a simple loop, described earlier, to tie everything together:

(defun euler-28 ()
  (1+ (loop for n from 3 to 1001 by 2
         sum (sum-corners n))))

Done. A simple problem disguised as something a little more difficult than it really is and has a couple of simple but cool patterns.