フィボナッチ数の役割
自然数nが積においては素数が大切な役割を担うのに対し
和においてはフィボナッチ数{1,2,3,5,8,13,21,34,55,･･･}
がその任を担う位なことを教えてくれるのが
Zeckenrorf's Theorem(ゼッケンドリフの定理）で
”あらゆる自然数nは連続しないフィボナッチ数の和で必ず構成可能で
その表現はただ一通り”
というものに出会った。
確かに100までの自然数は
1 = 1
2 = 2
3 = 3
4 = 1 + 3
5 = 5
6 = 1 + 5
7 = 2 + 5
8 = 8
9 = 1 + 8
10 = 2 + 8
11 = 3 + 8
12 = 1 + 3 + 8
13 = 13
14 = 1 + 13
15 = 2 + 13
16 = 3 + 13
17 = 1 + 3 + 13
18 = 5 + 13
19 = 1 + 5 + 13
20 = 2 + 5 + 13
21 = 21
22 = 1 + 21
23 = 2 + 21
24 = 3 + 21
25 = 1 + 3 + 21
26 = 5 + 21
27 = 1 + 5 + 21
28 = 2 + 5 + 21
29 = 8 + 21
30 = 1 + 8 + 21
31 = 2 + 8 + 21
32 = 3 + 8 + 21
33 = 1 + 3 + 8 + 21
34 = 34
35 = 1 + 34
36 = 2 + 34
37 = 3 + 34
38 = 1 + 3 + 34
39 = 5 + 34
40 = 1 + 5 + 34
41 = 2 + 5 + 34
42 = 8 + 34
43 = 1 + 8 + 34
44 = 2 + 8 + 34
45 = 3 + 8 + 34
46 = 1 + 3 + 8 + 34
47 = 13 + 34
48 = 1 + 13 + 34
49 = 2 + 13 + 34
50 = 3 + 13 + 34
51 = 1 + 3 + 13 + 34
52 = 5 + 13 + 34
53 = 1 + 5 + 13 + 34
54 = 2 + 5 + 13 + 34
55 = 55
56 = 1 + 55
57 = 2 + 55
58 = 3 + 55
59 = 1 + 3 + 55
60 = 5 + 55
61 = 1 + 5 + 55
62 = 2 + 5 + 55
63 = 8 + 55
64 = 1 + 8 + 55
65 = 2 + 8 + 55
66 = 3 + 8 + 55
67 = 1 + 3 + 8 + 55
68 = 13 + 55
69 = 1 + 13 + 55
70 = 2 + 13 + 55
71 = 3 + 13 + 55
72 = 1 + 3 + 13 + 55
73 = 5 + 13 + 55
74 = 1 + 5 + 13 + 55
75 = 2 + 5 + 13 + 55
76 = 21 + 55
77 = 1 + 21 + 55
78 = 2 + 21 + 55
79 = 3 + 21 + 55
80 = 1 + 3 + 21 + 55
81 = 5 + 21 + 55
82 = 1 + 5 + 21 + 55
83 = 2 + 5 + 21 + 55
84 = 8 + 21 + 55
85 = 1 + 8 + 21 + 55
86 = 2 + 8 + 21 + 55
87 = 3 + 8 + 21 + 55
88 = 1 + 3 + 8 + 21 + 55
89 = 89
90 = 1 + 89
91 = 2 + 89
92 = 3 + 89
93 = 1 + 3 + 89
94 = 5 + 89
95 = 1 + 5 + 89
96 = 2 + 5 + 89
97 = 8 + 89
98 = 1 + 8 + 89
99 = 2 + 8 + 89
100 = 3 + 8 + 89
･･･････
といかにも素因数分解される様にしてフィボナッチ数分解されていく。
この「連続しない」の条件を外せば、例えばn=100では
100=1+2+8+89
=3+8+34+55
=1+2+3+5+89
=1+2+8+34+55
=3+8+13+21+55
=1+2+3+5+34+55
=1+2+8+13+21+55
=1+2+3+5+13+21+55
とそれ以外にも8個、計9通りの構成が可能になる。
そこで
n=7777 の場合のZeckenrorf的分解型と
他の連続も許す分解型の実例を示してほしい。
もちろんプログラム的に作業されても構いませんが、計算にかかった時間を示してほしい。
7777
=1+3+21+987+6765 (Zeckendorf)
=1+3+8+13+987+6765
=1+3+21+377+610+6765
=1+3+8+13+377+610+6765
=1+3+21+144+233+610+6765
=1+3+8+13+144+233+610+6765
=1+3+21+55+89+233+610+6765
=1+3+8+13+55+89+233+610+6765
=1+3+8+13+21+34+89+233+610+6765
=1+3+21+987+2584+4181
=1+3+8+13+987+2584+4181
=1+3+21+377+610+2584+4181
=1+3+8+13+377+610+2584+4181
=1+3+21+144+233+610+2584+4181
=1+3+8+13+144+233+610+2584+4181
=1+3+21+55+89+233+610+2584+4181
=1+3+8+13+55+89+233+610+2584+4181
=1+3+8+13+21+34+89+233+610+2584+4181
=1+3+21+377+610+987+1597+4181
=1+3+8+13+377+610+987+1597+4181
=1+3+21+144+233+610+987+1597+4181
=1+3+8+13+144+233+610+987+1597+4181
=1+3+21+55+89+233+610+987+1597+4181
=1+3+8+13+55+89+233+610+987+1597+4181
=1+3+8+13+21+34+89+233+610+987+1597+4181
計25個
実行時間:約0.01秒
Zeckendorfの表現を利用すると、その他の表し方を含む総数の個数を求める計算方法は色々な資料を読む中で分かって計算上直ぐに
求められる手段はわかりました。
ところがその実例はとなると、何とかゼッケンドルフのフィボナッチ数が使われる部分を1、使っていないものは0で表示していくとき
（7777=>[1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1]となる。）
本での説明ではこの列での1,0,0の部分を0,1,1へ変更すれば良いとの説明を読むが、桁がもっと短いものなら何とかそれで求まると
体験は出来るんですが、これを自動でプログラムしようとすると例えばこの例のように1,0,0 の部分が何通りもある場合、1か所だけ変更
や2か所同時に変更するなど、いろいろな枝分かれが起こっていってしまい、どの様に組んで行っていいのか分からなくなりました。
従って、フィボナッチ数の個数19から5,6,7,8,9,10,11,12個取り出す各組合せを和が7777になるものをチェックするという手法しかやれず
その計算時間は何と半日以上という,0.01秒が夢のまた夢の状態でした。
そこをらすかるさんはプログラム的にどのような経路で出力できたるのか粗筋的でも良いので教えて下さい。
大きい順にフィボナッチ数を使うかどうかで分岐します。
7777以下の最大のフィボナッチ数は6765
6765を使う場合と使わない場合で分岐
6765を使う場合はあと1012
1012以下の最大のフィボナッチ数は987
987を使う場合と使わない場合で分岐
987を使う場合はあと25
25以下の最大のフィボナッチ数は21
21を使う場合と使わない場合で分岐
21を使う場合はあと4
4以下の最大のフィボナッチ数は3
3を使う場合と使わない場合で分岐
3を使う場合はあと1→1+3+21+987+6765
3を使わない場合はそれ未満のフィボナッチ数の和が4未満なので不適
21を使わない場合は次のフィボナッチ数は13
（このとき残りのフィボナッチ数の和が25以上かどうかチェックするが、32なのでOK）
13を使う場合と使わない場合で分岐
13を使う場合はあと12
12以下の最大のフィボナッチ数は8
8を使う場合と使わない場合で分岐
8を使う場合はあと4 → 上と同じ処理なので省略
8を使わない場合はそれ未満のフィボナッチ数の和が12未満なので不適
13を使わない場合はそれ未満のフィボナッチ数の和が25未満なので不適
987を使わない場合は次のフィボナッチ数は610
・・・・
実際には再帰で処理しており、また「分岐」と書いているのは実際に分岐しているわけではなく
「どのフィボナッチ数を使うか」という19ビットのフラグに1を立てるかどうかです。
また「それ未満のフィボナッチ数の和」がただちに得られるように、
Σ[k=1～n]F(k)のテーブルを最初に作っています。
説明してもらったプログラムの分岐を再現しようとやっていたんですが
やはり難しく、もう単純に7777のZeckendorf表示
7777=[1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1]
をレバースさせた
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
において
[0,0,1]の部分があれば、そこを[1,1,0]へ変更させる作業をその都度
行い、新たにそれらを集めた集合を作っていくことを繰り返してみました。
2か所以上あっても、同時に変化させることはしなくてそれぞれの変化を
集めることにしました。
ですから、1回目の操作では次がその集合になります。
[[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
[ 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
[ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0]]
2回目はこの集合に対し同様な操作をそれぞれに行っていき、これの集合に
新たに追加していきました。
但し同じものが重なった場合はそれはその重なりを解消する操作を入れておきます。
これを数回繰り返しておけば、集まってくる集合の個数が一定の数に収斂していき
それ以上は増えも減りもしなくなりました。
これを見つけたら、その集合に対しフィボナッチ数を割り振って構成できました。
但し最後の成分が0があるものは、その0を取り除く作業をしておきます。
ここまでを自動でやらせるプログラムを準備したら、あっと言う間に全フィボナッチ数の
分解表現を並ばせることができました。
ちなみにn=123456でZeckendorf表示は、
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393]
までが使われるフィボナッチ数なので、最大なフィボナッチ数を採用していくと(貪欲法)
gp > 123456-121393 (25番目を使う)
%176 = 2063
gp > 2063-1597 (16番目を使う)
%177 = 466
gp > 466-377 (13番目を使う)
%178 = 89 (10番目を使う)
を使えばよいことになるので後は使われるフィボナッチ数を位取りで示せばよいので
123456=[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
これにプログラムを適応したら
1; 89 + 377 + 1597 + 121393
2; 89 + 377 + 1597 + 46368 + 75025
3; 89 + 377 + 1597 + 17711 + 28657 + 75025
4; 89 + 377 + 1597 + 6765 + 10946 + 28657 + 75025
5; 89 + 377 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
6; 89 + 377 + 610 + 987 + 121393
7; 89 + 377 + 610 + 987 + 46368 + 75025
8; 89 + 377 + 610 + 987 + 17711 + 28657 + 75025
9; 89 + 377 + 610 + 987 + 6765 + 10946 + 28657 + 75025
10; 89 + 377 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
11; 89 + 144 + 233 + 1597 + 121393
12; 89 + 144 + 233 + 1597 + 46368 + 75025
13; 89 + 144 + 233 + 1597 + 17711 + 28657 + 75025
14; 89 + 144 + 233 + 1597 + 6765 + 10946 + 28657 + 75025
15; 89 + 144 + 233 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
16; 89 + 144 + 233 + 610 + 987 + 121393
17; 89 + 144 + 233 + 610 + 987 + 46368 + 75025
18; 89 + 144 + 233 + 610 + 987 + 17711 + 28657 + 75025
19; 89 + 144 + 233 + 610 + 987 + 6765 + 10946 + 28657 + 75025
20; 89 + 144 + 233 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
21; 34 + 55 + 377 + 1597 + 121393
22; 34 + 55 + 377 + 1597 + 46368 + 75025
23; 34 + 55 + 377 + 1597 + 17711 + 28657 + 75025
24; 34 + 55 + 377 + 1597 + 6765 + 10946 + 28657 + 75025
25; 34 + 55 + 377 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
26; 34 + 55 + 377 + 610 + 987 + 121393
27; 34 + 55 + 377 + 610 + 987 + 46368 + 75025
28; 34 + 55 + 377 + 610 + 987 + 17711 + 28657 + 75025
29; 34 + 55 + 377 + 610 + 987 + 6765 + 10946 + 28657 + 75025
30; 34 + 55 + 377 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
31; 34 + 55 + 144 + 233 + 1597 + 121393
32; 34 + 55 + 144 + 233 + 1597 + 46368 + 75025
33; 34 + 55 + 144 + 233 + 1597 + 17711 + 28657 + 75025
34; 34 + 55 + 144 + 233 + 1597 + 6765 + 10946 + 28657 + 75025
35; 34 + 55 + 144 + 233 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
36; 34 + 55 + 144 + 233 + 610 + 987 + 121393
37; 34 + 55 + 144 + 233 + 610 + 987 + 46368 + 75025
38; 34 + 55 + 144 + 233 + 610 + 987 + 17711 + 28657 + 75025
39; 34 + 55 + 144 + 233 + 610 + 987 + 6765 + 10946 + 28657 + 75025
40; 34 + 55 + 144 + 233 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
41; 13 + 21 + 55 + 377 + 1597 + 121393
42; 13 + 21 + 55 + 377 + 1597 + 46368 + 75025
43; 13 + 21 + 55 + 377 + 1597 + 17711 + 28657 + 75025
44; 13 + 21 + 55 + 377 + 1597 + 6765 + 10946 + 28657 + 75025
45; 13 + 21 + 55 + 377 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
46; 13 + 21 + 55 + 377 + 610 + 987 + 121393
47; 13 + 21 + 55 + 377 + 610 + 987 + 46368 + 75025
48; 13 + 21 + 55 + 377 + 610 + 987 + 17711 + 28657 + 75025
49; 13 + 21 + 55 + 377 + 610 + 987 + 6765 + 10946 + 28657 + 75025
50; 13 + 21 + 55 + 377 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
51; 13 + 21 + 55 + 144 + 233 + 1597 + 121393
52; 13 + 21 + 55 + 144 + 233 + 1597 + 46368 + 75025
53; 13 + 21 + 55 + 144 + 233 + 1597 + 17711 + 28657 + 75025
54; 13 + 21 + 55 + 144 + 233 + 1597 + 6765 + 10946 + 28657 + 75025
55; 13 + 21 + 55 + 144 + 233 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
56; 13 + 21 + 55 + 144 + 233 + 610 + 987 + 121393
57; 13 + 21 + 55 + 144 + 233 + 610 + 987 + 46368 + 75025
58; 13 + 21 + 55 + 144 + 233 + 610 + 987 + 17711 + 28657 + 75025
59; 13 + 21 + 55 + 144 + 233 + 610 + 987 + 6765 + 10946 + 28657 + 75025
60; 13 + 21 + 55 + 144 + 233 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
61; 5 + 8 + 21 + 55 + 377 + 1597 + 121393
62; 5 + 8 + 21 + 55 + 377 + 1597 + 46368 + 75025
63; 5 + 8 + 21 + 55 + 377 + 1597 + 17711 + 28657 + 75025
64; 5 + 8 + 21 + 55 + 377 + 1597 + 6765 + 10946 + 28657 + 75025
65; 5 + 8 + 21 + 55 + 377 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
66; 5 + 8 + 21 + 55 + 377 + 610 + 987 + 121393
67; 5 + 8 + 21 + 55 + 377 + 610 + 987 + 46368 + 75025
68; 5 + 8 + 21 + 55 + 377 + 610 + 987 + 17711 + 28657 + 75025
69; 5 + 8 + 21 + 55 + 377 + 610 + 987 + 6765 + 10946 + 28657 + 75025
70; 5 + 8 + 21 + 55 + 377 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
71; 5 + 8 + 21 + 55 + 144 + 233 + 1597 + 121393
72; 5 + 8 + 21 + 55 + 144 + 233 + 1597 + 46368 + 75025
73; 5 + 8 + 21 + 55 + 144 + 233 + 1597 + 17711 + 28657 + 75025
74; 5 + 8 + 21 + 55 + 144 + 233 + 1597 + 6765 + 10946 + 28657 + 75025
75; 5 + 8 + 21 + 55 + 144 + 233 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
76; 5 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 121393
77; 5 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 46368 + 75025
78; 5 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 17711 + 28657 + 75025
79; 5 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 6765 + 10946 + 28657 + 75025
80; 5 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
81; 2 + 3 + 8 + 21 + 55 + 377 + 1597 + 121393
82; 2 + 3 + 8 + 21 + 55 + 377 + 1597 + 46368 + 75025
83; 2 + 3 + 8 + 21 + 55 + 377 + 1597 + 17711 + 28657 + 75025
84; 2 + 3 + 8 + 21 + 55 + 377 + 1597 + 6765 + 10946 + 28657 + 75025
85; 2 + 3 + 8 + 21 + 55 + 377 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
86; 2 + 3 + 8 + 21 + 55 + 377 + 610 + 987 + 121393
87; 2 + 3 + 8 + 21 + 55 + 377 + 610 + 987 + 46368 + 75025
88; 2 + 3 + 8 + 21 + 55 + 377 + 610 + 987 + 17711 + 28657 + 75025
89; 2 + 3 + 8 + 21 + 55 + 377 + 610 + 987 + 6765 + 10946 + 28657 + 75025
90; 2 + 3 + 8 + 21 + 55 + 377 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
91; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 1597 + 121393
92; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 1597 + 46368 + 75025
93; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 1597 + 17711 + 28657 + 75025
94; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 1597 + 6765 + 10946 + 28657 + 75025
95; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 1597 + 2584 + 4181 + 10946 + 28657 + 75025
96; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 121393
97; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 46368 + 75025
98; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 17711 + 28657 + 75025
99; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 6765 + 10946 + 28657 + 75025
100; 2 + 3 + 8 + 21 + 55 + 144 + 233 + 610 + 987 + 2584 + 4181 + 10946 + 28657 + 75025
と一気に全部のフィボナッチ数での和に分解してくれました。
（従来の方法では3日は計算に要する時間がかかりそうです。）
また全部で100個の方法があることは、次の計算方法で求まるそうです。
123456=[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
のZeckendorf表示から、これを0が続く数を10の指数に採用して
10^8*10^2*10^2*10^9
と表し
一般に10^dを次の2×2行列M(d)=[1 1]
[floor(d/2) ceil(d/2)] (floor;床関数、ceil;天井関数)
これにより上記の数は
M(8)*M(2)*M(2)*M(9)
= [1 1]*[1 1]^2*[1 1]
[4 4] [1 1] [4 5]
=[20 24]
[80 96]
最後にこの行列を[1 1],[1 0]~で挟み
[1 1]*[20 24]*[1]=[100]
[80 96] [0]
なる行列計算で処理できるという。（よくこんな方法を編み出すな～）
私の方法は何も考えずに和が目的の数になる組合せを探すだけなので、
おそらくZeckendorf表示から分解するGAIさんの方法の方が速いでしょうね。
