まずは \(S_0\) を決める.

\[N = S_0 - 2(S_1(-2)^0 + S_2(-2)^1 + \dots + S_k(-2)^{k-1})\]

となるので, \(N\) が \(2\) で割り切れれば \(S_0 = 0\) であり, そうでなければ \(S_0 = 1\) となる.

次に \((S_0-N)/2\) を新しい \(N\) とすると,

\[N = S_1(-2)^0 + S_2(-2)^1 + \dots + S_k(-2)^{k-1}\]

以下 \(N\) が \(0\) になるまでこれを続ける.