この「連続しない」の条件を外せば、例えば、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 の場合のZeckendorf 的分解型と他の連続も許す分解型の実例を示して
ほしい。
もちろん、プログラム的に作業されても構いませんが、計算にかかった時間を示して下さ
い。
らすかるさんからのコメントです。（令和４年７月２６日付け）
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か所だけ変更
や２か所同時に変更するなど、いろいろな枝分かれが起こっていってしまい、どの様に組ん
で行っていいのか分からなくなりました。
従って、フィボナッチ数の個数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]へ変更させる作業をその都度行い、新たに
それらを集めた集合を作っていくことを繰り返してみました。
２か所以上あっても、同時に変化させることはしなくてそれぞれの変化を集めることにしま
した。ですから、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]]
２回目は、この集合に対し、同様な操作をそれぞれに行っていき、これの集合に新たに追
加していきました。但し、同じものが重なった場合はそれはその重なりを解消する操作を入
れておきます。
これを数回繰り返しておけば、集まってくる集合の個数が一定の数に収斂していき、それ
以上は増えも減りもしなくなりました。
これを見つけたら、その集合に対しフィボナッチ数を割り振って構成できました。但し、最
後の成分が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さんの方法の方が速いでしょうね。
以下、工事中！
