飽きるまでProject Eulerに挑戦中

programming

はじめに

ネタバレ注意

タイトルの通り。 まずは一番簡単なレベルの問題を制覇したい。

Project Euler とは

About - Project Euler

一言で言うと数学絡みのプログラミングの問題を出しているサイト。 どの問題も1分以内で答えが出せる設定らしい。 コンピュータで力任せに計算して答えを出すこともできるが、数学的にエレガントな解き方があったりするとかしないとか。

問題例

ネタバレは推奨されていないが、そこら中に解法が転がっている。 はじめから解く気がない人や既に解いた人が見るのはいいと思う。 そもそもサイト上に解いた人が読める解説PDF付の問題が存在している。

Wikipediaで解説されているProblem 1と似たようなProblem 28 Number spiral diagonalsを問題例として紹介する。

Problem 28 - Project Euler

1001\times1001の螺旋状に並んだ数字の対角線部分の数字の和を求めよという問題。

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

5\times5の例では 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25 = 101になる。

実際に螺旋状に辿って角に来たときに足して行くのもよいが、正直自分にはそれは実装できない(できるが)。

足すべき数字を列挙すると次のようになる。

1 | 3, 5, 7, 9 | 13, 17, 21, 25 | \dots

懐かしき群数列。

今考えるのは 1001\times1001なのでとりあえず1は置いておく。 まず螺旋の大きさは(奇数)x(奇数)になる。 数字は1から始まり1ずつ増えていくので最大の数字はその(奇数)の2乗。

|で区切られた(群という)四つの項は外側二つの和と内側二つの和が等しいので群の最初の項と最後の項がわかれば、それらを足して2倍するとその群の項の和が得られる。

例: | 3, 5, 7, 9|に注目すると、 3 + 9 = 5 + 7 = 12。この群の項の和は2 \times 12 = 24。

1を第0群とする。 i \geq 1のとき、第 i群の最後の項は { (2i + 1)^{2} } であり、最初の項は前の群の最後の項より 2i大きい。

したがって、第i群の項の和は \displaystyle 2\{(2i - 1)^{2} + 2i + (2i + 1)^{2}\} = 16i^{2} + 4i + 4 \, (i \geq 1)である。

よって、第0群から第n群までの項の和は

{\displaystyle 1 + \sum_{i=1}^{n} (16i^{2} + 4i + 4) = 1 + \frac{16}{3}n^{3} + 10n^{2} + \frac{26}{3}n = 1 + \frac{2n(n(8n + 15) + 13)}{3} }

である(n=0のときも成立つ)。

1001\times1001の螺旋で最大の数は 1001^{2}だから、第500群まである。 n = 500で計算すれば答えが出る。

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t sum(uint64_t n)
{
    return 1 + 2 * n * (n * (8 * n + 15) + 13) / 3;
}

int main(void)
{
    uint64_t ans = sum(500);
    printf("%"PRIu64"\n", ans);
    return 0;
}