ফিবোনাচ্চি সংখ্যা#

ফিবোনাচ্চি সিকোয়েন্সটি এভাবে ডিফাইন করা:

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$

সিকোয়েন্সের প্রথম কয়েকটি পদ (OEIS A000045):

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$$

বৈশিষ্ট্য#

ফিবোনাচ্চি সংখ্যাগুলোর অনেক আকর্ষণীয় বৈশিষ্ট্য রয়েছে। এখানে কয়েকটি উল্লেখ করা হলো:

  • ক্যাসিনির অভেদ (Cassini’s identity):
$$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$

এটা আরোহ পদ্ধতিতে (induction) প্রুফ করা যায়। নুথ (Knuth) কর্তৃক একটি এক-লাইনের প্রুফ পাওয়া যায়, যেটা নিচে দেওয়া ২x২ ম্যাট্রিক্স ফর্মের ডিটারমিন্যান্ট থেকে আসে।

  • “যোগের” নিয়ম:
$$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$$
  • উপরের অভেদটিতে $k = n$ বসালে আমরা পাই:
$$F_{2n} = F_n (F_{n+1} + F_{n-1})$$

  • এটা থেকে আরোহ পদ্ধতিতে প্রুফ করা যায় যে, যেকোনো ধনাত্মক পূর্ণসংখ্যা $k$-এর জন্য $F_{nk}$, $F_n$-এর গুণিতক।

  • বিপরীতটিও সত্য: যদি $F_m$, $F_n$-এর গুণিতক হয়, তাহলে $m$, $n$-এর গুণিতক।

  • GCD অভেদ:

$$GCD(F_m, F_n) = F_{GCD(m, n)}$$
  • ইউক্লিডীয় অ্যালগরিদমের জন্য ফিবোনাচ্চি সংখ্যাগুলো সবচেয়ে খারাপ ইনপুট (লেমির থিওরেম দেখো ইউক্লিডীয় অ্যালগরিদম-এ)

ফিবোনাচ্চি কোডিং#

আমরা এই সিকোয়েন্সটি ব্যবহার করে ধনাত্মক পূর্ণসংখ্যাগুলোকে বাইনারি কোডওয়ার্ডে এনকোড করতে পারি। জেকেনডর্ফের থিওরেম (Zeckendorf’s theorem) অনুসারে, যেকোনো স্বাভাবিক সংখ্যা $n$-কে ফিবোনাচ্চি সংখ্যাগুলোর যোগফল হিসেবে অনন্যভাবে প্রকাশ করা যায়:

$$N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}$$

যেখানে $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2$ (অর্থাৎ, এই উপস্থাপনে পরপর দুটি ফিবোনাচ্চি সংখ্যা ব্যবহার করা যাবে না)।

এটা থেকে বোঝা যায় যে, যেকোনো সংখ্যাকে ফিবোনাচ্চি কোডিং-এ অনন্যভাবে এনকোড করা সম্ভব। এবং আমরা এই উপস্থাপনটিকে বাইনারি কোড $d_0 d_1 d_2 \dots d_s 1$ দিয়ে বর্ণনা করতে পারি, যেখানে $d_i$ হলো $1$ যদি $F_{i+2}$ উপস্থাপনে ব্যবহৃত হয়। কোডওয়ার্ডের শেষ নির্দেশ করতে একটি $1$ যোগ করা হয়। লক্ষ্য কর, এটিই একমাত্র স্থান যেখানে পরপর দুটি 1-বিট দেখা যায়।

$$\begin{eqnarray} 1 &=& 1 &=& F_2 &=& (11)_F \\ 2 &=& 2 &=& F_3 &=& (011)_F \\ 6 &=& 5 + 1 &=& F_5 + F_2 &=& (10011)_F \\ 8 &=& 8 &=& F_6 &=& (000011)_F \\ 9 &=& 8 + 1 &=& F_6 + F_2 &=& (100011)_F \\ 19 &=& 13 + 5 + 1 &=& F_7 + F_5 + F_2 &=& (1001011)_F \end{eqnarray}$$

একটি পূর্ণসংখ্যা $n$-এর এনকোডিং একটি সহজ গ্রিডি অ্যালগরিদম দিয়ে করা যায়:

১. সবচেয়ে বড় থেকে সবচেয়ে ছোট ফিবোনাচ্চি সংখ্যাগুলোর মধ্যে দিয়ে ইটারেট করো যতক্ষণ না $n$-এর সমান বা ছোট একটি সংখ্যা পাওয়া যায়।

২. ধরো সেই সংখ্যাটি $F_i$। $n$ থেকে $F_i$ বিয়োগ করো এবং কোডওয়ার্ডের $i-2$ অবস্থানে একটি $1$ বসান (বাম থেকে ডানে ০ থেকে ইনডেক্সিং)।

৩. বাকি না থাকা পর্যন্ত পুনরাবৃত্তি করো।

৪. কোডওয়ার্ডের শেষে একটি $1$ যোগ করো এর শেষ নির্দেশ করতে।

একটি কোডওয়ার্ড ডিকোড করতে, প্রথমে শেষের $1$ সরিয়ে ফেলুন। তারপর, যদি $i$-তম বিট সেট থাকে (বাম থেকে ডানে ০ থেকে ইনডেক্সিং), তাহলে সংখ্যাটির সাথে $F_{i+2}$ যোগ করো।

$n^{\text{th}}$ ফিবোনাচ্চি সংখ্যার সূত্রসমূহ#

ক্লোজড-ফর্ম এক্সপ্রেশন#

একটি সূত্র আছে যা “বিনের সূত্র” (Binet’s formula) নামে পরিচিত, যদিও এটা আগে থেকেই ময়ভ্র (Moivre) জানতেন:

$$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

এই সূত্রটি আরোহ পদ্ধতিতে সহজেই প্রুফ করা যায়, তবে এটা জেনারেটিং ফাংশনের ধারণা বা একটি ফাংশনাল ইকুয়েশন সমাধানের মাধ্যমেও বের করা সম্ভব।

সহজেই লক্ষ্য করা যায় যে দ্বিতীয় পদের পরম মান সর্বদা $1$-এর চেয়ে কম, এবং এটা অত্যন্ত দ্রুত (সূচকীয়ভাবে) হ্রাস পায়। তাই শুধু প্রথম পদের মানই “প্রায়” $F_n$-এর সমান। এটা কঠোরভাবে লেখা যায়:

$$F_n = \left[\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right]$$

যেখানে তৃতীয় বন্ধনী নিকটতম পূর্ণসংখ্যায় রাউন্ডিং বোঝায়।

এই দুটি সূত্রে ফ্র্যাকশন সংখ্যা নিয়ে কাজ করতে খুব উচ্চ নির্ভুলতা প্রয়োজন হওয়ায়, ব্যবহারিক গণনায় এগুলো তেমন কাজে আসে না।

লিনিয়ার সময়ে ফিবোনাচ্চি#

$n$-তম ফিবোনাচ্চি সংখ্যা সহজেই $O(n)$ সময়ে বের করা যায়, একটি একটি করে $n$ পর্যন্ত গণনা করে। তবে আরও দ্রুত পদ্ধতিও আছে, যা আমরা পরে দেখব।

আমরা একটি ইটারেটিভ পদ্ধতি থেকে শুরু করতে পারি, $F_n = F_{n-1} + F_{n-2}$ সূত্রটি ব্যবহার করে। তাই আমরা মানগুলো একটি অ্যারেতে আগে থেকে গণনা করে রাখব। $F_0$ এবং $F_1$-এর বেস কেস কনসিডার করে:

int fib(int n) {
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return a;
}

এভাবে আমরা একটি লিনিয়ার সমাধান পাই, $O(n)$ সময়ে, সিকোয়েন্সের $n$-এর আগের সব মান সংরক্ষণ করে।

ম্যাট্রিক্স ফর্ম#

$(F_n, F_{n-1})$ থেকে $(F_{n+1}, F_n)$-এ যেতে, আমরা এই লিনিয়ার রিকারেন্সটিকে একটি ২x২ ম্যাট্রিক্স গুণ হিসেবে প্রকাশ করতে পারি:

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} F_n + F_{n-1} \\ F_{n} \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} $$

এটা আমাদের রিকারেন্সের ইটারেশনকে বারবার ম্যাট্রিক্স গুণ হিসেবে কনসিডার করতে দেয়, যার চমৎকার বৈশিষ্ট্য রয়েছে। বিশেষত,

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} $$

যেখানে $F_1 = 1, F_0 = 0$। আসলে, যেহেতু

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix} $$

আমরা সরাসরি ম্যাট্রিক্সটি ব্যবহার করতে পারি:

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} $$

সুতরাং, $O(\log n)$ সময়ে $F_n$ বের করতে আমাদের ম্যাট্রিক্সটিকে n-তম ঘাতে উন্নীত করতে হবে। (দেখো বাইনারি এক্সপোনেনশিয়েশন)

struct matrix {
    long long mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 2; k++) {
                  c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, long long n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}

long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}

ফাস্ট ডাবলিং মেথড#

উপরের ম্যাট্রিক্স এক্সপ্রেশনটি $n = 2\cdot k$-এর জন্য বিস্তৃত করলে

$$ \begin{pmatrix} F_{2k+1} & F_{2k}\\ F_{2k} & F_{2k-1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{2k} = \begin{pmatrix} F_{k+1} & F_{k}\\ F_{k} & F_{k-1} \end{pmatrix} ^2 $$

আমরা এই সরলতর ইকুয়েশনগুলো পাই:

$$ \begin{align} F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \\ F_{2k} &= F_k(F_{k+1}+F_{k-1}) = F_k (2F_{k+1} - F_{k})\\ \end{align}.$$

এভাবে উপরের দুটি ইকুয়েশন ব্যবহার করে ফিবোনাচ্চি সংখ্যা সহজেই নিচের কোড দিয়ে গণনা করা যায়:

pair<int, int> fib (int n) {
    if (n == 0)
        return {0, 1};

    auto p = fib(n >> 1);
    int c = p.first * (2 * p.second - p.first);
    int d = p.first * p.first + p.second * p.second;
    if (n & 1)
        return {d, c + d};
    else
        return {c, d};
}

উপরের কোডটি একটি পেয়ার হিসেবে $F_n$ এবং $F_{n+1}$ রিটার্ন করে।

p দ্বারা মডুলোতে পর্যায়ক্রমিকতা#

ফিবোনাচ্চি সিকোয়েন্সটি $p$ মডুলোতে কনসিডার করি। আমরা প্রুফ করব যে সিকোয়েন্সটি পর্যায়ক্রমিক (periodic)।

চলো এটা পরোক্ষ প্রুফের (contradiction) মাধ্যমে দেখাই। $p$ মডুলোতে নেওয়া প্রথম $p^2 + 1$ জোড়া ফিবোনাচ্চি সংখ্যা কনসিডার করো:

$$(F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{p^2},\ F_{p^2 + 1})$$

$p$ মডুলোতে মাত্র $p$ ধরনের ভাগশেষ সম্ভব, এবং সর্বোচ্চ $p^2$ ধরনের ভাগশেষের জোড়া সম্ভব, তাই এদের মধ্যে অন্তত দুটি অভিন্ন জোড়া থাকবে। এটা সিকোয়েন্সটি যে পর্যায়ক্রমিক তা প্রুফের জন্য যথেষ্ট, কারণ একটি ফিবোনাচ্চি সংখ্যা শুধুমাত্র তার আগের দুটি সংখ্যা দ্বারা নির্ধারিত হয়। অতএব, যদি পরপর দুটি সংখ্যার দুটি জোড়া পুনরাবৃত্ত হয়, তাহলে জোড়ার পরের সংখ্যাগুলোও একই ধাঁচে পুনরাবৃত্ত হবে।

এখন আমরা সিকোয়েন্সে ক্ষুদ্রতম সূচকবিশিষ্ট দুটি অভিন্ন ভাগশেষের জোড়া বেছে নিই। ধরো জোড়া দুটি হলো $(F_a,\ F_{a + 1})$ এবং $(F_b,\ F_{b + 1})$। আমরা প্রুফ করব যে $a = 0$। যদি এটা মিথ্যা হতো, তাহলে দুটি আগের জোড়া $(F_{a-1},\ F_a)$ এবং $(F_{b-1},\ F_b)$ থাকত, যেগুলো ফিবোনাচ্চি সংখ্যার বৈশিষ্ট্য অনুসারে সমান হতো। কিন্তু এটা আমাদের ক্ষুদ্রতম সূচকের জোড়া বেছে নেওয়ার শর্তের সাথে সাংঘর্ষিক, যা প্রুফ করে যে কোনো পূর্ব-পর্যায় (pre-period) নেই (অর্থাৎ সংখ্যাগুলো $F_0$ থেকেই পর্যায়ক্রমিক)।

অনুশীলন সমস্যা#