C#で Project Euler P6 別解

はじめに

　C#で Project Euler P6 - さんぽみち　の効率のいい方法を見つけので実装しました。
　どう考えてももっと早くなりそうだったのでちゃんと考えました。
　手続的な実装というよりも一般項を求めることがメインです。

問題

Problem 6 「二乗和の差」
最初の10個の自然数について, その二乗の和は,
1² + 2² + ... + 10² = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)² = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
Problem 6 - PukiWiki

解答

public static class P6
{
    public static void Main()
    {
        Console.WriteLine(Calc());
    }
    
    private static long Calc()
    {
        return GetPowSub(100);
    }
    private static long GetPowSub(long n)
    {
        return (((3 * n + 2) * n - 3) * n - 2) * n / 12;
    }
}

計算量　$O(1)$

二乗の和を式１、和の二乗を式２とすると、 \begin{align*} 式２=&(N_1 + N_2 + N_3 + ... + N_n)^2 \\ = &N_1N_1+N_1N_2+N_1N_3+...+N_1N_n+N_2N_1+N_2N_2+N_2N_3+...+N_2N_n+ \\ &N_3N_1+N_3N_2+N_3N_3+...+N_3N_n+...+N_nN_1+N_nN_2+N_nN_3+...+N_nN_n \\ = &(N_1^2+N_2^2+N_3^2+...+N_n^2)+2\{N_1(N_2+N_3+...+N_n)+N_2(N_3+...+N_n)+...N_{n-1}(N_n)\}\\ =&Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}j \end{align*} ここで、 \begin{align*} 式１ = &Σ_{k=1}^n N_k^2 \end{align*} であるため、 \begin{align*} 式２-式１ = &Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j - Σ_{k=1}^n N_k^2\\ =&2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j\\ =&2Σ_{k=1}^{n-1}k\frac{(k+1+n)}{2}(n-k)\\ =&Σ_{k=1}^{n-1}k(k+n+1)(-k+n)\\ =&Σ_{k=1}^{n-1}k(-k^2+n^2-k+n)\\ =&Σ_{k=1}^{n-1}(-k^3-k^2+kn^2+kn)\\ =&-Σ_{k=1}^{n-1}k^3-Σ_{k=1}^{n-1}k^2+Σ_{k=1}^{n-1}k(n^2+n)\ \ \ \ \ \ \ \ \ \ \ \ ...① \end{align*} と表せる。

まず、$-Σ_{k=1}^{n-1}k^3$について考える。 \begin{align*} -Σ_{k=1}^{n-1}k^3 =&-(Σ_{k=1}^{n}k^3 - n^3)\\ =&-Σ_{k=1}^{n}k^3 + n^3\\ =&-\{\frac{n}{2}(n+1)\}^2 + n^3\\ =&-\frac{n^2}{4}(n^2+2n+1) + n^3\\ =&-\frac{n^2}{4}(n^2+2n+1-4n)\\ =&-\frac{n^2}{4}(n^2-2n+1)\ \ \ \ \ \ \ \ \ \ \ \ ...② \end{align*} 次に、$-Σ_{k=1}^{n-1}k^2$について考える。 \begin{align*} -Σ_{k=1}^{n-1}k^2 =&-(Σ_{k=1}^{n}k^2 - n^2)\\ =&-Σ_{k=1}^{n}k^2 + n^2\\ =&-\frac{n}{6}(n+1)(2n+1) + n^2\\ =&-\frac{n}{6}(2n^2 + 3n + 1) + n^2\\ =&-\frac{n}{6}(2n^2 + 3n + 1 - 6n)\\ =&-\frac{n}{6}(2n^2 - 3n + 1)\ \ \ \ \ \ \ \ \ \ \ \ ...③ \end{align*} 最後に、$Σ_{k=1}^{n-1}k(n^2+n)$について考える。 \begin{align*} Σ_{k=1}^{n-1}k(n^2+n) =&(n^2+n)Σ_{k=1}^{n-1}k\\ =&(n^2+n)\frac{(1+n-1)}{2}(n-1) \\\ =&\frac{n}{2}(n^2+n)(n-1) \\\ =&\frac{n^2}{2}(n+1)(n-1) \\\ =&\frac{n^2}{2}(n^2-1) \ \ \ \ \ \ \ \ \ \ \ \ ...④ \end{align*} ①=②+③+④ であるため、 \begin{align*} &-Σ_{k=1}^{n-1}k^3-Σ_{k=1}^{n-1}k^2+Σ_{k=1}^{n-1}k(n^2+n)\\ =&-\frac{n^2}{4}(n^2-2n+1) -\frac{n}{6}(2n^2 - 3n + 1)+\frac{n^2}{2}(n^2-1)\\ =&\frac{n}{12}(-3n^3+6n^2-3n) +\frac{n}{12}(-4n^2 + 6n - 2)+\frac{n}{12}(6n^3-6n)\\ =&\frac{n}{12}(-3n^3+6n^2-3n-4n^2 + 6n - 2+6n^3-6n)\\ =&\frac{n}{12}(3n^3+2n^2-3n - 2)\\ =&(((3n+2)n-3)n - 2)n\frac{1}{12} \\ \end{align*} となり、一般項が求まる。

2016/05/09追記

　上記の方法でも導出できるが冷静に考えると $(Σ_{k=1}^nk)^2-Σ_{k=1}^nk^2$ を、等差数列の和及び平方数の和の公式から簡単にするだけでよかった気がした、両方の公式を上でも使ってるし。
　その方針でやってみると、 \begin{align*} (Σ_{k=1}^nk)^2=&(\frac{n + 1}{2}n)^2 \\ =&\frac{n^2 + 2n + 1}{4}n^2 \\ =&\frac{n^2}{4}(n^2 + 2n + 1) \\\\ Σ_{k=1}^nk^2=&\frac{n}{6}(n+1)(2n+1) \\ =&\frac{n}{6}(2n^2 + 3n + 1) \\\\ (Σ_{k=1}^nk)^2-Σ_{k=1}^nk^2 =& \frac{n^2}{4}(n^2 + 2n + 1) - \frac{n}{6}(2n^2 + 3n + 1) \\ =& \frac{n}{12}(3n^3 + 6n^2 + 3n) + \frac{n}{12}(-4n^2 - 6n - 2) \\ =& \frac{n}{12}(3n^3 + 6n^2 + 3n - 4n^2 - 6n - 2)\\ =& \frac{n}{12}(3n^3 + 2n^2 - 3n - 2)\\ =& (((3n + 2)n - 3)n - 2)n\frac{1}{12} \end{align*} 　前回のから引き継いで書いてたら出発点を間違えてえらい遠回りに。。。