স্টার্ন-ব্রকট ট্রি এবং ফ্যারে সিকোয়েন্স#
স্টার্ন-ব্রকট ট্রি#
স্টার্ন-ব্রকট ট্রি হলো সমস্ত ধনাত্মক ভগ্নাংশের সেটকে উপস্থাপন করার একটি মার্জিত গঠন। এটি স্বতন্ত্রভাবে আবিষ্কার করেছিলেন জার্মান গণিতবিদ মরিৎস স্টার্ন ১৮৫৮ সালে এবং ফরাসি ঘড়ি নির্মাতা আশিল ব্রকট ১৮৬১ সালে। তবে, কিছু উৎস এই আবিষ্কারকে প্রাচীন গ্রিক গণিতবিদ এরাটোস্থেনিসকে আরোপ করে।
গঠনটি শূন্যতম ইটারেশনে দুটি ভগ্নাংশ দিয়ে শুরু হয়
$$ \frac{0}{1}, \frac{1}{0} $$যেখানে লক্ষণীয় যে দ্বিতীয় রাশিটি কঠোরভাবে একটি ভগ্নাংশ নয়, কিন্তু এটিকে অসীমকে উপস্থাপনকারী একটি অপরিবর্তনীয় ভগ্নাংশ হিসেবে ব্যাখ্যা করা যেতে পারে।
প্রতিটি পরবর্তী ইটারেশনে, সমস্ত সন্নিহিত ভগ্নাংশ $\frac{a}{b}$ এবং $\frac{c}{d}$ বিবেচনা করুন এবং তাদের মধ্যে তাদের মিডিয়ান্ট $\frac{a+c}{b+d}$ সন্নিবেশ করুন।
প্রথম কয়েকটি ইটারেশন এরকম দেখায়:
$$ \begin{array}{c} \dfrac{0}{1}, \dfrac{1}{1}, \dfrac{1}{0} \\ \dfrac{0}{1}, \dfrac{1}{2}, \dfrac{1}{1}, \dfrac{2}{1}, \dfrac{1}{0} \\ \dfrac{0}{1}, \dfrac{1}{3}, \dfrac{1}{2}, \dfrac{2}{3}, \dfrac{1}{1}, \dfrac{3}{2}, \dfrac{2}{1}, \dfrac{3}{1}, \dfrac{1}{0} \end{array} $$এই প্রক্রিয়াটি অসীম পর্যন্ত চালিয়ে গেলে এটি সমস্ত ধনাত্মক ভগ্নাংশ কভার করে। অতিরিক্তভাবে, সমস্ত ভগ্নাংশ অনন্য এবং অপরিবর্তনীয় হবে। পরিশেষে, ভগ্নাংশগুলো ঊর্ধ্বক্রমেও প্রদর্শিত হবে।
এই বৈশিষ্ট্যগুলো প্রমাণ করার আগে, আসুন তালিকা উপস্থাপনার বদলে স্টার্ন-ব্রকট ট্রি-র একটি ভিজ্যুয়ালাইজেশন দেখি। ট্রি-তে প্রতিটি ভগ্নাংশের দুটি চাইল্ড আছে। প্রতিটি চাইল্ড হলো বামের নিকটতম পূর্বসূরি এবং ডানের নিকটতম পূর্বসূরির মিডিয়ান্ট।
প্রমাণসমূহ#
ক্রম। ক্রম প্রমাণ করা সহজ। আমরা লক্ষ্য করি যে দুটি ভগ্নাংশের মিডিয়ান্ট সবসময় ভগ্নাংশ দুটির মাঝে থাকে
$$ \frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d} $$যদি
$$ \frac{a}{b} \le \frac{c}{d}. $$দুটি অসমতাই সাধারণ হর দিয়ে ভগ্নাংশগুলো পুনঃলিখন করে সহজেই দেখানো যায়।
যেহেতু শূন্যতম ইটারেশনে ক্রম ঊর্ধ্বমুখী, তাই প্রতিটি পরবর্তী ইটারেশনে এটি বজায় থাকবে।
অপরিবর্তনীয়তা। এটি প্রমাণ করতে আমরা দেখাব যে যেকোনো দুটি সন্নিহিত ভগ্নাংশ $\frac{a}{b}$ এবং $\frac{c}{d}$-এর জন্য
$$ bc - ad = 1. $$মনে রাখুন যে দুটি চলকের একটি ডায়োফ্যান্টাইন সমীকরণ $ax+by=c$-এর সমাধান থাকে যদি এবং কেবল যদি $c$, $\gcd(a,b)$-এর গুণিতক হয়। আমাদের ক্ষেত্রে এটা বোঝায় যে $\gcd(a,b) = \gcd(c,d) = 1$, যা আমরা দেখাতে চাই।
স্পষ্টতই শূন্যতম ইটারেশনে $bc - ad = 1$। যা দেখানো বাকি তা হলো মিডিয়ান্টগুলো এই বৈশিষ্ট্য বজায় রাখে।
ধরি আমাদের দুটি সন্নিহিত ভগ্নাংশ $bc - ad = 1$ বজায় রাখে, তালিকায় মিডিয়ান্ট যোগ করার পর
$$ \frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d} $$নতুন রাশিগুলো হয়
$$\begin{align} b(a+c) - a(b+d) &= 1 \\ c(b+d) - d(a+c) &= 1 \end{align}$$যা, $bc-ad=1$ ব্যবহার করে, সহজেই সত্য দেখানো যায়।
এখান থেকে আমরা দেখি যে বৈশিষ্ট্যটি সবসময় বজায় থাকে এবং তাই সমস্ত ভগ্নাংশ অপরিবর্তনীয়।
সমস্ত ভগ্নাংশের উপস্থিতি। এই প্রমাণটি স্টার্ন-ব্রকট ট্রি-তে একটি ভগ্নাংশ খুঁজে বের করার সাথে ঘনিষ্ঠভাবে সম্পর্কিত। ক্রম বৈশিষ্ট্য থেকে আমরা পাই যে একটি ভগ্নাংশের বাম সাবট্রিতে শুধুমাত্র প্যারেন্ট ভগ্নাংশের চেয়ে ছোট ভগ্নাংশ থাকে, এবং ডান সাবট্রিতে শুধুমাত্র প্যারেন্ট ভগ্নাংশের চেয়ে বড় ভগ্নাংশ থাকে। এর মানে আমরা রুট থেকে ট্রি-তে ট্রাভার্স করে একটি ভগ্নাংশ অনুসন্ধান করতে পারি, লক্ষ্য বর্তমান ভগ্নাংশের চেয়ে ছোট হলে বামে এবং লক্ষ্য বড় হলে ডানে যাই।
একটি ইচ্ছামতো ধনাত্মক লক্ষ্য ভগ্নাংশ $\frac{x}{y}$ নিন। এটি স্পষ্টতই $\frac{0}{1}$ এবং $\frac{1}{0}$-এর মধ্যে, তাই ট্রি-তে ভগ্নাংশটি না থাকার একমাত্র উপায় হলো এটিতে পৌঁছাতে অসীম সংখ্যক ধাপ লাগা।
যদি তা হয় তাহলে সমস্ত ইটারেশনে আমাদের থাকবে
$$ \frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d} $$যা (একটি পূর্ণসংখ্যা $z \gt 0 \iff z \ge 1$ তথ্য ব্যবহার করে) পুনঃলিখন করা যায়
$$ \begin{align} bx - ay &\ge 1 \\ cy - dx &\ge 1. \end{align} $$এখন প্রথম অসমতাকে $c+d$ দিয়ে এবং দ্বিতীয়টিকে $a+b$ দিয়ে গুণ করে যোগ করলে পাই
$$ (c+d)(bx - ay) + (a+b)(cy - dx) \ge a+b+c+d. $$এটি বিস্তৃত করে এবং পূর্বে দেখানো $bc-ad=1$ বৈশিষ্ট্য ব্যবহার করে আমরা পাই
$$ x+y \ge a+b+c+d. $$এবং যেহেতু প্রতিটি ইটারেশনে $a,b,c,d$-এর অন্তত একটি বাড়বে, তাই ভগ্নাংশ অনুসন্ধান প্রক্রিয়ায় $x+y$-এর বেশি ইটারেশন থাকবে না। এটি $\frac{x}{y}$-এ যাওয়ার পথ অসীম ছিল এমন ধারণার সাথে সাংঘর্ষিক এবং তাই $\frac{x}{y}$ অবশ্যই ট্রি-র অংশ।
ট্রি নির্মাণ অ্যালগরিদম#
স্টার্ন-ব্রকট ট্রি-র যেকোনো সাবট্রি নির্মাণ করতে, বাম এবং ডান পূর্বসূরি জানাই যথেষ্ট। প্রথম লেভেলে, বাম এবং ডান পূর্বসূরি হলো যথাক্রমে $\frac{0}{1}$ এবং $\frac{1}{0}$। এগুলো ব্যবহার করে, আমরা মিডিয়ান্ট গণনা করি এবং একটি লেভেল গভীরে যাই, যেখানে বাম সাবট্রিতে মিডিয়ান্ট ডান পূর্বসূরিকে প্রতিস্থাপন করে, এবং উল্টোটাও।
এই সুডোকোড সম্পূর্ণ অসীম ট্রি নির্মাণের চেষ্টা করে:
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
int x = a + c, y = b + d;
... output the current fraction x/y at the current level in the tree
build(a, b, x, y, level + 1);
build(x, y, c, d, level + 1);
}ভগ্নাংশ অনুসন্ধান অ্যালগরিদম#
অনুসন্ধান অ্যালগরিদমটি ইতোমধ্যেই সমস্ত ভগ্নাংশ ট্রি-তে প্রদর্শিত হওয়ার প্রমাণে বর্ণিত হয়েছে, কিন্তু আমরা এটি এখানে পুনরাবৃত্তি করব। অ্যালগরিদমটি একটি বাইনারি সার্চ অ্যালগরিদম। প্রাথমিকভাবে আমরা ট্রি-র রুটে দাঁড়াই এবং আমাদের লক্ষ্যকে বর্তমান ভগ্নাংশের সাথে তুলনা করি। যদি তারা একই হয় তাহলে আমরা প্রক্রিয়া শেষ করি। আমাদের লক্ষ্য ছোট হলে বাম চাইল্ডে যাই, অন্যথায় ডান চাইল্ডে যাই।
সরল অনুসন্ধান#
এখানে একটি ইমপ্লিমেন্টেশন দেওয়া হলো যা একটি প্রদত্ত ভগ্নাংশ $\frac{p}{q}$-এ পৌঁছানোর পথকে 'L' এবং 'R' ক্যারেক্টারের সিকোয়েন্স হিসেবে রিটার্ন করে, যথাক্রমে বাম এবং ডান চাইল্ডে ট্রাভার্সাল বোঝায়। ক্যারেক্টারের এই সিকোয়েন্স সমস্ত ধনাত্মক ভগ্নাংশকে অনন্যভাবে সংজ্ঞায়িত করে এবং একে স্টার্ন-ব্রকট সংখ্যা পদ্ধতি বলা হয়।
string find(int p, int q) {
int pL = 0, qL = 1;
int pR = 1, qR = 0;
int pM = 1, qM = 1;
string res;
while(pM != p || qM != q) {
if(p * qM < pM * q) {
res += 'L';
tie(pR, qR) = {pM, qM};
} else {
res += 'R';
tie(pL, qL) = {pM, qM};
}
tie(pM, qM) = pair{pL + pR, qL + qR};
}
return res;
}স্টার্ন-ব্রকট সংখ্যা পদ্ধতিতে অমূলদ সংখ্যা ক্যারেক্টারের অসীম সিকোয়েন্সের সাথে সম্পর্কিত। অমূলদ সংখ্যার দিকে অসীম পথ ধরে অ্যালগরিদম ক্রমবর্ধমান বড় হরবিশিষ্ট সরলীকৃত ভগ্নাংশ খুঁজে পাবে যা অমূলদ সংখ্যার ক্রমশ উন্নততর আসন্নমান প্রদান করে। তাই অসীম সিকোয়েন্সের একটি প্রিফিক্স নিয়ে যেকোনো কাঙ্ক্ষিত নির্ভুলতা অর্জন করা যায়। এই অ্যাপ্লিকেশনটি ঘড়ি নির্মাণে গুরুত্বপূর্ণ, যা ব্যাখ্যা করে কেন ট্রিটি সেই ক্ষেত্রে আবিষ্কৃত হয়েছিল।
লক্ষ্য করুন যে একটি ভগ্নাংশ $\frac{p}{q}$-এর জন্য, ফলাফল সিকোয়েন্সের দৈর্ঘ্য $O(p+q)$ পর্যন্ত বড় হতে পারে, উদাহরণস্বরূপ যখন ভগ্নাংশটি $\frac{p}{1}$ আকারের। এর মানে উপরের অ্যালগরিদম ব্যবহার করা উচিত নয়, যদি না এই কমপ্লেক্সিটি গ্রহণযোগ্য হয়!
লগারিদমিক অনুসন্ধান#
সৌভাগ্যবশত, উপরের অ্যালগরিদমকে $O(\log (p+q))$ কমপ্লেক্সিটি নিশ্চিত করতে উন্নত করা সম্ভব। এজন্য আমাদের লক্ষ্য করা উচিত যে বর্তমান সীমানা ভগ্নাংশ $\frac{p_L}{q_L}$ এবং $\frac{p_R}{q_R}$ হলে, $a$ ধাপ ডানে গেলে আমরা $\frac{p_L + a p_R}{q_L + a q_R}$ ভগ্নাংশে পৌঁছাই, এবং $a$ ধাপ বামে গেলে $\frac{a p_L + p_R}{a q_L + q_R}$ ভগ্নাংশে পৌঁছাই।
অতএব, একবারে একটি করে L বা R ধাপ না নিয়ে, আমরা একই দিকে একবারে $k$ ধাপ নিতে পারি, তারপর অন্য দিকে যেতে শুরু করব, ইত্যাদি। এভাবে, আমরা ভগ্নাংশ $\frac{p}{q}$-এর পথটিকে এর রান-লেংথ এনকোডিং হিসেবে খুঁজে পেতে পারি।
যেহেতু দিকগুলো এভাবে পর্যায়ক্রমে পরিবর্তিত হয়, আমরা সবসময় জানব কোনটি নিতে হবে। তাই, সুবিধার জন্য আমরা একটি ভগ্নাংশ $\frac{p}{q}$-এর পথকে ভগ্নাংশের সিকোয়েন্স হিসেবে উপস্থাপন করতে পারি
$$ \frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots, \frac{p_n}{q_n}, \frac{p_{n+1}}{q_{n+1}} = \frac{p}{q} $$এমনভাবে যে $\frac{p_{k-1}}{q_{k-1}}$ এবং $\frac{p_k}{q_k}$ হলো $k$-তম ধাপে অনুসন্ধান ব্যবধানের সীমানা, $\frac{p_0}{q_0} = \frac{0}{1}$ এবং $\frac{p_1}{q_1} = \frac{1}{0}$ দিয়ে শুরু করে। তারপর, $k$-তম ধাপের পরে আমরা একটি ভগ্নাংশে পৌঁছাই
$$ \frac{p_{k+1}}{q_{k+1}} = \frac{p_{k-1} + a_k p_k}{q_{k-1} + a_k q_k}, $$যেখানে $a_k$ একটি ধনাত্মক পূর্ণসংখ্যা। আপনি যদি সন্তত ভগ্নাংশ-এর সাথে পরিচিত হন, তাহলে চিনতে পারবেন যে $\frac{p_i}{q_i}$ সিকোয়েন্সটি হলো $\frac{p}{q}$-এর অভিসারী ভগ্নাংশের সিকোয়েন্স এবং $[a_1; a_2, \dots, a_{n}, 1]$ সিকোয়েন্সটি $\frac{p}{q}$-এর সন্তত ভগ্নাংশ উপস্থাপনা।
এটি ভগ্নাংশ $\frac{p}{q}$-এর সন্তত ভগ্নাংশ উপস্থাপনা গণনার অ্যালগরিদম অনুসরণ করে $\frac{p}{q}$-এর পথের রান-লেংথ এনকোডিং খুঁজে বের করতে দেয়:
auto find(int p, int q) {
bool right = true;
vector<pair<int, char>> res;
while(q) {
res.emplace_back(p / q, right ? 'R' : 'L');
tie(p, q) = pair{q, p % q};
right ^= 1;
}
res.back().first--;
return res;
}তবে, এই পদ্ধতি কেবল তখনই কাজ করে যখন আমরা ইতোমধ্যেই $\frac{p}{q}$ জানি এবং স্টার্ন-ব্রকট ট্রি-তে এর অবস্থান খুঁজতে চাই।
বাস্তবে, প্রায়ই $\frac{p}{q}$ আগে থেকে জানা থাকে না, কিন্তু আমরা নির্দিষ্ট $\frac{x}{y}$-এর জন্য পরীক্ষা করতে পারি $\frac{x}{y} < \frac{p}{q}$ কি না।
এটি জেনে, আমরা বর্তমান সীমানা $\frac{p_{k-1}}{q_{k-1}}$ এবং $\frac{p_k}{q_k}$ রক্ষণাবেক্ষণ করে স্টার্ন-ব্রকট ট্রি-তে অনুসন্ধান অনুকরণ করতে পারি, এবং প্রতিটি $a_k$ বাইনারি সার্চের মাধ্যমে খুঁজে বের করতে পারি। তখন অ্যালগরিদমটি একটু বেশি টেকনিক্যাল এবং সম্ভাব্যভাবে $O(\log^2(x+y))$ কমপ্লেক্সিটির হবে, যদি না সমস্যার গঠন আপনাকে দ্রুত $a_k$ খুঁজে বের করতে দেয় (উদাহরণস্বরূপ, কোনো পরিচিত রাশির floor ব্যবহার করে)।
ফ্যারে সিকোয়েন্স#
$n$-তম ক্রমের ফ্যারে সিকোয়েন্স হলো $0$ এবং $1$-এর মধ্যে ভগ্নাংশগুলোর সাজানো সিকোয়েন্স যাদের হর $n$-এর বেশি নয়।
সিকোয়েন্সগুলো ইংরেজ ভূতত্ত্ববিদ জন ফ্যারে-র নামে নামকরণ করা হয়েছে, যিনি ১৮১৬ সালে অনুমান করেছিলেন যে একটি ফ্যারে সিকোয়েন্সের যেকোনো ভগ্নাংশ তার প্রতিবেশীদের মিডিয়ান্ট। এটি কিছু সময় পরে কশি দ্বারা প্রমাণিত হয়েছিল, কিন্তু তাদের উভয়ের থেকে স্বতন্ত্রভাবে, গণিতবিদ হ্যারোস ১৮০২ সালে প্রায় একই সিদ্ধান্তে পৌঁছেছিলেন।
ফ্যারে সিকোয়েন্সের নিজস্ব অনেক আকর্ষণীয় বৈশিষ্ট্য আছে, কিন্তু স্টার্ন-ব্রকট ট্রি-র সাথে সংযোগটিই সবচেয়ে সুস্পষ্ট। প্রকৃতপক্ষে, ট্রি থেকে শাখা ছেঁটে ফেলে ফ্যারে সিকোয়েন্স পাওয়া যেতে পারে।
স্টার্ন-ব্রকট ট্রি নির্মাণের অ্যালগরিদম থেকে, আমরা ফ্যারে সিকোয়েন্সের জন্য একটি অ্যালগরিদম পাই। ভগ্নাংশের তালিকা $\frac{0}{1}, \frac{1}{0}$ দিয়ে শুরু করুন। প্রতিটি পরবর্তী ইটারেশনে, মিডিয়ান্ট কেবল তখনই সন্নিবেশ করুন যদি হর $n$-এর বেশি না হয়। কোনো এক সময়ে তালিকা পরিবর্তন হওয়া বন্ধ হবে এবং কাঙ্ক্ষিত ফ্যারে সিকোয়েন্স পাওয়া যাবে।
ফ্যারে সিকোয়েন্সের দৈর্ঘ্য#
$n$-তম ক্রমের একটি ফ্যারে সিকোয়েন্সে $n-1$-তম ক্রমের ফ্যারে সিকোয়েন্সের সমস্ত উপাদান রয়েছে সেইসাথে $n$ হরবিশিষ্ট সমস্ত অপরিবর্তনীয় ভগ্নাংশ রয়েছে, কিন্তু পরেরটি হলো টোশেন্ট $\varphi(n)$। তাই $n$-তম ক্রমের ফ্যারে সিকোয়েন্সের দৈর্ঘ্য $L_n$ হলো
$$ L_n = L_{n-1} + \varphi(n) $$অথবা সমতুল্যভাবে, রিকার্সন উন্মোচন করলে আমরা পাই
$$ L_n = 1 + \sum_{k=1}^n \varphi(k). $$