和の公式

Euler Problemという問題があります。問題の#1はこのページに日本語で載っています。電卓があれば手計算でもできる問題だと思います。3の倍数の和と5の倍数の和から、(3の倍数∧5の倍数)15の倍数の和を引いた数が答えになりますよね。そういう方針でコードを書きます。

コード

sumOneTo :: Int -> Int
sumOneTo n = sum [1..n]
answer :: Int -> Int
answer n = 3*sumOneTo((n-1) `div` 3) +
           5* sumOneTo((n-1) `div` 5) -
           15*sumOneTo((n-1) `div` 15)

"answer 10"で23が出ることを確認。"answer 1000"だと233168。

算数

ところで1+2+..+nの公式はn*(n+1)/2になります。この公式はn*nの面積の正方形をした箱の中に1*1のブロックを1コ,2コ,...nコと左から順に敷き詰めるようなことを考えてみると分かります。このように敷き詰めたとき、ちょうど対角線上にあるnコのブロックを除くと、n*nマスの箱のちょうど半分埋まることが分かります。つまり残ったブロックの数は(n*n-n)/2です。先ほど除いたnコのブロックを足せば、全体のブロックの数が分かります。それは(n*n-n)/2+n=n*(n+1)/2です。

コード2

もっと人間の方が何も計算せずに結果を出す方法は次のようになります。

answer :: Int -> Int
answer n = sum [a| a <- [1..(n-1)], a `mod` 3 == 0 || a `mod` 5 == 0]

Cで書くと少し長くなる。

#include <stdio.h>
#include <assert.h>
int answer(int n, FILE* fp) {
int tot = 0;
int i;
for(i = 1; i < n; i++) {
  if((i % 3) == 0 || (i % 5) == 0) {
    tot += i;
  }
}
if(fp)
  fprintf(fp, "%d\n", tot);
  return tot;
}

int main(void) {
  assert(23 == answer(10, NULL));
  assert(233168 == answer(1000, NULL));
  return 0;
}