\(G_{i,d}\) の石の大きさの合計 \(S_i\) は以下の漸化式で表せる.

\[S_1 = d \\ S_{i+1} = (d+1)S_i + d(i+1)\]

ここで階差を取ると,

\[S_{i+2}-S_{i+1} = (d+1)(S_{i+1}-S_i) + d\]

となる. \(T_i = S_{i+1}-S_i\) と置くと,

\[T_1 = d(d+2) \\ T_{i+1} = (d+1)T_i + d\]

となり, これを解いて,

\[\begin{align} T_i &= (d(d+2)+1)(d+1)^{i-1}-1 \\ &= (d+1)^{i+1}-1 \end{align}\]

となる. よって階差が求められたので,

\[\begin{align} S_i &= d + \sum_{k=1}^{i-1} ((d+1)^{k+1}-1) \\ &= d + \frac{(d+1)^2((d+1)^{i-1}-1)}{d} - (i-1) \\ &= \frac{(d+1)((d+1)^i - 1)}{d} - i \end{align}\]

となる. 累乗部分は繰り返し2乗法で計算する.

次に下から \(n\) 段に含まれる石の大きさの合計を求める.

\(G_{i,d}\) の高さを \(H_i\) とすると, これは,

\[H_{i+1} = (d+1)H_i + d\]

となる. これを \(n\) を超えない範囲で計算しておく. 最低でも2の累乗のペースで大きくなるので, \(i\) は大きくとも30程度である.

\(n\) を超えない \(H_i\) を求める. そうすると, \(n\) の中にはすくなくとも1つの \(G_{i,d}\) が含まれるので, これを取り除いて再帰的に \(n\) が \(0\) になるまで繰り返す.