Twierdzenie Zeckendorfa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Twierdzenie Zeckendorfa, od nazwiska belgijskiego matematyka Edouarda Zeckendorfa, jest twierdzeniem o reprezentacji liczb całkowitych jako sum liczb Fibonacciego.

Twierdzenie Zeckendorfa mówi, że każda dodatnia liczba całkowita może być przedstawiona jednoznacznie jako suma jednej lub więcej różnych liczb Fibonacciego w taki sposób, że owa suma nie zawiera żadnych dwóch kolejnych liczb Fibonacciego. Czyli, jeżeli  N jest dowolną dodatnią liczbą całkowitą, istnieją takie liczby całkowite  c_i \geqslant 2 spełniające  c_{i+1} > c_i + 1 , że:

N = \sum_{i = 0}^k F_{c_i},

gdzie  F_n jest n-tą liczbą Fibonacciego. Taką sumę nazywamy reprezentacją Zeckendorfa liczby  N.

Na przykład, reprezentacja Zeckendorfa dla liczby 100 to:

100 = 89 + 8 + 3

Są także inne sposoby przedstawienia liczby 100 jako sumy liczb Fibonacciego, na przykład:

100 = 89 + 8 + 2 + 1
100 = 55 + 34 + 8 + 3

ale nie są one reprezentacjami Zeckendorfa, gdyż 1 i 2 są kolejnymi liczbami Fibonacciego, podobnie jak 34 i 55.

Dla każdej dodatniej liczby całkowitej reprezentacja, która spełnia warunki twierdzenia Zeckendorfa, może być znaleziona poprzez użycie algorytmu zachłannego, poprzez wybór największej możliwej liczby Fibonacciego przy każdym kroku.

Bibliografia[edytuj | edytuj kod]

  • Zeckendorf representation - Wolfram MathWorld (ang.). [dostęp 10.02.2009 r.].
  • D. E. Knuth: Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.
  • E. Zeckendorf: Representation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liege 41, 179-182, 1972