Bilangan Fibonacci

Apa itu bilangan Fibonacci?

Bilangan Fibonacci adalah barisan yang setiap bilangan dari yang ketiga adalah jumlah dua bilangan sebelumnya, dimulai dari 0 dan 1. Dalam lambang F_0=0, F_1=1, F_n=F_n-1+F_n-2 (n\ge2). Suku-suku pertamanya

dan F_20=6765, F_30=832 040, F_50=12 586 269 025. Sebagian buku mulai dari F_1=F_2=1 dan melewatkan F_0; bilangannya sama, jadi periksa konvensi yang dipakai sebuah sumber.

Aturan yang mendefinisikan tiap suku dari suku sebelumnya adalah rekurensi, dan yang ini linear (suku-sukunya hanya dijumlahkan, tidak pernah dikalikan satu sama lain) dan berorde dua (melihat dua tempat ke belakang), itulah sebabnya diperlukan dua nilai awal. Menjalankannya mundur memberi F_-1=1, F_-2=-1, F_-3=2, dan seterusnya, dengan tanda yang bergantian.

Dari mana namanya. Leonardo dari Pisa, yang disebut Fibonacci, memasukkan barisan ini dalam bukunya Liber Abaci (1202) dalam soal tentang kelinci: sepasang kelinci memiliki sepasang anak setiap bulan, dan sepasang anak mulai beranak pada bulan keduanya. Dimulai dari sepasang, berapa pasang yang ada setelah setahun? Setelah 1,2,3,5,8,… jawabannya 377 pasang, yaitu F_14. Secara umum ada F_n+2 pasang setelah n bulan. Barisan ini jauh lebih tua, namun: para sarjana India yang mempelajari irama puisi menguraikannya berabad-abad sebelumnya (lihat sejarah di bawah).

Geser penggeser di bawah untuk membaca nilai eksak F_n sampai n=120, bersama perbandingan tetangga dan uji pertama sebuah rumus terkenal.

Apa yang dihitung oleh bilangan Fibonacci?

Setiap kali soal menghitung dapat dibagi dengan "apa bagian terakhirnya?" menjadi dua salinan yang lebih kecil, jawabannya adalah bilangan Fibonacci. Ambil tangga. Misalkan s_n adalah banyaknya cara menaiki n anak tangga dengan satu atau dua sekali langkah. Langkah terakhir adalah 1 (menyisakan n-1 anak tangga yang didaki sebelumnya, s_n-1 cara) atau 2 (menyisakan n-2, s_n-2 cara), sehingga s_n=s_n-1+s_n-2 dengan s_1=1 dan s_2=2. Itu rekurensi Fibonacci yang bergeser satu tempat: s_n=F_n+1, s_10=F_11=89.

Argumen yang sama menghitung banyak hal: - Pengubinan. Banyaknya cara menutup pita sepanjang n dengan persegi panjang 1 dan domino panjang 2 adalah F_n+1. Hitungan Pingala tentang irama dari suku kata pendek dan panjang adalah soal yang sama. - Untai. Untai biner panjang n tanpa dua 1 berurutan berjumlah F_n+2: untuk n=3 mereka 000,001,010,100,101, lima, F_5. Bilangan yang sama menghitung himpunan bagian \1,\dots,n\ tanpa dua bilangan berurutan. - Kelinci. F_n+2 pasang setelah n bulan, seperti di atas. - Segitiga Pascal. Jumlah sepanjang diagonal landai adalah bilangan Fibonacci: C(5,0)+C(4,1)+C(3,2)=1+4+3=8=F_6, dengan C(n,k) koefisien binomial, dan secara umum F_n+1=\sum_kC(n-k,k).

Komposisi. Menuliskan n sebagai jumlah terurut dari 1 dan 2 adalah soal tangga lagi: 4=1+1+1+1, 4=1+1+2, 4=1+2+1, 4=2+1+1, dan 4=2+2: lima cara, F_5. Itulah sebabnya bilangan Fibonacci muncul dalam begitu banyak latihan menghitung, dan sebabnya contoh pemrograman dinamis "menaiki tangga" adalah perhitungan Fibonacci yang menyamar (lihat bagian tentang menghitung di bawah).

Adakah rumus untuk bilangan Fibonacci ke-n?

Ya: rumus Binet F_n=(φ^n-\psi^n)/(√5), dengan φ=(1+√5)/(2) dan \psi=(1-√5)/(2) kedua akar x^2=x+1. Inilah alasannya. Cari penyelesaian rekurensi berbentuk F_n=r^n. Maka r^n=r^n-1+r^n-2, dan membagi dengan r^n-2 memberi r^2=r+1, r=(1±√5)/(2). Jadi φ^n dan \psi^n keduanya memenuhi rekurensi, demikian pula setiap kombinasi Aφ^n+B\psi^n (rekurensinya linear). Pilih A dan B agar cocok dengan nilai awal: F_0=0 memberi A+B=0, dan F_1=1 memberi Aφ+B\psi=1. Karena φ-\psi=√5, solusinya A=(1)/(√5)=-B, yaitu rumus Binet (sudah dikenal Euler dan de Moivre; Jacques Binet menerbitkannya pada 1843).

Siapa kedua bilangan itu. φ=1,6180339887… adalah rasio emas, dan \psi=1-φ=-\frac1φ=-0,6180339887… memiliki nilai mutlak di bawah 1, sehingga \psi^n menyusut cepat dan tandanya bergantian. Untuk n\ge0 berlaku \left|(\psi^n)/(√5)\right|\le\frac1√5<\frac12, sehingga F_n adalah bilangan bulat terdekat dengan (φ^n)/(√5): untuk n=10, (φ^10)/(√5)=55,0036…, yang dibulatkan menjadi F_10=55.

Perbandingan tetangga. Dari rumus itu, F_n+1-φ F_n=\psi^n secara eksak, sehingga (F_n+1)/(F_n)-φ=(\psi^n)/(F_n)≈((-1)^n)/(√5 F_n^2). Perbandingan itu karenanya bergantian di sekitar φ (1,2,1,5,1,667,1,6,1,625,1,615,…) dan sampai ke sana dengan cepat: ia memperoleh sekitar 2\log_10φ≈0,42 tempat desimal per langkah, sehingga (F_31)/(F_30) sudah sesuai dengan φ sampai sepuluh desimal. Bandingkan dengan bilangan irasional yang paling sulit dihampiri pecahan: pecahan (F_n+1)/(F_n) persis yang terbaik untuk φ, dan merupakan pecahan berantai yang paling lambat konvergen.

Peringatan bagi pemrogram. Menghitung round(phi ** n / sqrt(5)) dengan bilangan titik mengambang biasa benar untuk n\le70 dan salah mulai n=71 (308 061 521 170 130 bukan 308 061 521 170 129): sebuah double hanya memiliki sekitar 16 angka (lihat jarak antarbilangan titik mengambang), dan φ^71 harus diketahui lebih baik daripada satu bagian dalam 10^15. Untuk nilai eksak pakai bilangan bulat.

Identitas apa yang dipenuhi bilangan Fibonacci?

Bilangan Fibonacci memenuhi lusinan identitas, dan beberapa bukti singkat menjelaskan sebagian besarnya.

Jumlah. Karena F_k=F_k+2-F_k+1, menjumlahkan untuk k=1 sampai n meniadakan suku-suku: F_1+F_2+…+F_n=F_n+2-F_2=F_n+2-1. Untuk n=10 kesepuluh suku 1,1,2,3,5,8,13,21,34,55 berjumlah 143, dan F_12-1=143 juga. Dengan cara yang sama F_1+F_3+…+F_2n-1=F_2n dan F_2+F_4+…+F_2n=F_2n+1-1. Untuk kuadrat, gambar persegi bersisi F_k× F_k yang ditumpuk menjadi persegi panjang F_n× F_n+1 membuktikan F_1^2+F_2^2+…+F_n^2=F_nF_n+1, 1+1+4+9+25=40=5·8.

Bukti matriks. Misalkan Q=\beginpmatrix1&1\\1&0\endpmatrix. Maka Q\beginpmatrixF_n\\F_n-1\endpmatrix=\beginpmatrixF_n+1\\F_n\endpmatrix, sehingga dengan induksi Q^n=\beginpmatrixF_n+1&F_n\\F_n&F_n-1\endpmatrix. Dua fakta langsung mengikuti. Dengan determinan, \det Q=-1 memberi identitas Cassini F_n-1F_n+1-F_n^2=(-1)^n. Dan Q^2n=(Q^n)^2 membandingkan entri-entrinya untuk memberi rumus penggandaan F_2n=F_n (2F_n+1-F_n), F_2n+1=F_n^2+F_n+1^2. Misalnya F_20=F_10(2F_11-F_10)=55·123=6765.

Persegi yang hilang. Cassini dengan n=6 berkata F_5F_7-F_6^2=5·13-8^2=1. Itulah teka-teki lama tentang memotong persegi 8×8 (luas 64) menjadi empat bagian dan menyusunnya menjadi persegi panjang 5×13 (luas 65): bagian-bagian itu tidak dapat mengisi persegi panjang secara tepat, dan di sepanjang diagonal panjang ada celah tipis seluas 1 yang tidak terlihat mata, karena bilangan Fibonacci berurutan memiliki perbandingan yang begitu dekat dengan φ.

Keterbagian. Bilangan Fibonacci berurutan saling prima: pembagi persekutuan F_n+1 dan F_n membagi F_n+1F_n-1-F_n^2=±1. Lebih umum \gcd(F_m,F_n)=F_\gcd(m,n). Jadi F_m membagi F_n bila m membagi n (misalnya F_6=8 membagi F_12=144), setiap bilangan Fibonacci ketiga genap, setiap yang keempat kelipatan 3, dan setiap yang kelima kelipatan 5. Buktinya memakai F_m+n=F_m+1F_n+F_mF_n-1, yang mengubah \gcd(F_m,F_n) menjadi \gcd(F_m-n,F_n): algoritma Euclid berjalan pada subskripnya.

Pilih n di bawah. Setiap identitas memiliki ruas kiri yang disusun dengan cara panjang dan ruas kanan dari rumus ringkas, dengan bilangan eksak, dan baris terakhir memeriksa aturan gcd.

Bagaimana menghitung bilangan Fibonacci dengan cepat?

Rekurensi mengundang fungsi rekursif, dan itulah cara paling lambat menghitung bilangan Fibonacci; perulangan cukup cepat untuk kebanyakan keperluan, dan penggandaan cepat adalah cara mencapai n yang sangat besar.

Rekursi biasa. fib(n) = fib(n-1) + fib(n-2) menghitung ulang nilai yang sama berulang-ulang. Banyaknya panggilan C_n memenuhi C_n=C_n-1+C_n-2+1 dengan C_0=C_1=1, yang diselesaikan menjadi C_n=2F_n+1-1≈(2φ^n+1)/(√5). Itu 21 891 panggilan untuk n=20, 331 160 281 untuk n=40, 40 730 022 147 untuk n=50 (sekitar 41 detik pada satu miliar panggilan per detik) dan sekitar 1,1×10^21 untuk n=100 (sekitar 36 000 tahun). Biayanya tumbuh seperti φ^n, eksponensial, yaitu contoh yang dipakai dalam bagian tentang rekurensi pada artikel Big-O.

Memoisasi dan perulangan. Ingat setiap nilai yang sudah dihitung dan panggilan turun menjadi 2n-1. Lebih baik lagi, simpan hanya dua nilai terakhir dalam perulangan: n-1 penjumlahan tanpa rekursi (batas bawaan Python sebesar 1000 panggilan bersarang menghentikan versi rekursif di sekitar n=1000).

Penggandaan cepat. Identitas F_2k=F_k(2F_k+1-F_k) dan F_2k+1=F_k^2+F_k+1^2 mendapatkan (F_2k,F_2k+1) dari (F_k,F_k+1), sehingga dengan membaca bit n dari atas, satu langkah penggandaan per bit memberi (F_n,F_n+1) dengan 3\lceil\log_2n\rceil perkalian. Ini adalah perpangkatan dengan pengkuadratan yang diterapkan pada matriks Q di bagian sebelumnya, dengan entri yang berlebih dibuang. Untuk mendapatkan F_10^6 diperlukan 20 langkah, bukan sejuta penjumlahan.

Bilangannya menjadi panjang. F_n memiliki \lfloor n\log_10φ-\log_10√5\rfloor+1 angka, sekitar 0,209 n: F_100 memiliki 21, F_1000 memiliki 209, F_10^5 memiliki 20 899 dan F_10^6 memiliki 208 988. Jadi satu penjumlahan bukan satu langkah melainkan sekitar 0,2 n operasi angka, dan perulangan sebenarnya berbiaya sekitar n^2 operasi angka. Penggandaan cepat juga menang di sini, karena ia mengalikan beberapa bilangan yang sangat panjang. Perhatikan pula bahwa bilangan bulat berukuran tetap meluap lebih awal: bilangan bulat bertanda 32-bit berhenti di F_46=1 836 311 903 dan sebuah double berhenti eksak di F_78 (lihat bilangan biner).

Geser n di bawah untuk membandingkan keempat cara dan membaca angka pertama dan terakhir dari jawaban eksak.

Bagaimana menuliskan bilangan sebagai jumlah bilangan Fibonacci?

Teorema Zeckendorf berkata bahwa setiap bilangan bulat positif adalah jumlah bilangan Fibonacci dari 1,2,3,5,8,13,… dengan tepat satu cara bila tidak ada dua di antaranya yang boleh bertetangga dalam daftar itu. Misalnya 100=89+8+3=F_11+F_6+F_4, 12=8+3+1, 4=3+1. (Daftar dimulai dari F_2=1, karena F_1 adalah bilangan yang sama.) Bila aturan tanpa tetangga dibuang, bilangan yang sama biasanya memiliki beberapa jumlah: 100 dapat ditulis dalam 9 cara dengan bilangan Fibonacci berbeda, seperti 89+8+3 dan 55+34+8+3, dan hanya satu yang tanpa tetangga.

Metode rakus menemukannya. Ambil bilangan Fibonacci terbesar yang tidak melebihi N, kurangkan, dan ulangi pada sisanya. Sisanya lebih kecil daripada bilangan Fibonacci sebelumnya (jika tidak, yang lebih besar akan muat), sehingga suku berikutnya tidak pernah bertetangga dengan yang baru diambil.

Mengapa tunggal. Jumlah teleskopik pada bagian identitas menunjukkan bahwa jumlah terbesar bilangan Fibonacci tak bertetangga di bawah F_k adalah F_k-1+F_k-3+F_k-5+…=F_k-1 (untuk k=7: 8+3+1=12=13-1). Jadi jumlah tanpa tetangga untuk N tidak dapat melewatkan bilangan Fibonacci terbesar F_k\le N: tanpanya jumlahnya paling banyak F_k-1<N. Suku terbesarnya dipaksa, dan argumennya berulang pada sisanya.

Angka Fibonacci. Tulis 1 untuk setiap bilangan Fibonacci yang dipakai dan 0 untuk yang dilewati, dari yang terbesar turun ke F_2: 100 menjadi 1000010100 (posisi F_11 sampai F_2), dan tidak pernah ada dua 1 yang bersebelahan. Ia adalah sistem bilangan dengan bilangan Fibonacci sebagai nilai tempat, seperti biner memakai pangkat dua. Karena 11 tidak pernah muncul di dalam sebuah kata sandi, menuliskan satu 1 tambahan setelah angka terakhir menandai akhir kata: kode Fibonacci yang dapat menyimpan barisan bilangan tanpa pemisah, kode yang bertahan terhadap bit yang rusak lebih baik daripada banyak kode lain. Biner biasa memakai sekitar \log_2N angka dan sistem Fibonacci sekitar \log_φ N, sekitar empat puluh empat persen lebih banyak.

Ketik sebuah bilangan di bawah untuk melihat jumlah Zeckendorf-nya, untaian angka Fibonacci di samping bentuk binernya dan banyaknya jumlah lain; tabel di bawahnya mendaftar 1 sampai 20.

Apa itu periode Pisano?

Sisa bilangan Fibonacci modulo m berulang dengan periode yang disebut periode Pisano π(m), yang memungkinkan kamu mencari F_n\bmod m untuk n yang sangat besar dengan mereduksi n lebih dulu. Modulo 10 barisannya 0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1, 0,1,1,… dan ia dimulai lagi setelah 60 bilangan: π(10)=60. Jadi angka terakhir F_n adalah angka terakhir F_n\bmod60.

Mengapa barisannya berulang. Lihat pasangan (F_n\bmod m, F_n+1\bmod m). Hanya ada m^2 pasangan yang mungkin, jadi sebuah pasangan harus kembali, dan sejak itu semuanya berulang, karena sebuah pasangan menentukan yang berikutnya. Langkah (a,b)→(b,a+b) juga dapat dibatalkan, (b,c)→(c-b,b), sehingga pasangan pertama yang kembali adalah yang paling pertama, (0,1): barisannya murni periodik, tanpa bagian pendahulu. Bahkan π(m)\le6m.

Beberapa nilai: π(2)=3, π(3)=8, π(4)=6, π(5)=20, π(6)=24, π(7)=16, π(10)=60, π(100)=300, π(1000)=1500, dan π(10^k)=15·10^k-1 untuk k\ge3. Jadi dua angka terakhir berulang setiap 300 bilangan dan tiga angka terakhir setiap 1500.

Contoh lengkap. Berapa angka terakhir F_10^18? Karena 10^18\bmod60=40 dan F_40=102 334 155, jawabannya 5. Dan dengan penggandaan cepat dan sisa yang diambil pada setiap langkah, F_10^18\bmod(10^9+7)=209 783 453 keluar dalam sekitar enam puluh langkah; tidak ada barisan sekuintiliun suku yang pernah ditulis. Ini adalah pemakaian standar bilangan Fibonacci dalam kontes dan kriptografi: "beri jawabannya modulo 10^9+7".

Pilih modulus di bawah, lihat sisa dan periodenya, lalu cari F_n\bmod m untuk n sampai tiga puluh angka.

Di mana bilangan Fibonacci benar-benar muncul di alam dan dalam algoritma?

Rasio emas φ dan bilangan Fibonacci muncul di beberapa tempat yang dapat dijelaskan, dan di banyak tempat yang merupakan mitos.

Persegi panjang emas. Persegi panjang dengan sisi berperbandingan φ:1 memiliki sifat khusus: potong sebuah persegi dan yang tersisa adalah persegi panjang yang lebih kecil dengan perbandingan yang sama, karena φ^2=φ+1 membuat (1)/(φ-1)=φ. Persegi bersisi 1,1,2,3,5,8,… saling bertaut menjadi spiral pada sampul artikel ini, dan seperempat lingkaran yang digambar di dalamnya menghampiri spiral emas. Itu hampiran: spiral emas sejati tumbuh dengan faktor φ setiap seperempat putaran, sedangkan persegi Fibonacci tumbuh dengan perbandingan yang hanya dekat dengannya.

Biji, kerucut, dan nanas. Pada kepala bunga matahari, kerucut pinus, atau nanas, biji atau sisiknya berada pada dua keluarga spiral, masing-masing berputar ke satu arah, dan kedua hitungannya sangat sering bertetangga dalam barisan Fibonacci: 34 dan 55 (atau 55 dan 89) pada kepala bunga matahari, 8 dan 13 pada banyak kerucut pinus. Ada alasannya. Tumbuhan yang menambahkan setiap biji baru pada putaran tetap dari yang sebelumnya menyia-nyiakan ruang kecuali putarannya adalah pecahan lingkaran yang tidak dapat dihampiri dengan baik oleh pecahan sederhana, dan (1)/(φ^2) adalah bilangan paling sulit seperti itu (lihat hampiran rasional bilangan irasional). Putarannya adalah sudut emas (360^\circ)/(φ^2)≈137,5^\circ, dan ia menghasilkan spiral yang dihitung dengan bilangan Fibonacci bertetangga. Ini model Helmut Vogel (1979); tumbuhan sungguhan sering mengikutinya, tidak selalu.

Apa yang mitos. Klaim bahwa Piramida Besar, Parthenon, Mona Lisa, atau proporsi tubuh manusia dirancang dengan rasio emas bersandar pada pengukuran selektif atau tanpa bukti, dan cangkang nautilus adalah spiral logaritmik yang bukan emas. Banyaknya kelopak sebuah bunga adalah bilangan Fibonacci sebagian karena bilangan kecil ada di mana-mana. Perlakukan pernyataan seperti itu dengan curiga, dan tanyakan pengukuran apa yang diambil dan di mana.

Dalam algoritma. Bilangan Fibonacci melakukan kerja nyata dalam komputasi. Algoritma Euclid untuk gcd paling lambat pada bilangan Fibonacci berurutan: \gcd(F_n+1,F_n) memerlukan tepat n-1 langkah pembagian, dan Gabriel Lamé membuktikan pada 1844 bahwa banyaknya langkah tidak pernah melebihi lima kali banyaknya angka bilangan yang lebih kecil (sering disebut analisis pertama waktu jalan sebuah algoritma). Pencarian Fibonacci dan pencarian golden-section (lihat artikel optimisasi) memperkecil kurungan dengan rasio emas. Heap Fibonacci mendapat namanya dari bilangan Fibonacci yang membatasi ukuran pohonnya.

Bagaimana menghitung bilangan Fibonacci di Python, JavaScript, dan C++?

Pakai bilangan bulat berpresisi sembarang (int Python, BigInt JavaScript), perulangan untuk n biasa dan penggandaan cepat untuk n yang sangat besar, dan ambil sisa pada setiap langkah bila hanya F_n\bmod m yang diperlukan. Program Python pertama menghitung panggilan rekursi biasa, lalu menghitung bilangan yang sama dengan memo, perulangan, dan penggandaan cepat, dan memeriksa rumus Binet. Peringatan: sejak Python 3.11 bilangan bulat lebih dari 4300 angka tidak dapat diubah menjadi teks kecuali kamu menaikkan batasnya dengan sys.set_int_max_str_digits, itulah sebabnya program mencetak banyaknya bit F_10^6, bukan angkanya.

from functools import lru_cache
from math import sqrt


def fib_naive(n):
    """Returns (F(n), number of calls) for the plain recursion."""
    if n < 2:
        return n, 1
    a, ca = fib_naive(n - 1)
    b, cb = fib_naive(n - 2)
    return a + b, ca + cb + 1


@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)


def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def fib_doubling(n):
    """Returns (F(n), F(n + 1)) with F(2k) = F(k)(2F(k+1) - F(k)) and F(2k+1) = F(k)^2 + F(k+1)^2."""
    if n == 0:
        return 0, 1
    a, b = fib_doubling(n // 2)
    c = a * (2 * b - a)
    d = a * a + b * b
    return (d, c + d) if n % 2 else (c, d)


print(fib_naive(20), fib_memo(20), fib_loop(20), fib_doubling(20)[0])
print(fib_naive(25)[1], 2 * fib_loop(26) - 1)               # the calls: 2F(n+1) - 1
print(fib_loop(100), len(str(fib_doubling(1000)[0])), len(str(fib_doubling(20000)[0])))
print(fib_doubling(10 ** 6)[0].bit_length())                 # a number of 208 988 digits, in a blink

phi = (1 + sqrt(5)) / 2
for n in (10, 70, 71, 72):
    print(n, round(phi ** n / sqrt(5)), fib_loop(n))         # Binet in doubles goes wrong at 71
# (6765, 21891) 6765 6765 6765
# 242785 242785
# 354224848179261915075 209 4180
# 694241
# 10 55 55
# 70 190392490709135 190392490709135
# 71 308061521170130 308061521170129
# 72 498454011879265 498454011879264

def zeckendorf(n):
    """Greedy: the largest Fibonacci number that fits, again and again."""
    fibs = [1, 2]
    while fibs[-1] <= n:
        fibs.append(fibs[-1] + fibs[-2])
    out = []
    for f in reversed(fibs):
        if f <= n:
            out.append(f)
            n -= f
    return out


def pisano(m):
    """The period of F(n) mod m: walk the pairs of remainders until (0, 1) returns."""
    a, b, p = 0, 1 % m, 0
    while True:
        a, b = b, (a + b) % m
        p += 1
        if (a, b) == (0, 1 % m):
            return p


def fib_mod(n, m):
    """F(n) mod m for a huge n, by fast doubling with the remainder taken at each step."""
    def go(k):
        if k == 0:
            return 0, 1 % m
        a, b = go(k // 2)
        c = a * (2 * b - a) % m
        d = (a * a + b * b) % m
        return (d, (c + d) % m) if k % 2 else (c, d)
    return go(n)[0]


print(zeckendorf(100), zeckendorf(2026))
print([pisano(m) for m in (2, 3, 5, 10, 100, 1000)])
print(fib_mod(10 ** 18, 10), fib_mod(10 ** 18, 10 ** 9 + 7), fib_mod(10 ** 18, 1000))
print(fib_mod(10 ** 18 % 60, 10), fib_mod(10, 10 ** 9 + 7))  # reduce n by the period first
# [89, 8, 3] [1597, 377, 34, 13, 5]
# [3, 8, 20, 60, 300, 1500]
# 5 209783453 875
# 5 55

const fib = (n) => { let a = 0n, b = 1n; for (let i = 0; i < n; i++) [a, b] = [b, a + b]; return a }
fib(100)                                      // 354224848179261915075n

// fast doubling: F(2k) = F(k)(2F(k+1) - F(k)), F(2k+1) = F(k)^2 + F(k+1)^2
const pair = (n) => {
  if (n === 0n) return [0n, 1n]
  const [a, b] = pair(n >> 1n)
  const c = a * (2n * b - a), d = a * a + b * b
  return n & 1n ? [d, c + d] : [c, d]
}
pair(1000000n)[0].toString().length           // 208988

// plain numbers stop being exact: the first b that is not a safe integer is wrong in its last digit
let a = 0, b = 1, n = 0
while (Number.isSafeInteger(b)) { [a, b] = [b, a + b]; n++ }
;[n, a, b]                                    // [78, 8944394323791464, 14472334024676220]; the true F(79) ends in ...221

// Binet in doubles
const phi = (1 + Math.sqrt(5)) / 2
let k = 0
while (BigInt(Math.round(phi ** k / Math.sqrt(5))) === fib(k)) k++
k                                             // 71

// F(n) mod m for a huge n
const fibMod = (n, m) => {
  const go = (j) => {
    if (j === 0n) return [0n, 1n % m]
    const [x, y] = go(j >> 1n)
    const c = (x * ((2n * y - x) % m + m)) % m, d = (x * x + y * y) % m
    return j & 1n ? [d, (c + d) % m] : [c, d]
  }
  return go(n)[0]
}
;[fibMod(10n ** 18n, 10n), fibMod(10n ** 18n, 1000000007n)]   // [5n, 209783453n]

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
  int a = 0, b = 1;
  for (int i = 0; i < 40; i++) {
    int t = a + b;
    a = b;
    b = t;
  }
  printf("%d\n", a);                                   // F(40); F(47) no longer fits in an int

  int ms[4] = {2, 5, 10, 100};
  for (int k = 0; k < 4; k++) {
    int m = ms[k], x = 0, y = 1 % m, p = 0;
    do {
      int t = (x + y) % m;
      x = y;
      y = t;
      p++;
    } while (!(x == 0 && y == 1));
    printf("%d %d\n", m, p);                           // the Pisano period
  }

  int u = 233, v = 144, steps = 0;                     // Euclid's algorithm on F(13) and F(12)
  while (v != 0) {
    int t = u % v;
    u = v;
    v = t;
    steps++;
  }
  printf("%d %d\n", u, steps);                         // gcd 1 after n - 1 = 11 divisions
  return 0;
}

/* output:
102334155
2 3
5 20
10 60
100 300
1 11
*/

Dari mana bilangan Fibonacci berasal?

Bilangan Fibonacci ditemukan di India sebagai hitungan irama puisi, berabad-abad sebelum kelinci Fibonacci.

• Sekitar 200 SM. Sarjana India Pingala, dalam karyanya tentang matra Sanskerta, menghitung pola suku kata pendek dan panjang, yang mengarah ke bilangan 1,2,3,5,8,….
• Sekitar 700 dan 1150. Virahanka menyatakan aturan bahwa setiap hitungan adalah jumlah dua hitungan sebelumnya, dan Hemachandra memberikannya lagi; Gopala telah melakukannya sekitar 1135.
• 1202. Leonardo dari Pisa, yang dikenal sebagai Fibonacci, menerbitkan Liber Abaci dengan soal kelinci dan suku-suku pertama sampai 377. Buku itu terutama mengajarkan angka Hindu-Arab kepada orang Eropa.
• 1730–1843. Abraham de Moivre dan Leonhard Euler mengetahui rumus tertutupnya; Jacques Binet menerbitkannya pada 1843.
• 1844. Gabriel Lamé memakai bilangan Fibonacci untuk membatasi langkah algoritma Euclid.
• 1870-an. Édouard Lucas mempelajari barisan itu secara mendalam, memperkenalkan bilangan Lucas pendampingnya 2,1,3,4,7,11,…, memakainya untuk menguji apakah bilangan besar prima, dan menamai barisan itu Fibonacci.
• 1939–1972. Edouard Zeckendorf membuktikan teorema tentang jumlah bilangan Fibonacci (diterbitkan pada 1972, setelah makalah Gerrit Lekkerkerker tahun 1952).
• 1963. Fibonacci Association dan jurnalnya, Fibonacci Quarterly, didirikan.
• 1970. Yuri Matiyasevich memakai pertumbuhan eksponensial bilangan Fibonacci untuk melengkapi bukti bahwa masalah kesepuluh Hilbert, metode umum untuk menyelesaikan persamaan dalam bilangan bulat, tidak memiliki penyelesaian.

Kesalahan apa yang sering terjadi pada bilangan Fibonacci?

Kesalahan paling umum pada bilangan Fibonacci adalah sembilan hal berikut, masing-masing dengan pernyataan yang benar.

Latihan: uji pemahamanmu

Soal-soal ini mencampur semua yang dibahas di atas. Jika jawabanmu belum tepat, perhatikan petunjuk yang tersedia, lalu coba kembali.

Ringkasan: bilangan Fibonacci sekilas

• Definisi: F_0=0, F_1=1, F_n=F_n-1+F_n-2; F_n+1 menghitung cara menaiki n anak tangga dengan langkah 1 atau 2.
• Binet: F_n=(φ^n-\psi^n)/(√5), bilangan bulat terdekat dengan (φ^n)/(√5); perbandingan (F_n+1)/(F_n) adalah φ+(\psi^n)/(F_n); dalam double ia gagal pada n=71.
• Identitas: \sum F_k=F_n+2-1, \sum F_k^2=F_nF_n+1, Cassini (-1)^n, penggandaan, \gcd(F_m,F_n)=F_\gcd(m,n); semuanya mengikuti dari Q=\beginpmatrix1&1\\1&0\endpmatrix.
• Menghitung: rekursi 2F_n+1-1 panggilan, memo 2n-1, perulangan n-1 penjumlahan, penggandaan cepat 3\lceil\log_2n\rceil perkalian; F_n memiliki 0,209 n angka.
• Zeckendorf: setiap bilangan bulat positif adalah jumlah tunggal bilangan Fibonacci tak bertetangga, ditemukan secara rakus; kode Fibonacci dibangun di atasnya.
• Pisano: F_n\bmod m berulang dengan periode π(m)\le6m; π(10)=60, jadi reduksi n lebih dulu.
• Alam dan algoritma: sudut emas 137,5^\circ pada spiral biji, kasus terburuk Euclid; klaim piramida dan lukisan adalah mitos.
• Kode: bilangan bulat besar, perulangan, penggandaan cepat, sisa pada setiap langkah.

Glosarium: istilah penting

Bilangan Fibonacci

Suku barisan 0, 1, 1, 2, 3, 5, 8, 13, … yang setiap sukunya adalah jumlah dua suku sebelumnya.

Rasio emas

Bilangan 1 ditambah akar 5, dibagi 2, sekitar 1,618, limit perbandingan bilangan Fibonacci berurutan.

Rumus Binet

Bentuk tertutup bilangan Fibonacci ke-n sebagai selisih pangkat ke-n dari kedua akar x kuadrat sama dengan x tambah 1, dibagi akar 5.

Identitas Cassini

Identitas bahwa F(n−1) kali F(n+1) dikurangi F(n) kuadrat sama dengan minus 1 pangkat n.

Penggandaan cepat

Cara yang mendapatkan F(n) dengan sekitar log n perkalian bilangan besar dengan memperoleh F(2k) dan F(2k+1) dari F(k) dan F(k+1).

Representasi Zeckendorf

Cara tunggal menuliskan bilangan bulat positif sebagai jumlah bilangan Fibonacci yang tidak ada dua yang bertetangga dalam barisan.

Periode Pisano

Panjang siklus bilangan Fibonacci modulo m, ditulis pi dari m; untuk m sama dengan 10 nilainya 60.

Filotaksis

Susunan daun, biji, atau sisik pada tumbuhan, sering dalam spiral yang hitungannya adalah bilangan Fibonacci bertetangga.

Bilangan Lucas

Barisan pendamping 2, 1, 3, 4, 7, 11, … dengan rekurensi yang sama seperti bilangan Fibonacci tetapi nilai awal berbeda.

Pertanyaan yang sering diajukan

Referensi

1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics (2nd ed.), section 6.6: Fibonacci Numbers. Addison-Wesley.
2. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1 (3rd ed.), section 1.2.8: Fibonacci Numbers. Addison-Wesley.
3. Thomas Koshy (2001). Fibonacci and Lucas Numbers with Applications. Wiley.
4. Laurence Sigler (2002). Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation. Springer.
5. Parmanand Singh (1985). The so-called Fibonacci numbers in ancient and medieval India. Historia Mathematica 12.
6. George Markowsky (1992). Misconceptions about the golden ratio. The College Mathematics Journal 23(1).
7. Gabriel Lamé (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus de l'Académie des Sciences 19.

Artikel terkait

• Barisan dan Deret Geometri: Rasio, Jumlah, dan Pertumbuhan: Barisan dan deret geometri: rasio, rumus suku ke-n, jumlah berhingga dan tak hingga, rata-rata geometri, bunga majemuk, dan peluruhan, dengan latihan.
• Notasi Big-O: Notasi Big-O dijelaskan: definisi, laju pertumbuhan dari O(1) sampai O(n!), menghitung langkah dalam kode, kasus terbaik dan terburuk, rekurensi, dan teorema Master.
• Bilangan Irasional: Pengertian, Contoh, Bukti, dan Hampiran: Bilangan irasional: mengapa √2 irasional, akar mana yang irasional, jumlah dan hasil kali, π dan e, bilangan transenden, serta hampiran pecahan, dengan latihan.
• Barisan dan Deret Aritmetika: Rumus, Jumlah, dan Contoh: Barisan dan deret aritmetika: beda, rumus suku ke-n, rumus jumlah, trik Gauss, rata-rata aritmetika, dan soal cerita, lengkap dengan latihan.