$N$を$3$以上の自然数とする。

略記して解き方だけ示します。各桁の値を0,3,6,9（残余0だが0と非零で区別）・残余1（1,4,7）・残余2（2,5,8）の４種類の状態で扱います。各状態のその桁に置ける実際の数字の個数はそれぞれ1,4,3,3（順に0,3,6,9,残余1,残余2）です。隣接制約は「現在の桁が非零なら次の桁の残余と和が0になってはいけない」という形になり，状態間の遷移重みは次のようになります（行が現在，列が次）：

・現在=0（ゼロ）なら次は任意：(1,4,3,3)

・現在=R0非零なら次は残余0禁止：(0,0,3,3)

・現在=R1なら次は残余2禁止：(1,4,3,0)

・現在=R2なら次は残余1禁止：(1,4,0,3)

ここで列順は(0, R0非零, R1, R2)で重みが並んでいます。先頭桁はゼロ不可なので初期ベクトルは(0,4,3,3)になります。

求めたいのは「全桁の残余の和≡0(mod 3)」となる列の総数なので，残余和でふるい分けるには三重根を使う母関数法を使います。具体的にはω = e^{2πi/3} として

count = (1/3) ∑_{t=0}^{2} v(ω^t) · M(ω^t)^{N-1} · u

と書けます。ここで v(z) は先頭桁の各状態に z^{残余値} をかけた重みベクトル（先頭のゼロは使えないので要注意），M(z) は上の遷移行列の各列に対応する状態の残余に z^{残余} を掛けた遷移重み行列，u=(1,1,1,1)^T は終端を合計するベクトルです。t=0の項は全列挙（残余制約無視）の寄与を与え，t=1,2の項で残余和が0のものだけを抽出します。

以上で数え上げは行列計算に帰着します。具体的な N に対してはこの式で数値を出せば正確な個数が得られます。問題が一般 N に対する閉形式解を求める意図であれば，上記の行列を対角化して固有値で書き下すことにより明示的な式を得られますが，手順はここに示した方法と同等です。