Project Euler 問題6（和の2乗と2乗の和の差）を解いてみる

Project Euler で紹介されている問題6を解いてみました。素直なプログラムと数列の和の公式を使ったプログラムを示します。

問題6（和の2乗と2乗の和の差）

解答例

整数（自然数）のデータ、繰り返し、出力ができれば、どのプログラミング言語でも解くことができるでしょう。C での記述例を示します。

#include <stdio.h>

int main(void)
{
	int i, sum1, sum2;

	sum1 = 0;
	sum2 = 0;
	for (i = 1; i <= 100; ++i) {
		sum1 += i;
		sum2 += i * i;
	}

	printf("Problem006: %d\n", sum1 * sum1 - sum2);

	return 0;
}

解答例（改善版）

問題1と同じく、上限の数の大きさに依存しない解法があります。

高校数学（数学B「数列」）では、以下を公式（数列の和の公式）として扱っています。

$$ 1 + 2 + … + n = \frac{1}{2}n(n+1) $$

$$ 1^2 + 2^2 + … + n^2 = \frac{1}{6}n(n + 1)(2n + 1) $$

$$ 1^3 + 2^3 + … + n^3 = \left\{ \frac{1}{2}n(n+1) \right\}^2 $$

数列の和の公式は、いろいろな証明方法がありますが、式の形が分かっている前提であれば、数学的帰納法を使った証明が分かりやすいでしょうか。

今回の問題では、上2つの公式を使うと、以下のようにループ文が無くても計算ができます。

#include <stdio.h>

int main(void)
{
	int n, sum1, sum2;

	n = 100;
	sum1 = n * (n + 1)/ 2;
	sum2 = n * (n + 1) * (2 * n + 1)/ 6;

	printf("Problem006: %d\n", sum1 * sum1 - sum2);

	return 0;
}

最後に

これは、解いた人が4番目に多い問題でした（解いた人が多い順から、問題1、問題2、問題3、問題6 2022/8/12時点）。この問題は、数学的な背景が少なくても、手順を素直にコードとして表現できれば解けるため、取り組みやすいのではないでしょうか。

引き続き、Project Euler の問題を紹介していきます。