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

ফিবোনাচ্চি সিকোয়েন্সটি নিম্নরূপে সংজ্ঞায়িত:

$$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$ থেকেই পর্যায়ক্রমিক)।

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