パスカルの三角形を塗りわけてフラクタル図形を作ろうとしてるのですが,思わぬところで難問にぶつかってしまいました。
正の整数 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,...
ですよね。これぞフラクタル!?ですかな。
プログラミングでは「関数」はいろいろな手続きを含めてるんだけど,それはともかくとして,毎回描画のたびに関数呼び出ししていたら遅くなりそう。最初に計算して一気にテーブルを作成しておくのがよさそうですねえ。
しかし,それにしても,しらみつぶしじゃないうまいアルゴリズムないかなあ。