COLOR(#006789){パスカルの三角形を塗りわけてフラクタル図形を作ろうとしてるのですが，思わぬところで難問にぶつかってしまいました。}

正の整数 N について

CENTER: N! = p * 2^k

と表す。ここで p は奇数，k は整数 である。k を求めるにはどうしたらよいか。
たとえば N = 5 であれば，

CENTER: 4! = 120 = 15 * 2^3, → k = 3

というふうに。これを任意の N について簡単に求めたい。

COLOR(#006789){で，考え始めたけど分からんのです。もうひとつ砕いて考えると，}

任意の正の整数 i について，i を素因数分解したら 2 は何個現れるか

COLOR(#006789){という問題に帰着します。ノートに書き並べていくと，規則性があるけれども，単純じゃないんですね。どうもこれは一筋縄ではいかないような。うーむ}

COLOR(#fe891c){そうですね。関数というわけにはいかないのでしょう。元々の階乗の中に2が因数として幾つ含まれるかという問題は、Ｎが偶数の場合だけを考えれば良いわけですよね。プログラムは書けても、定式化は無理ですね。きっと。}

COLOR(#fe891c){因みに規則性って、}

 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,...

COLOR(#fe891c){ですよね。これぞフラクタル！？ですかな。}
COLOR(#006789){''そそ，そうなんですよ！''}

COLOR(#006789){プログラミングでは「関数」はいろいろな手続きを含めてるんだけど，それはともかくとして，毎回描画のたびに関数呼び出ししていたら遅くなりそう。最初に計算して一気にテーブルを作成しておくのがよさそうですねえ。}

COLOR(#006789){しかし，それにしても，しらみつぶしじゃないうまいアルゴリズムないかなあ。}

COLOR(#fe891c){やはり、家の環境では書き込めませんねえ。タイムラグがありますが、フラクタルな構造はこんな具合ですね。rubyだと簡単に実装できますよ。}

 0　　最初に０を１つ準備
 1　　全部に１を足す
 0 1 0　　間に０を埋める
 1 2 1　　全部に１を足す
 0 1 0 2 0 1 0　　間に０を埋める
 1 2 1 3 1 2 1　　全部に１を足す
 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0　間に１を埋める、、、

COLOR(#fe891c){さて、このアルゴリズムで（虱潰しですが）作れます。ドラゴンカーブ？なんかと同じですね。、、、ってなんだか断言しただけで「検証」というか「論証」というか「何故かの説明」はありません。どなたか簡単に説明を付けてください。}

COLOR(#fe891c){ってそうかあ、2進数にして、一の位？から連続する０の数を数えれば因数としての２の数が分かるわけですよね。ふむふむ。}

 5!(10進)=101×100×11×10×1(2進)　だから、3
                ^^       ^

COLOR(#fe891c){ってそうかあ、そもそもパスカルの三角形を色で塗り分けて「フラクタル図形」なんだから、構造的に仕方ないのですよね。}

COLOR(#006789){2進法表記からもっていくのは高速にできる可能性があると思ったですが，結局２で何回割れるかを数えるわけでちょっと面白くない。で，効率のよいアルゴリズムを考えることにしました。}

+ hoge(n)
+ n が奇数なら n  <-  n-1 とする
+ n は偶数だから（上の結果として）， n <- n/2 とする
+ n + hoge(n) を計算してくれ
+ n = 1,2 のときにはそれぞれ 0, 1 を返す

COLOR(#006789){という流れです。つまり 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
----
COLOR(#006789){それにしても，こういうところにもフラクタルな構造が出現するものですね。おもしろい！}
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS