স্টার্ন-ব্রকট ট্রি এবং ফ্যারে সিকোয়েন্স#
স্টার্ন-ব্রকট ট্রি#
স্টার্ন-ব্রকট ট্রি হলো সমস্ত ধনাত্মক ফ্র্যাকশনের সেটকে উপস্থাপন করার একটি মার্জিত গঠন। এটা স্বতন্ত্রভাবে আবিষ্কার করেছিলেন জার্মান গণিতবিদ মরিৎস স্টার্ন ১৮৫৮ সালে এবং ফরাসি ঘড়ি নির্মাতা আশিল ব্রকট ১৮৬১ সালে। তবে, কিছু উৎস এই আবিষ্কারকে প্রাচীন গ্রিক গণিতবিদ এরাটোস্থেনিসকে আরোপ করে।
গঠনটি শূন্যতম ইটারেশনে দুটি ফ্র্যাকশন দিয়ে শুরু হয়
$$ \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). $$