階乗のなぞの変更点

追加された行はこの色です。
削除された行はこの色です。
階乗のなぞへ行く。
階乗のなぞの差分を削除
 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){それにしても，こういうところにもフラクタルな構造が出現するものですね。おもしろい！}
 
 COLOR(#fe891c){そうですね。それだけ「フラクタル」が自然な概念なんだってことでしょうね。ところで、このアルゴリズムって}
 
  6!=6×5×4×3×2×1
     6     4     2
     3×2×1
     2
     1
 
 COLOR(#fe891c){ってことですよね。階乗に含まれる因数2の個数？ってことだから、まず問題になるのは偶数の個数。偶数だけ取り出して数えたら（n<-n/2）、その分差っぴいて2で割る。すると、半分の長さの階乗が現れる。で、また同じことを考えるという再帰なんですね。うまくできていますね。先に私が書いたものの逆なんですね。}
 
 ----
 それにしても、此処を何人の人が見ているか知らないけど、二乗階乗ってどれぐらいの人が知っているのでしょう？
 COLOR(#fe891c){それにしても、此処を何人の人が見ているか知らないけど、二乗階乗ってどれぐらいの人が知っているのでしょう？と言いつつ、自身もあまり話したことはなかったりするのですが。}
  二重階乗:これは、自然数 n に対し、
  n が奇数なら 1 から n までの奇数の総乗、
  n が偶数なら 2 から n までの偶数の総乗である。
  これを n!! と書く。
階乗のなぞ の変更点

階乗のなぞの変更点
