Project Eulerに挑戦: 問題1

Table of Contents

問題1

1000未満の自然数で3あるいは5の倍数となっている数の総和を求めよ.

Cで解く

1から1000未満まで繰り返すfor文を作成し, その中で条件に合っている場合に総和に足し込む操作を行えば良い.

1:  int e001() {
2:      int s = 0;
3:      int n;
4:      for (n = 1; n < 1000; n++) {
5:          if (n % 3 == 0 || n % 5 == 0)
6:              s += n;
7:      }
8:      return s;
9:  }

Scalaで解く

Range(1, n) あるいは 1 until n は1以上n未満の整数リストを作成する (正確にはリストではない).

scala> Range(1, 10)
res: ... = Range(1, 2, 3, 4, 5, 6, 7, 8, 9)
scala> 1 until 10
res: ... = Range(1, 2, 3, 4, 5, 6, 7, 8, 9)

filterで条件に合うものだけを取り出せる.

scala> Range(1, 10).filter(n => n % 3 == 0 || n % 5 == 0)
res: ... = Vector(3, 5, 6, 9)

sumで合計を求めることができる.

scala> Range(1, 10).filter(n => n % 3 == 0 || n % 5 == 0).sum
res: Int = 23

したがって回答は以下で求められる.

scala> Range(1, 1000).filter(n => n % 3 == 0 || n % 5 == 0).sum

手で解く

15で割った余りで考える. 15m+0, 15m+1, …, 15m+14 のうち, 3または5で割り切れる数は 15m+0, 15m+3, 15m+5, 15m+6, 15m+9, 15m+10, 15m+12 であり, 合計は 105m+45 である.

m=66の時 15mは990となる. したがって,以下の式は990未満についての求めるべき総和を与える. \[ \sum_{m=0}^{65} (105m+45) = \frac{105}{2} 65\cdot 66 + 2970 \] これに 990, 993, 995, 996, 999 を加えれば回答が得られる.

改善版

よく考えると,3あるいは5の倍数の総和は, 3の倍数の総和と5の倍数の総和の合計から, 15の倍数の総和を引いた値である.

したがって,与えられた数 p の倍数の総和さえ求められれば良い. これは \(m = \lfloor 1000/p \rfloor\) と置けば,以下の式で求められる. \begin{eqnarray*} \sum_{i=1}^{m} p i & = & \frac{p}{2}m(m+1) \end{eqnarray*} p=3 の時の m は 333,p=5 の時の m は 199,p=15 の時の m は 66 であるから, 求める回答は以下の式で与えられる. \[ \frac{3}{2}333\cdot 334 + \frac{5}{2}199\cdot 200 - \frac{15}{2}66\cdot 67 \]

改善版 C

プログラムは以下のように改善できる.

1:  int msum(int p, int lim) {
2:      int m = (lim - 1) / p;
3:      return p * m * (m + 1) / 2;
4:  }
5:  
6:  int e001() {
7:      return msum(3, 1000) + msum(5, 1000) - msum(15, 1000);
8:  }

改善版 Scala

lim 未満の p の倍数の総和を求める関数を定義する.

1:  def msum(p: Int, lim: Int) = {
2:     val m = (lim - 1) / p
3:     p * m * (m + 1) / 2
4:   }

したがって回答は以下で求められる.

scala> msum(3, 1000) + msum(5, 1000) - msum(15, 1000)

Date: 2017-09-29 21:44:00 JST

Author: 田村直之

Validate XHTML 1.0