Project Euler 479. Roots on the Rise

No.479 Roots on the Rise

一見すると\(S(n)\)が整数になることに驚きますが，実は簡単に示すことができます．

考え方とプログラム例．

まず与えられた方程式を変形して分かりやすい形にします．両辺に\(x^2\)をかけて，

\begin{align}
x = k^2(k+x^2)-kx^3
\end{align}

移項，整理すると

\begin{align}
kx^3-k^2x^2+x-k^3=0
\end{align}

後で使うので，\(f(x)=x^3-kx^2+\frac{x}{k}-k^2\)とおきます．(上の式の左辺を\(k)で割り，モニック(最高次の係数が1)にしたもの)

3次方程式なので，解と係数の関係から

\begin{align}
a_k+b_k+c_k &= k
\end{align}

が得られるので，

\begin{align}
\left\{\begin{array}{ll}
a_k+b_k &= k-c_k\\
b_k+c_k &= k-a_k\\
c_k+a_k &= k-b_k
\end{align}\right.
\end{align}

\(S(n)\)の式に代入すると

\begin{align}
S(n) &= \sum_{p=1}^n \sum_{k=1}^n (k-c_k)^p(k-a_k)^p(k-b_k)^p\\
&= \sum_{p=1}^n \sum_{k=1}^n \{(k-a_k)(k-b_k)(k-c_k)\}^p
\end{align}

さて，\(a_k, b_k, c_k\) は3次方程式\(f(x)=0\)の解なので，

\begin{align}
f(x) =  (x-a_k)(x-b_k)(x-c_k)
\end{align}

と書けるので，

\begin{align}
(k-a_k)(k-b_k)(k-c_k) &= f(k)\\
&= k^3-k^3+1-k^2\\
&= 1-k^2
\end{align}

よって，

\begin{align}
S(n) &= \sum_{p=1}^n \sum_{k=1}^n (1-k^2)^p
\end{align}

この式から，\(S(n)\)が\(n\)によらず整数になることが分かります．さて，和を取る順序を変えて先に\(p\)についての和を取れば，

\begin{align}
S(n) &= \sum_{k=1}^n (1-k^2)\frac{1-(1-k^2)^n}{1-(1-k^2)}\\
&= \sum_{k=1}^n (1-k^2)\frac{1-(1-k^2)^n}{k^2}
\end{align}