Reprezentace přirozených čísel ve Fibonacciho soustavě František Maňák, FJFI ČVUT, 2005
Úvod Jak víme, přirozená čísla lze vyjádřit různými způsoby. Nejčastěji k zápisu čísel používáme soustavu desítkovou, ale umíme používat i jiné soustavy – například dvojkovou a osmičkovou. V tomto článku se budeme zabývat rekurentně zadanými číselnými soustavami, zejména pak soustavou Fibonacciho.
Číselné soustavy ∞ Definice: Nechť Z = (Z j ) j =1 je ostře rostoucí posloupnost celých čísel taková, že Z0 = 1. Reprezentací přirozeného čísla n v soustavě Z rozumíme konečnou posloupnost celočíselných koeficientů
(a )
k
takovou, že n = ∑ a j Z j . Číslo n v soustavě Z zapisujeme jako
j k ≥ j ≥1
j =1
n = (a k a k −1 L a1 )Z a číslo k nazýváme délkou reprezentace.
Vidíme, že jedno přirozené číslo může mít více reprezentací v dané soustavě Z. Mezi všemi reprezentacemi daného n je nejvýznamnější tzv. hladový rozvoj, který získáme hladovým algoritmem. Na množině rozvojů přirozeného čísla n lze definovat tzv. lexikografické uspořádání a dá se ukázat, že hladový rozvoj je lexikograficky největší ze všech možných rozvojů přirozeného čísla n. Jeho důležitost spočívá zejména v tom, že je pro každé číslo n určen jednoznačně.
Fibonacciho číselná soustava Jedná se o číselnou soustavu, jejíž základ tvoří prvky Fibonacciho posloupnosti – tzv. Fibonacciho čísla. Ta jsou definována následovně: F0 = 1 , F1 = 1 a pro j ≥ 2 definujeme F j = F j −1 + F j − 2 . Existuje i přímý vzorec pro n-té Fibonacciho číslo: 1+ 5 1− 5 1 n +1 Fn = τ − (τ ´)n +1 , kde τ = a τ ´= . 2 2 5
(
)
Definice: Nechť n ∈ N . Posloupnost a k L a1 splňující n = ∑ j =1 a j F j nazveme k
a) Fibonacciho rozvojem čísla n, pokud a j ∈ {0,1} pro 1 ≤ j ≤ k
b) Fibonacciho reprezentací čísla n, pokud a j ∈ N pro 1 ≤ j ≤ k Zapisujeme n = (a k a k −1 L a1 )F .
Hladový rozvoj: Lexikograficky největší, neobsahuje dvě jedničky vedle sebe. Líný rozvoj: Lexikograficky nejmenší, neobsahuje dvě nuly vedle sebe. Zápis přirozeného čísla n jako součet různých Fibonacciho čísel není jednoznačný. Příklad: Vypišme některé možné rozvoje čísla n = 63: 63 = 55 + 5 + 3 = F9 + F4 + F3 = (100001100)F 63 = 34 + 21 + 5 + 2 + 1 = F8 + F7 + F4 + F2 + F1 = (11001011)F
Hladový rozvoj čísla 63: 63 = 55 + 8 = F9 + F5 = (100010000)F Reprezentace, která není rozvoj: 63 = 2F7 + 2F5 + F4 = (2021000)F Z definice Fibonacciho čísel vyplývá následující pravidlo pro rozvoje: „Pokud ve Fibonacciho rozvoji čísla n zaměníme libovolnou sekvenci 100 za 011 nebo naopak, získáme Fibonacciho rozvoj stejného čísla. Postupným zaměňováním těchto sekvencí získáme všechny Fibonacciho rozvoje čísla n.“ K převodu přirozeného čísla do Fibonacciho soustavy použijeme hladový algoritmus, který je pro Fibonacciho soustavu jednodušší, než pro soustavy obecné. Zjednodušení je možné díky omezení koeficientů a efektivnímu výpočtu Fibonacciho čísel. Hladový algoritmus je velmi podobný algoritmu pro převádění čísel z desítkové soustavy do dvojkové. Podařilo se ukázat, že průměrný počet nul za první jedničkou v hladovém rozvoji konverguje k hodnotě τ 2 ≅ 2,618 . Proto ve hladovém algoritmu budeme Fibonacciho čísla počítat zpětně dle vztahu F j = F j + 2 − F j +1 . Poznámka: Pro hladový rozvoj čísla n ∈ N používáme často zápis n = 10 r110 r2 L10 rk . Zápisem 10 i rozumíme jedničku a za ní i nul. Poznamenejme, že hladový rozvoj Fibonacciho čísla Fn má právě n míst, z toho na prvním místě je jednička a za ní následuje n–1 nul.
Počet rozvojů přirozeného čísla n ve Fibonacciho soustavě Chceme zkoumat, kolik existuje různých Fibonacciho rozvojů daného přirozeného čísla n. Dále nás zajímají vlastnosti funkce, která tuto nejednoznačnost popisuje. Definice: Nechť n ∈ N . Definujeme následující funkce: R(n) – počet všech možných rozvojů čísla n do Fibonacciho soustavy R0(n) – počet krátkých rozvojů čísla n, tj. těch, které mají délku menší než hladový R1(n) – počet dlouhých rozvojů n, tj. těch, které mají stejnou délku jako hladový Je zřejmé, že platí: R (n ) = R0 (n ) + R1 (n ) . Dále se podařilo ukázat, že funkce R(n) je
F symetrická a platí R(Fk − 1 + i ) = R(Fk +1 − 1 − i ) pro každé i ∈ 0, K , k −1 . 2
Funkce R(n)
Metody pro výpočet hodnot R(n): a) Přímá metoda – využívá nahrazování sekvencí 100 za 011. Vychází z hladového rozvoje, je velmi zdlouhavá a neefektivní. Používá se pro výpis všech možných rozvojů daného přirozeného čísla n. b) Gi – Hi metoda – velmi rychlá a efektivní metoda pro výpočet hodnot R(n) založená na výpočtu hodnot dvou velmi rychle konvergujících posloupností. Vychází z hladového algoritmu, konkrétně pak z počtů nul mezi sousedícími jedničkami v hladovém rozvoji. Metoda je složitosti O(log n). c) Berstelova metoda – rovněž velmi rychlá a efektivní metoda pro výpočet hodnot R(n) založená na Berstelově maticovém schématu. Využívá rekurzivních vlastností posloupnosti R(n) a je stejné složitosti jako metoda Gi – Hi, tedy O(log n).
Vlastnosti funkce R(n) Funkce R(n) byla podrobena rozsáhlému výzkumu. Podařilo se nejen dokázat její symetrii, ale také polohu a jednoznačný tvar všech jejich maxim a minim. Podařilo se ukázat, jaká přirozená čísla mají maximální možný počet rozvojů do Fibonacciho číselné soustavy, uvažujeme-li rozvoje pevné délky. Pro hledání maxim této funkce potřebujeme definovat následující funkce: Max(n ) = max{R(k ) | Fn ≤ k < Fn +1 }
ArgMax(n ) = {k ∈ N | Fn ≤ k < Fn +1 ∧ R(k ) = Max(n )} Funkce Max(n) udává maximální počet rozvojů čísla v intervalu mezi sousedními Fibonacciho čísly. Jde o maximum počtu rozvojů na všech číslech, jejichž hladový rozvoj má ve Fibonacciho soustavě n míst. Funkce ArgMax(n) je množina všech čísel z intervalu Fn , Fn +1 − 1 na kterých funkce R(k) svého maxima nabývá. Zde je souhrn poznatků o funkci R(n), které se podařilo dokázat: a) Pro všechna n ∈ N platí R (n ) ≥ 1 a navíc R(n ) = 1 ⇔ n = Fk − 1 pro nějaké k.
( )
n b) R(Fn ) = R 10 n = + 1 2 c) lim inf R(n ) = 1 , lim sup R(n ) = +∞ . d) Max(2k + 1) = Fk +1 , Max(2k + 2 ) = 2 Fk . e) Pro n lichá mají hladové rozvoje čísel, na kterých funkce R nabývá maxima, tvar ArgMax(4k + 1) = 10 3 L10 310 4 F , 10110 3 L10 310 2 F , kde počet sekvencí 103 je roven k–1. Pro k=2 bude navíc v množině ArgMax prvek (102102102)F. ArgMax(4k + 3) = 10 3 L10 310 2 F , 10110 3 L10 310 4 F , kde počet sekvencí 103 je roven k v prvním rozvoji a k–1 ve druhém rozvoji. f) Pro n sudá, n > 5 , získáme množinu ArgMax(n) tak, že k prvkům množiny ArgMax(n − 3) přidáváme na začátek a na konec sekvenci 100. Nesmíme však přidávat tuto sekvenci současně na začátek i na konec rozvoje. g) R 10 3 L10 310 4 = R 10110 3 L10 310 2 = F2 k +1 , kde počet bloků 103 je roven k–1. h)
( R(10
3
{(
) (
)}
{(
) (
)}
) ( ) = R(10 10
1 3 L10 310 2 L10 310 4 roven k a ve druhém čísle roven k–1.
) )= F
2k +2
, kde počet bloků 103 v prvním čísle je
(
i) Nechť n ∈ N , n = 10 r1 L10 rk
)
F
. Pokud existuje i ∈ {1, K , k } tak, že ri ≥ 5 , potom
R(n) není maximální (pro rozvoje délky k + ∑i =1 ri ). k
(
j) Pokud existuje i ∈ {1, K , k − 2} takové, že ri ≥ 4 , potom rovněž R 10 r1 L10 rk maximální. 5 2n k) Průměrná hodnota R na intervalu Fn , Fn +1 − 1 je přibližně rovna ⋅ . 3 τn
) není
Rekurzivní generování R(n) Byly odvozeny nové algoritmy založené na rekurzivních vlastnostech R(n), které umožnily generovat hodnoty této funkce po velkých blocích a přispěly tak k urychlení výpočtu hodnot této funkce. Rovněž v dalších partiích, které tuto funkci využívají, byly velmi přínosné. Poznatky byly aplikovány také v algoritmu na hledání maxim R(n), kde se podařilo původní složitost řádu O(n log n) snížit na řád O(n).
Funkce rk(m) a její vlastnosti Funkce rk(m) udává četnost výskytu hodnoty m v palindromech posloupnosti R(n). Její formální definice je následující: Definice: Nechť n ∈ N . Definujeme množinu B (m) = ω = 10 r1 L10 rk | r j ≥ 1, rk ≥ 2, R (ω ) = m .
{
}
Definujeme funkci rk(m) = #B(m), kde # značí počet prvků množiny. Funkce rk(m) je velmi chaotická. Nicméně se podařilo o ní dokázat následující tvrzení: a) Prvky množiny B(m) mají rozvoje omezené délky. Tedy pro ω ∈ B (m ) platí | ω |≤ 2m . b) Nechť m ≥ 1 , k ≥ 2m . Potom počet výskytů čísla m mezi čísly R (Fk ), K , R (Fk +1 − 1) je roven rk(m) = #B(m). c) Nechť m ∈ N , m ≥ 2 . Potom hodnota funkce rk(m) je sudé číslo. Pro výpočet hodnot funkce rk(m) je nutné vyjít ze vzorce, který je poněkud nepřehledný, ale který dává funkci rk(m) do souvislosti s Eulerovou funkcí φ : m rk (m ) = ∑ φ ⋅ rk (d ) 1≤ d < m d d |m
S využitím tohoto vztahu spolu se známými vlastnostmi Eulerovy funkce můžeme odvodit velmi nepřehledný vzorec, pomocí kterého budeme moci hodnoty rk(m) algoritmicky vypočítat. Algoritmus bude založen na rychlém výpočtu hodnot Eulerovy funkce – tzv. Eratostenovu sítu. Rovněž můžeme zformulovat vztah pro přímý vzorec rk(m) pro některá m. a) Nechť m je prvočíslo. Potom rk(m) = 2 φ (m ) = 2 (m–1).
( )
b) Nechť m je prvočíslo a k ∈ N . Potom rk p k = 2( p − 1)(2 p − 1) . Poznamenejme, že další zobecnění není přímočaré z důvodů extrémní chaotičnosti funkce rk. k −1
Výpočet hodnot funkce rk(m) a) S využitím rekurzivních vlastností R(n) – algoritmus exponenciální složitosti b) S využitím Eratostenova síta – algoritmus složitosti O(m ln m). Úskalí spočívá ve správném naprogramování velmi nepřehledného vzorce a efektivním výpočtu hodnot.
Funkce rk(m)
Funkce rk(m) je opravdu velmi chaotická
Eulerova funkce φ (n )
Fibonacciho reprezentace přirozeného čísla Počet reprezentací přirozeného čísla ve Fibonacciho soustavě je vetší nebo roven počtu jeho rozvojů. Každý rozvoj je zároveň i reprezentací, opačné tvrzení ale neplatí. Definice: Nechť n ∈ N . Definujme funkci B(n) = počet Fibonacciho reprezentací čísla n. Pro tuto funkci byl odvozen rekurzivní vzorec a algoritmus pro výpočet jejích hodnot. Definice: Nechť i, n ∈ N . Definujeme b(n, i ) = počet Fibonacciho reprezentací čísla n, kde největší Fibonacciho číslo vyskytující se v součtu je Fi. Věta: Nechť k , n ∈ N taková, že Fk ≤ n < Fk +1 . Potom b(n, i ) = 0 pro ∀i > k , i ∈ N . Věta: Pro hodnoty b(n, i ) definované výše platí: b(n, i ) = b(n − Fi , i ) + b(n − Fi , i − 1) + L + b(n − Fi ,1)
Spolu s počáteční podmínkou b(0,1) = 1 tak získáváme vzorec pro výpočet hodnot b(n, i ) . k
Pro výpočet hodnot B(n) použijeme vztah B(n ) = ∑ b(n, i ) , kde k , n ∈ N a Fk ≤ n < Fk +1 . i =1
První pozorování ukazují, že hodnoty B(n) rostou exponenciálně. Toto pozorování se prozatím nepodařilo matematicky dokázat. Co se ale dokázat podařilo, jsou následující tvrzení: a) Funkce B(n) je rostoucí n2 1 n b) Pro všechna n ∈ N platí: b(n,1) = 1 , b(n,2) = , b(n,3) = + . 2 12 2
Funkce B(n)
Závěr Pro práci s Fibonacciho soustavou byl vytvořen program Fibonacci3, který si lze spolu s celou diplomovou prací stáhnout z adresy http://fmanak.webzdarma.cz . Tento program umožnil vzniknout spoustě vět a definic týkajících se Fibonacciho soustavy a funkcí na ní definovaných. Poslouží také k další práci s Fibonacciho soustavou, aplikaci výsledků na konkrétní problematiku a další. Zmíním také možnost používat rychlého výpočtu Eulerovy funkce, která je užitečná zejména v oblasti diskrétní matematiky a kryptologie. Rovněž z odvozených matematických poznatků může vycházet další práce.
