Minden 10^8-nál kisebb pozitív egész szám felírható legfeljebb x db Fibonacci-szám összegeként. X=?

Amúgy rosszul számoltam, egy tízessel arrébb ment a számításom, így a válasz 19 lesz.. :-)

A tétel azt mondja, hogy minden szám felírható kvázi Fibonacci számrendszerben. Ugye itt egy olyan számrendszert kell elképzelni, ahol az egyes helyértékek: … 34, 21, 13, 8, 5, 3, 2, 1.

A tétel szerint minden természetes szám úgy felírható egy ilyen számrendszerben, hogy csak két számjegyet kell használni, nullát vagy egyest. Sőt úgy felírható, hogy nem állhat két egyes egymás mellett.

Pl.:

1 → 1 (=1)

2 → 10 (=2)

3 → 100 (=3)

4 → 101 (=3+1)

5 → 1000 (=5)

6 → 1001 (=5+1)

7 → 1010 (=5+2)

8 → 10000 (=8)

9 → 10001 (=8+1)

10 → 10010 (=8+2)

11 → 10100 (=8+3)

12 → 10101 (=8+3+1)

13 → 100000 (=13)

14 → 100001 (=13+1)

15 → 100010 (=13+2)

16 → 100100 (=13+3)

17 → 100101 (=13+3+1)

18 → 101000 (=13+5)

19 → 101001 (=13+5+1)

20 → 101010 (=13+5+2)

…

A 40. Fibonacci szám: 102 334 155 > 10^8. Tehát a legnagyobb felhasználható Fibonacci szám a 39. szám lesz. A legkisebb Fibonacci szám, amit használni lehet, az a 2. Fibonacci szám, a kettes. Összesen tehát maximum 38 számjegy elegendő egy 10^8-nál kisebb szám felírásához. Mivel egyesek nem állhatnak egymást mellett, így ez maximum 19 darab egyest jelent ebben a felírásban, azaz maximum 19 Fibonacci-szám összegeként fel lehet írni minden 10^8-nál kisebb számot. Ez a felső becslés.

Innen meg jó ötlet megnézni, hogy mit kapsz, ha felírod a 0101…0101 (19 nulla és 19 egyes) számot. Ez a szám: 63 245 985. Ezt 19-nél kevesebb Fibonacci-szám összegeként nem lehet felírni.

A válasz tehát pontosan 19.