パスカルの三角形を塗りわけてフラクタル図形を作ろうとしてるのですが,思わぬところで難問にぶつかってしまいました。
正の整数 N について
N! = p * 2^k
と表す。ここで p は奇数,k は整数 である。k を求めるにはどうしたらよいか。 たとえば N = 5 であれば,
4! = 120 = 15 * 2^3, → k = 3
というふうに。これを任意の N について簡単に求めたい。
で,考え始めたけど分からんのです。もうひとつ砕いて考えると,
任意の正の整数 i について,i を素因数分解したら 2 は何個現れるか
という問題に帰着します。ノートに書き並べていくと,規則性があるけれども,単純じゃないんですね。どうもこれは一筋縄ではいかないような。うーむ
そうですね。関数というわけにはいかないのでしょう。元々の階乗の中に2が因数として幾つ含まれるかという問題は、Nが偶数の場合だけを考えれば良いわけですよね。プログラムは書けても、定式化は無理ですね。きっと。
因みに規則性って、
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,8, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,9,...
ですよね。これぞフラクタル!?ですかな。 そそ,そうなんですよ!
プログラミングでは「関数」はいろいろな手続きを含めてるんだけど,それはともかくとして,毎回描画のたびに関数呼び出ししていたら遅くなりそう。最初に計算して一気にテーブルを作成しておくのがよさそうですねえ。
しかし,それにしても,しらみつぶしじゃないうまいアルゴリズムないかなあ。
やはり、家の環境では書き込めませんねえ。タイムラグがありますが、フラクタルな構造はこんな具合ですね。rubyだと簡単に実装できますよ。
0 最初に0を1つ準備 1 全部に1を足す 0 1 0 間に0を埋める 1 2 1 全部に1を足す 0 1 0 2 0 1 0 間に0を埋める 1 2 1 3 1 2 1 全部に1を足す 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 間に1を埋める、、、
さて、このアルゴリズムで(虱潰しですが)作れます。ドラゴンカーブ?なんかと同じですね。、、、ってなんだか断言しただけで「検証」というか「論証」というか「何故かの説明」はありません。どなたか簡単に説明を付けてください。
ってそうかあ、2進数にして、一の位?から連続する0の数を数えれば因数としての2の数が分かるわけですよね。ふむふむ。
5!(10進)=101×100×11×10×1(2進) だから、3 ^^ ^
ってそうかあ、そもそもパスカルの三角形を色で塗り分けて「フラクタル図形」なんだから、構造的に仕方ないのですよね。
2進法表記からもっていくのは高速にできる可能性があると思ったですが,結局2で何回割れるかを数えるわけでちょっと面白くない。で,効率のよいアルゴリズムを考えることにしました。
という流れです。つまり 6! に含まれる 2 のべき数を数えるには,6!! について考えればよい。すると 6!! = 2^3 × 3! と砕くことができるので,再帰的に呼び出す方法が使えるというわけです。Ruby で実装してみたら簡単でした。このアルゴリズムだと消費されるスタックも浅いので,n = 2000 くらいは余裕で実行してくれます。
#! /usr/local/bin/ruby def powerof2inFactorial(n) if n == 1 return 0 elsif n == 2 return 1 end if n % 2 == 1 n -= 1 end n /= 2 return n + powerof2inFactorial(n) end ######################################### # n = 2000 まで計算させてみる。 for i in 1 .. 1000 printf("%3d -- %3d\n",i*2,powerof2inFactorial(i*2)) end
それにしても,こういうところにもフラクタルな構造が出現するものですね。おもしろい!
そうですね。それだけ「フラクタル」が自然な概念なんだってことでしょうね。ところで、このアルゴリズムって
6!=6×5×4×3×2×1 6 4 2 3×2×1 2 1
ってことですよね。階乗に含まれる因数2の個数?ってことだから、まず問題になるのは偶数の個数。偶数だけ取り出して数えたら(n<-n/2)、その分差っぴいて2で割る。すると、半分の長さの階乗が現れる。で、また同じことを考えるという再帰なんですね。うまくできていますね。先に私が書いたものの逆なんですね。