に、簡単な方法（実際に9で割ってさらに判定するのは禁止、二桁以上での割り算禁止）で
判別できないか考えてみたところ、以下のような発想に至りました。
N桁の数字を、３で何回割り切れるか判別するとします。
１．各位の数の和を、S1とする。
S1が３の倍数なら、３で１回割り切れる。
S1が９の倍数なら、３で２回割り切れる。
２回割り切れる場合は、S1を９で割った商を"繰り上げ"て次の判定へ。
２．先頭の桁から順に、{N-1，N-2，…，1，0}を掛けて合計し、"繰り上げ"された数も足して
S2とする。
S2が３の倍数なら、３で３回割り切れる。
S2が９の倍数なら、３で４回割り切れる。
４回割り切れる場合は、S2を９で割った商を"繰り上げ"て次の判定へ。
３．先頭の桁から順に{N-2番目の三角数，N-3番目の三角数，…，1，0，0}をかけて合計し、
"繰り上げ"された数も足してS3とする。
S3が３の倍数なら、３で５回割り切れる。
S3が９の倍数なら、３で６回割り切れる。
６回割り切れる場合は、S3を９で割った商を"繰り上げ"て次の判定へ。
４．先頭の桁から順に{N-3番目の三角錐数，N-4番目の三角錐数，…，1，0，0，0}をかけて
合計し、"繰り上げ"された数も足してS4とする。
S4が３の倍数なら、３で７回割り切れる。
S4が９の倍数なら、３で８回割り切れる。
（次は四次元立体の何かになるのでこの辺までで……）
例: 104841 （Ｎ=6）の場合、S1=1+0+4+8+4+1 = 18 = 9×2 で、
1×5+0×4+4×3+8×2+4×1+1×0 +2 = 39 = 3×13
よって、104841は、３で３回割り切れる。実際、104841=33×11×353
例: 1012581 （Ｎ=7）の場合、S1=1+0+1+2+5+8+1 = 18 = 9×2 で、
1×6+0×5+1×4+2×3+5×2+8×1+1×0 +2 = 36 = 9×4
1×15+0×10+1×6+2×3+5×1+8×0+1×0 +4 = 36 = 9×4
1×20+0×10+1×4+2×1+5×0+8×0+1×0 +4 = 30 = 3×10
よって、1012581は、３で７回割り切れる。実際、1012581=37×463
※ 発想だけあって証明はできていません。三角数や三角錐数がどうして関連するのかさっ
ぱりなので証明の方向性すらよくわかりません。でも、実際にいくつかやってみると、なんか
うまくいくっぽいんですが、これ、本当に正確に判定できてるんでしょうか？それとも偶然う
まくいく数字を引き当て続けただけ？
りらひいさんからのコメントです。（平成２７年１１月１６日付け）
とりあえず、具体例をひも解いてみた。
104841の場合
104841
= 1*100000+0*10000+4*1000+8*100+4*10+1
= (1*99999+0*9999+4*999+8*99+4*9)+(1+0+4+8+4+1)
= 9*(1*11111+0*1111+4*111+8*11+4*1)+(1+0+4+8+4+1)
= 9*(1*(9*1234+5)+0*(9*123+4)+4*(9*12+3)+8*(9*1+2)+4*(9*0+1))+(1+0+4+8+4+1)
= 9*9*(1*1234+0*123+4*12+8*1)+9*(1*5+0*4+4*3+8*2+4*1)+(1+0+4+8+4+1)
今、1+0+4+8+4+1 = 18 = 9*2 であるので、
104841 = 9*9*(1*1234+0*123+4*12+8*1)+9*{(1*5+0*4+4*3+8*2+4*1)+2}
よって、
(1*5+0*4+4*3+8*2+4*1)+2が3の倍数であれば104841は9*3の倍数であり、
(1*5+0*4+4*3+8*2+4*1)+2が9の倍数であれば104841は9*9の倍数である。
計算してみると、(1*5+0*4+4*3+8*2+4*1)+2 = 39 = 3*13 であるので、
104841 = 9*9*(1*1234+0*123+4*12+8*1)+9*3*13
= 9*3*{3*(1*1234+0*123+4*12+8*1)+13}
となって、3で3回割り切れる。
1012581の場合
1012581
= 1*1000000+0*100000+1*10000+2*1000+5*100+8*10+1
= (1*999999+0*99999+1*9999+2*999+5*99+8*9)+(1+0+1+2+5+8+1)
= 9*(1*111111+0*11111+1*1111+2*111+5*11+8*1)+(1+0+1+2+5+8+1)
ここで、1+0+1+2+5+8+1 = 18 = 9*2 であるので、
1012581
= 9*{(1*111111+0*11111+1*1111+2*111+5*11+8*1)+2}
= 9*{(1*(9*12345+6)+0*(9*1234+5)+1*(9*123+4)+2*(9*12+3)+5*(9*1+2)+8*(9*0+1))+2}
= 9*{9*(1*12345+0*1234+1*123+2*12+5*1)+(1*6+0*5+1*4+2*3+5*2+8*1)+2}
となる。また、(1*6+0*5+1*4+2*3+5*2+8*1)+2 = 36 = 9*4 なので、
1012581
= 9*9*{(1*12345+0*1234+1*123+2*12+5*1)+4}
= 9*9*{(1*(9*1370+15)+0*(9*136+10)+1*(9*13+6)+2*(9*1+3)+5*(9*0+1))+4}
= 9*9*{9*(1*1370+0*136+1*13+2*1)+(1*15+0*10+1*6+2*3+5*1)+4}
となり、さらに、(1*15+0*10+1*6+2*3+5*1)+4 = 36 = 9*4 であるので、
1012581
= 9*9*9*{(1*1370+0*136+1*13+2*1)+4}
= 9*9*9*{(1*(9*150+20)+0*(9*14+10)+1*(9*1+4)+2*(9*0+1))+4}
= 9*9*9*{9*(1*150+0*14+1*1)+(1*20+0*10+1*4+2*1)+4}
となって、さらにさらに、(1*20+0*10+1*4+2*1)+4 = 30 = 3*10 なので、
1012581
= 9*9*9*{9*(1*150+0*14+1*1)+3*10}
= 9*9*9*3*{3*(1*150+0*14+1*1)+10}
となることがわかり、3で7回割り切れる。
ここまでやってみると、あとは、9で割った割り算の結果が三角数や三角錐数と関連してい
ることが言えれば、大筋の流れは作れそうかな？
10^N = 1 + 9*(Σi=0〜N-110^i)
ここで、
Σi=0〜N-110^i
= Σi=0〜N-1{1+9*(Σj=0〜i-110^j)}
= Σi=0〜N-11 + 9*(Σi=0〜N-1Σj=0〜i-110^j)
Σi=0〜N-1Σj=0〜i-110^j
= Σi=0〜N-1Σj=0〜i-1{1+9*(Σk=0〜j-110^k)}
= Σi=0〜N-1Σj=0〜i-11 + 9*(Σi=0〜N-1Σj=0〜i-1{Σk=0〜j-110^k)
Σi=0〜N-1Σj=0〜i-1Σk=0〜j-110^k
= Σi=0〜N-1Σj=0〜i-1Σk=0〜j-1{1+9*(Σl=0〜k-110^l)}
= Σi=0〜N-1Σj=0〜i-1Σk=0〜j-11 + 9*(Σi=0〜N-1Σj=0〜i-1Σk=0〜j-1Σl=0〜k-110^l)
さて、ここで、
1 は、 1 であり、
Σi=0〜N-11 は、 1 の和で、自然数であり、
Σi=0〜N-1Σj=0〜i-11 は、自然数 の和で、三角数であり、
Σi=0〜N-1Σj=0〜i-1Σk=0〜j-11 は、三角数 の和で、三角錐数 である。
（続く）
こんな感じのことをうまいことまとめて書けば示すことができるのではないでしょうか？
ぱぱーっと書いただけなのでどこか違っていたらごめんなさい。
ＧＡＩ さんからのコメントです。（平成２７年１１月１６日付け）
次も確かめたくなったので、次の３角錐４次元立体（計算上Binomial[n+3,4] {n=4,3,2,1,0,0,0,0}
で）も利用してみました。
例: 3^10*197=11632653 の場合
1 +1 +6 +3 +2 +6 +5 +3 = 27 = 9×3
1×7+ 1×6+ 6×5+ 3×4+2×3+6×2+5×1+3×0 +3 = 81 = 9×9
1×21+1×15+6×10+3×6+2×3+6×1+5×0+3×0 +9 = 135 = 9×15
1×35+1×20+6×10+3×4+2×1+6×0+5×0+3×0 +15 = 144 = 9×16
1×35+1×15+6×5+ 3×1+2×0+6×0+5×0+3×0 +16 = 99 = 9×11
よって、11632653は3で10回割り切れる。
色々な数字で確認したんですが、このアルゴリズムで上手くいきそうですね。上の例で２段
目で81=3^4から直接4*2+2（一段目利用）=10（回）とは行かないですかね？これで判定でき
た他のものがザッと
{2184813,2539107,3129597,3601989,4901067,6082047,11632653,17301357,30055941}
のようなものがありました。
DD++さんからのコメントです。（平成２７年１１月１６日付け）
81=3^4から直接4*2+2（一段目利用）=10（回）と行かない？
4、2、2 は、それぞれどこの数を拾ったと思えばよいでしょう？
ＧＡＩ さんからのコメントです。（平成２７年１１月１７日付け）
２段目が81で3^4となっているので4を拾い、2段目であるので、これにかける2、１段目はそ
もそも9で割れていたので3^2の2ということで、元の数は3の因数を4*2+2個含むと見なしまし
た。
DD++さんからのコメントです。（平成２７年１１月１７日付け）
99711 はどうなるのでしょう？
9+9+7+1+1 = 27 = 9×3 、9×4+9×3+7×2+1×1+1×0 +3 = 81
ですが、99711 = 3^4 × 1231 です。
なお、9×6+9×3+7×1+1×0+1×0 +9 = 97 なので、こっちの判定では、5回目は割れな
いとちゃんと出ます。
りらひいさんからのコメントです。（平成２７年１１月１７日付け）
まとめてみました。
事前確認事項：二項係数をC[n,k]と書くとき、k>nならばC[n,k]=0である。
総和に関して、A＞Bならば、Σ[i=A〜B]f(i)=0である。
(一段階目) n,kを0以上の整数とする。
a[n,k]を次のように定義する。
k=0のとき、a[n,0] = 1
k=1のとき、a[n,1] = Σ[i[1]=0〜n-1]1
k=2のとき、a[n,2] = Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]1
…
k=kのとき、a[n,k] = Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1]1
このとき、a[n,k] = C[n,k] となることを数学的帰納法で示す。
(ア) k=0 のとき、a[n,0] = 1 = C[n,0] より、成り立つ。
(イ) k=l のときに、a[n,l] = C[n,l] が成り立っているとする。 k=l+1のとき、
a[n,l+1] = Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[l+1]=0〜i[l]-1]1
= Σ[i[1]=0〜n-1]a[i[1],l] (∵a[n,k]の定義)
= Σ[i[1]=0〜n-1]C[i[1],l] (∵帰納法の仮定)
= Σ[i[1]=l〜n-1]C[i[1],l] (∵i[1]<l ⇒ C[i[1],l]=0)
= Σ[j=0〜n-l-1]C[l+j,l] (j=i[1]-lとおきかえ)
= C[n,l+1] (∵二項係数の性質)
(ア),(イ)より、a[n,k] = C[n,k] が成り立つ。
(二段階目) bを2以上の整数とする。
d[n,k]を次のように定義する。
k=0のとき、d[n,0] = b^n
k=1のとき、d[n,1] = Σ[i[1]=0〜n-1]b^i[1]
k=2のとき、d[n,2] = Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]b^i[2]
…
k=kのとき、d[n,k] = Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1]b^i[k]
このとき、b^h = 1+(b-1)(Σ[i=0〜h-1]b^i) が成り立つ(∵右辺を展開すれば明らか)ことに
注意すると、
d[n,k]
= Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1]b^i[k]
= Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1](1+(b-1)(Σ[i[k+1]=0〜i[k]-1]b^i[k+1]))
= (Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1]1)
+ (b-1)(Σ[i[1]=0〜n-1]Σ[i[2]=0〜i[1]-1]…Σ[i[k]=0〜i[k-1]-1]Σ[i[k+1]=0〜i[k]-1]b^i[k+1])
= a[n,k] + (b-1)d[n,k+1]
= C[n,k] + (b-1)d[n,k+1]
が成り立つ。
(三段階目) ある整数Mが、m[n] (n=0,1,…,N)を整数として、M = Σ[n=0〜N]m[n]b^n と
なっているとする。
M = Σ[n=0〜N]m[n]d[n,0]
= Σ[n=0〜N]m[n](C[n,0]+(b-1)d[n,1])
= (Σ[n=0〜N]m[n]C[n,0]) + (b-1)(Σ[n=0〜N]m[n]d[n,1])
p[0] = Σ[n=0〜N]m[n]C[n,0] とおく。
もし p[0] が b-1 の倍数ならば、p[0] = (b-1)t[0] とおくことにより、
M = p[0] + (b-1)(Σ[n=0〜N]m[n]d[n,1])
= (b-1)(t[0] + (Σ[n=0〜N]m[n]d[n,1]))
となるため、Mはb-1で割り切る。
M = (b-1)(t[0]+Σ[n=0〜N]m[n]d[n,1])
= (b-1)(t[0]+Σ[n=0〜N]m[n](C[n,1]+(b-1)d[n,2]))
= (b-1)(t[0] + (Σ[n=0〜N]m[n]C[n,1]) + (b-1)(Σ[n=0〜N]m[n]d[n,2]))
p[1] = t[0] + (Σ[n=0〜N]m[n]C[n,1]) とおく。
もし p[1] が b-1 の倍数ならば、p[1] = (b-1)t[1] とおくことにより、
M = (b-1)(p[1] + (b-1)(Σ[n=0〜N]m[n]d[n,2])
= (b-1)^2(t[1] + (Σ[n=0〜N]m[n]d[n,2]))
となるため、Mは(b-1)^2で割り切れる。
以下同様にして、
p[k] = t[k-1] + (Σ[n=0〜N]m[n]C[n,k]) とおき、p[k] が b-1 の倍数ならば、p[k] = (b-1)t[k]
とおく操作を続けると、M = (b-1)^(k+1)(t[k] + (Σ[n=0〜N]m[n]d[n,k+1])) となって、
Mは(b-1)^(k+1)で割り切れることがわかる。
(四段階目) Mを十進表記でみているとすると、基数b=10を代入して10-1=3^2に注意すれば、
DD++さんの提示したものになる。
＃急いでいて、見直してないので、間違いがあっても許してください・・・。また時間のある時
に見直しをしておきます。
DD++さんからのコメントです。（平成２７年１１月２１日付け）
なるほど、時間かかりましたが、ようやく納得できました。つまり、10=9+1 として十進の位取
りを二項展開して九進モドキ（各位が十以上になってもよい）に変換し、繰り上げしながら下
の桁から順に判定していってるのに相当していたわけですね。なるほど、なるほど、そりゃこ
れで完全に判定できるのも道理です。
りらひいさんからのコメントです。（平成２７年１１月２１日付け）
なるほど、そういう解釈ができるんですね！わたしは、具体例を計算してみて、そこで見え
た流れをそのまま書いていっただけなので、そこにどんな意味があるのかをほとんど考えて
いませんでした。DD++さんの見方ならもっと簡単に書けそうですね。
…というわけで書いてみました。帰納法なんて使わないし、なんとわかりやすいことか！！
m[n] (n=0,1,…,N)を整数、bを２以上の整数とする。
M = Σ[n=0〜N]m[n]b^n
= Σ[n=0〜N]m[n](1+(b-1))^n (b=1+(b-1)と分割)
= Σ[n=0〜N]Σ[i=0〜n]m[n]C[n,i](b-1)^i (∵二項展開)
= Σ[n=0〜N]Σ[i=0〜N]m[n]C[n,i](b-1)^i (∵i>n ⇒ C[n,i]=0)
= Σ[i=0〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^i (有限和の入れ替え)
p[0]=Σ[n=0〜N]m[n]C[n,0] が b-1 の倍数なら、p[0]=(b-1)t[0] とおき、
M = p[0] + Σ[i=1〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^i
= (b-1)*(t[0] + Σ[i=1〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^(i-1))
p[1]=t[0]+Σ[n=0〜N]m[n]C[n,1] が b-1 の倍数なら、p[1]=(b-1)t[1] とおき、
M = (b-1)*(p[1] + Σ[i=2〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^(i-1))
= (b-1)^2*(t[1] + Σ[i=2〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^(i-2))
以下同様にして、
p[k]=t[k-1]+Σ[n=0〜N]m[n]C[n,k] が b-1 の倍数なら、p[k]=(b-1)t[k] とおき、
M = (b-1)^k*(p[k] + Σ[i=k+1〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^(i-k))
= (b-1)^(k+1)*(t[k] + Σ[i=k+1〜N]Σ[n=0〜N]m[n]C[n,i](b-1)^(i-k-1))
となって、Mは(b-1)^(k+1)で割り切れる。
