Negafibonacci
A matematikában a nem Gafibonacci-számok a Fibonacci-sorozat negatívan indexelt elemei .
A negafibonacci-számokat induktív módon a következő rekurzív összefüggés határozza meg:
- F − 1 = 1,
- F -2 = -1,
- F n = F (n+2) −F (n+1) .
Meghatározhatók az F −n = (−1) n+1 F n képlettel is .
A nega-Fibonacci sorozat első 10 száma:
| n | F( n ) |
|---|---|
| −1 | egy |
| −2 | −1 |
| −3 | 2 |
| −4 | −3 |
| −5 | 5 |
| −6 | −8 |
| −7 | 13 |
| −8 | −21 |
| −9 | 34 |
| −10 | −55 |
Egész szám ábrázolása
Bármely egész szám egyértelműen ábrázolható – Donald Knuth [1] munkája szerint – olyan nem-Fibonacci-számok összegeként, amelyek nem használnak két egymást követő nem-Fibonacci-számot. Például:
- −11 = F −4 + F −6 = (-3) + (-8)
- 12 = F - 2 + F - 7 = (-1) + 13
- 24 = F − 1 + F− 4 + F− 6 + F −9 = 1 + (-3) + (-8) + 34
- −43 = F −2 + F −7 + F −10 = (-1) + 13 + (-55)
- A 0-t üres összeg jelenti.
Figyelemre méltó, hogy például 0 = F −1 + F −2 , így az ábrázolás egyedisége valóban attól függ, hogy nem használunk két egymást követő nem Fibonacci számot.
Ez lehetővé teszi a nega-Fibonacci kódolórendszer számára, hogy a Zeckendorf-tételhez hasonló egész számokat kódoljon a számok bináris reprezentációval történő átkódolására. Az x , n - edik egész számot reprezentáló sorozatban a számjegy 1, ha F n szerepel az x -et képviselő összegben ; ez a számjegy nem 0. Például a 24-es szám ábrázolható az 100101001 sorozattal, amelynek 9, 6, 4 és 1 helyén az 1-es számjegy található, mert 24 = F −1 + F −4 + F − 6 + F - 9 . Egy x egész számot akkor és csak akkor páratlan hosszúságú sorozat reprezentál .
Identitások
Kapcsolatok a Fibonacci-számok normál, pozitív sorozatával:
