شجرة البروكلي

في نظرية الأعداد ، شجرة ستيرن-بروكوت هي شجرة ثنائية كاملة لا نهائية تتوافق رؤوسها واحد لواحد مع الأعداد النسبية الموجبة ، والتي يتم ترتيب قيمها من اليسار إلى اليمين كما هو الحال في شجرة البحث الثنائية .

طُرحت شجرة شتيرن-بروكوت بشكل مستقل من قبل موريتز شتيرن ( 1858 ) وأكيل بروكوت ( 1861 ) . كان شتيرن عالمًا ألمانيًا في نظرية الأعداد؛ أما بروكوت فكان صانع ساعات فرنسيًا استخدم شجرة شتيرن-بروكوت لتصميم أنظمة تروس بنسبة تروس قريبة من قيمة معينة مرغوبة عن طريق إيجاد نسبة من الأعداد السلسة القريبة من تلك القيمة.  

يمثل جذر شجرة ستيرن-بروكوت العدد 1. ويمكن تعريف العلاقة بين الأعداد في هذه الشجرة باستخدام الكسور المستمرة البسيطة أو الوسائط ، حيث يوفر أي مسار في الشجرة من الجذر إلى أي عدد آخر q سلسلة من التقريبات للعدد q بمقامات أصغر منه . ولأن الشجرة تحتوي على كل عدد نسبي موجب مرة واحدة فقط، فإن البحث بالعرض أولاً في الشجرة يوفر طريقة لسرد جميع الأعداد النسبية الموجبة، وهي طريقة وثيقة الصلة بمتتاليات فاري . وتُسمى الشجرة الفرعية اليسرى لشجرة ستيرن-بروكوت، التي تحتوي على الأعداد النسبية في النطاق (0، 1) ، بشجرة فاري .

يمكن ربط كل رأس في الشجرة بثلاثية من الكسور تتكون من ثلاثة كسور في نفس صف الرأس، وهي: الكسر الموجود مباشرةً على يسار الرأس، والكسر الموجود عند الرأس نفسه، والكسر الموجود مباشرةً على يمين الرأس. (انظر الشكل أعلاه). لا يتوافق الكسران الأيسر والأيمن مع رؤوس في نفس صف الرأس، بل مع رؤوس في صف سابق. يمكن فهم كل كسر من هذه الكسور على أنه يُحدد منطقة المستوى المحصورة بين مسارين لانهائيين ينحدران من الرأس السابق الذي يحمل نفس الكسر. يكون العنصر الثاني من الثلاثية دائمًا هو الوسيط بين العنصرين الأول والثالث. على سبيل المثال، يرتبط الجذر بـ${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{1}},{\tfrac {1}{0}}{\bigr )}}$ويرتبط نسله الأيسر والأيمن بـ${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}{\bigr )}}$و${\displaystyle {\bigl (}{\tfrac {1}{1}},{\tfrac {2}{1}},{\tfrac {1}{0}}{\bigr )}.}$

يتم إنشاء الشجرة وفقًا للقاعدة التالية: $${\displaystyle {\begin{array}{ccccc}&&\left({\dfrac {a}{b}},{\dfrac {c}{d}},{\dfrac {e}{f}}\right)&&\\&\swarrow &&\searrow &\\\left({\dfrac {a}{b}},{\dfrac {a+c}{b+d}},{\dfrac {c}{d}}\right)&&&&\left({\dfrac {c}{d}},{\dfrac {c+e}{d+f}},{\dfrac {e}{f}}\right)\end{array}}}$$

يمكن فهم العلاقة بين الآباء والأبناء أيضًا من خلال الكسور المستمرة. يمكن التعبير عن كل عدد نسبي موجب q ككسر مستمر على الصورة التالية: $${\displaystyle q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}}=[a_{0};a_{1},a_{2},\ldots ,a_{k}]}$$ حيث k و a₀ عددان صحيحان غير سالبين، وكل معامل لاحق aᵢ عدد صحيح موجب. _{هذا التمثيل} ليس فريدًا لأن $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],}$$ لكن باستخدام هذا التكافؤ لاستبدال كل كسر مستمر ينتهي بالعدد واحد بكسر مستمر أقصر، يتضح أن لكل عدد نسبي تمثيلًا فريدًا يكون فيه المعامل الأخير أكبر من واحد. عندئذٍ، ما لم يكن q = 1 ، فإن للعدد q عددًا أصليًا في شجرة ستيرن-بروكوت يُعطى بتعبير الكسر المستمر. $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1].}$$وبالمثل ، يُشكَّل هذا الأصل عن طريق إنقاص المقام في الحد الداخلي للكسر المستمر بمقدار 1، ثم تقليصه مع الحد السابق  إذا أصبح الكسر 1/1 . على سبيل المثال، العدد النسبي 23/16 له تمثيل كسر مستمر $${\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}=[1;2,3,2],}$$ إذن، العنصر الأب في شجرة ستيرن-بروكوت هو الرقم $${\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13}{9}}.}$$

وعلى العكس من ذلك، فإن لكل عدد q في شجرة ستيرن-بروكوت ولدين بالضبط: إذا $${\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]}$$ إذن، طفل واحد هو العدد الذي يمثله الكسر المستمر $${\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]}$$ بينما يُمثل الطفل الآخر بالكسر المستمر $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].}$$ أحد هذين الكسرين أصغر من q وهو الكسر الأيسر؛ والآخر أكبر من q وهو الكسر الأيمن (في الواقع، تعطي الصيغة الأولى الكسر الأيسر إذا كان k فرديًا، والكسر الأيمن إذا كان k زوجيًا). على سبيل المثال، تمثيل الكسر المستمر 13/9 هو [1 ، 2، 4] ، وكسراه هما [1، 2، 5] = 16/11 (الكسر الأيمن ) و [1، 2، 3 ، 2 ] = 23/16 ( الكسر الأيسر ) .

_{من الواضح أنه لكل تعبير كسر مستمر محدود، يمكن الانتقال مرارًا وتكرارًا إلى أصله، والوصول إلى جذر الشجرة [1;] = 1/1 في عدد محدود من الخطوات (في a₀ + ... + aₖ} - 1 خطوة تحديدًا ) . ​​لذلك ، _يظهر كل عدد نسبي موجب مرة واحدة فقط في هذه الشجرة. علاوة على ذلك، فإن جميع أبناء الابن الأيسر لأي عدد q أصغر من q ، وجميع أبناء الابن الأيمن لـ q أكبر من q . الأعداد الموجودة على عمق d في الشجرة هي الأعداد التي يكون مجموع معاملات الكسر المستمر لها d + 1 .

تشكل شجرة ستيرن-بروكوت شجرة بحث ثنائية لا نهائية بالنسبة للترتيب المعتاد للأعداد النسبية. ^{[ 1 ] [ 2 ]} تُعرَّف مجموعة الأعداد النسبية المنحدرة من عقدة q بالفترة المفتوحة ( L _q , H _q ) ، حيث L _q هو سلف q الأصغر منه والأقرب إليه في الشجرة (أو L _q = 0 إذا لم يكن لـ q سلف أصغر منه)، بينما H _q هو سلف q الأكبر منه والأقرب إليه في الشجرة (أو H _q = +∞ إذا لم يكن لـ q سلف أكبر منه).

يمكن إيجاد المسار من الجذر 1 إلى العدد q في شجرة ستيرن-بروكوت باستخدام خوارزمية البحث الثنائي ، والتي يمكن التعبير عنها ببساطة باستخدام الوسائط . يتم توسيع مجموعة الأعداد النسبية غير السالبة لتشمل القيمة 1/0 ( التي تمثل +∞) وهي، بحكم تعريفها، أكبر من جميع الأعداد النسبية الأخرى. وتعمل خوارزمية البحث الثنائي على النحو التالي :

• قم بتهيئة قيمتين L و H إلى 0 / 1 و 1 / 0 على التوالي .
• إلى أن يتم العثور على قيمة q ، كرر الخطوات التالية:
  • ليكن L = a / b و H = c / d ؛ احسب الوسيط​​${\displaystyle M=L\oplus H={\frac {a+c}{b+d}}.}$
  • إذا كانت M أقل من q ، فإن q تقع في الفترة المفتوحة ( M ، H ) ؛ استبدل L بـ M واستمر.
  • إذا كانت M أكبر من q ، فإن q تقع في الفترة المفتوحة ( L ، M ) ؛ استبدل H بـ M واستمر.
  • في الحالة المتبقية، q = M ؛ قم بإنهاء خوارزمية البحث.

إن تسلسل القيم M المحسوب بواسطة هذا البحث هو بالضبط تسلسل القيم على المسار من الجذر إلى q في شجرة ستيرن-بروكوت. كل فترة مفتوحة ( L , H ) تظهر في أي خطوة من خطوات البحث هي الفترة ( LM , H ) التي تمثل أحفاد الوسيط M. _أما والد q في شجرة ستيرن-بروكوت فهو آخر وسيط _تم العثور عليه ولا يساوي q .

يمكن استخدام إجراء البحث الثنائي هذا لتحويل الأعداد العشرية إلى أعداد نسبية. بالتوقف عند الوصول إلى الدقة المطلوبة، يمكن تقريب الأعداد العشرية بدقة اختيارية. [3] إذا تم تقريب عدد حقيقي x بأي عدد نسبي a/ ^{b غير موجود} في متتالية الوسائط التي تم العثور عليها بواسطة الخوارزمية أعلاه، فإن متتالية الوسائط تحتوي على تقريب أدق لـ x بمقام لا يتجاوز b ؛ وبهذا المعنى، تُشكل هذه الوسائط أفضل التقريبات النسبية لـ x .

يمكن تعريف شجرة ستيرن-بروكوت مباشرةً بدلالة الوسيط: الابن الأيسر لأي عدد q هو وسيط q مع أقرب سلف أصغر منه، والابن الأيمن لـ q هو وسيط q مع أقرب سلف أكبر منه. في هذه الصيغة، يجب تبسيط كل من q وسلفه إلى أبسط صورة ، وإذا لم يكن هناك سلف أصغر أو أكبر ، فيُستخدم 0/1 أو 1/0 على التوالي . مرة أخرى، باستخدام 7 / 5 كمثال ، فإن أقرب سلف أصغر له هو 4 / 3 ، لذا فإن ابنه الأيسر هو 4 + 7 / 3 + 5 = 11 / 8 ، وأقرب سلف أكبر له هو 3 / 2 ، لذا فإن ابنه الأيمن هو 7 + 3 / 5 + 2 = 10 / 7 .

متتالية فاري من الرتبة n هي متتالية مرتبة من الكسور في الفترة المغلقة [0,1] التي يكون مقامها أقل من أو يساوي n . وكما هو الحال في تقنية البحث الثنائي لإنشاء شجرة ستيرن-بروكوت، يمكن إنشاء متتاليات فاري باستخدام الوسائط: تُشكل متتالية فاري من الرتبة n + 1 من متتالية فاري من الرتبة n بحساب وسيط كل قيمتين متتاليتين في متتالية فاري من الرتبة n ، مع الاحتفاظ بمجموعة الوسائط التي يكون مقامها مساويًا تمامًا لـ n + 1 ، ووضع هذه الوسائط بين القيمتين اللتين حُسبت منهما.

عملية مماثلة لإدخال الوسيط، تبدأ بزوج مختلف من نقاط نهاية الفاصل الزمني${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$يمكن أيضًا اعتبارها وصفًا لبناء الرؤوس في كل مستوى من مستويات شجرة ستيرن-بروكوت. متتالية ستيرن-بروكوت من الرتبة 0 هي المتتالية${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$ومتتالية ستيرن-بروكوت من الرتبة i هي المتتالية المتكونة من إدخال وسيط بين كل زوج متتالي من القيم في متتالية ستيرن-بروكوت من الرتبة i − 1. تتكون متتالية ستيرن-بروكوت من الرتبة i من جميع القيم في المستويات i الأولى من شجرة ستيرن-بروكوت، بالإضافة إلى القيم الحدية 0/1 و 1 / 0 ، مرتبة ترتيبًا عدديًا .

وبالتالي، تختلف متتابعات ستيرن-بروكوت عن متتابعات فاري في جانبين: فهي تشمل في النهاية جميع الأعداد النسبية الموجبة، وليس فقط الأعداد النسبية ضمن الفترة [0,1] ، وفي الخطوة n ، تُضمَّن جميع الوسائط، وليس فقط تلك التي مقامها يساوي n . ويمكن إيجاد متتابعة فاري من الرتبة n عن طريق اجتياز الشجرة الفرعية اليسرى لشجرة ستيرن-بروكوت بترتيب تصاعدي، مع التراجع كلما تم الوصول إلى عدد مقامه أكبر من n .

لو${\displaystyle {\tfrac {p_{1}}{q_{1}}},{\tfrac {p_{2}}{q_{2}}},\dots ,{\tfrac {p_{n}}{q_{n}}}}$إذا كانت جميع النسب العقلانية على نفس العمق في شجرة ستيرن-بروكوت،

$${\displaystyle \sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1.}$$

علاوة على ذلك، إذا${\displaystyle {\tfrac {p}{q}}<{\tfrac {p'}{q'}}}$إذا كان هناك كسران متتاليان عند مستوى معين أو أعلى منه في الشجرة (بمعنى أن أي كسر بينهما يجب أن يكون في مستوى أدنى من الشجرة)، فإن ^{[ 4 ]}

$${\displaystyle p'q-pq'=1.}$$

إلى جانب التعريفات المتعلقة بالكسور المستمرة والوسيط المذكورة أعلاه، يمكن تعريف شجرة ستيرن-بروكوت أيضًا على أنها شجرة ديكارتية للأعداد النسبية، مرتبة حسب مقاماتها. بعبارة أخرى، هي شجرة البحث الثنائية الوحيدة للأعداد النسبية التي يكون فيها مقام والد أي رأس q أصغر من مقام q (أو إذا كان كل من q ووالده عددين صحيحين، يكون مقام الوالد أصغر من مقام q ). ويترتب على نظرية الأشجار الديكارتية أن السلف المشترك الأدنى لأي عددين q و r في شجرة ستيرن-بروكوت هو العدد النسبي في الفترة المغلقة [ q , r ] الذي له أصغر مقام بين جميع الأعداد في هذه الفترة.

يؤدي تبديل رؤوس كل مستوى من شجرة ستيرن-بروكوت باستخدام تبديل عكس البتات إلى إنتاج شجرة مختلفة، وهي شجرة كالكين-ويلف ، حيث يكون أبناء كل عدد a / b هما العددان a / a + b و a + b / b . ومثل شجرة ستيرن-بروكوت ، تحتوي شجرة كالكين-ويلف على كل عدد نسبي موجب مرة واحدة فقط، ولكنها ليست شجرة بحث ثنائية.

• دالة علامة الاستفهام لمينكوفسكي ، التي يرتبط تعريفها للحجج العقلانية ارتباطًا وثيقًا بشجرة ستيرن-بروكوت
• شجرة كالكين-ويلف

• Brocot، Achille (1861)، “Calcul des rouages ​​par approximation، nouvelle méthode”، Revue Chronométrique ، 3 : 186– 194.
• بروكوت، أخيل (1862)، “حساب الألوان التقريبية، طريقة جديدة”، https://gallica.bnf.fr/ark:/12148/bpt6k1661912?rk=21459;2
• ستيرن، موريتز أ. ( 1858)، “Ueber eine zahlentheoretische Funktion” ، مجلة für die reine und angewandte Mathematik ، 55 : 193–220.
• بيرستل، جان؛ لوف، آرون؛ رويتناور، كريستوف؛ ساليولا، فرانكو ف. (2009)، التوافقية على الكلمات. كلمات كريستوفيل والتكرارات في الكلمات ، سلسلة دراسات CRM، المجلد  27، بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية ، ISBN 978-0-8218-4480-9، Zbl 1161.68043 

• أيلام، دروفا (2013)، تسلسلات ستيرن-بروكوت المعدلة ، arXiv : 1301.6807 ، Bibcode : 2013arXiv1301.6807A
• أوستن، ديفيد، الأشجار، الأسنان، والزمن: رياضيات صناعة الساعات ، مقال مميز من الجمعية الأمريكية للرياضيات
• بوغومولني، ألكسندر ، شجرة البروكوت ستيرن ، قطع العقدة ، تم الاسترجاع في 2008-09-03
• سلون، إن جيه إيه ، شجرة ستيرن-بروكوت أو فاري ، موسوعة تسلسلات الأعداد الصحيحة على الإنترنت.
• وايلدبرغر، نورمان (29 مايو 2012)، MF96: الكسور وشجرة ستيرن-بروكوت
• وايسشتاين، إريك دبليو ، "شجرة ستيرن-بروكوت" ، عالم الرياضيات
• شجرة ستيرن-بروكوت في بلانيت ماث .
• كود لإنشاء أشجار ستيرن-بروكوت على GitHub
• الكسور اللانهائية ، نامبرفايل
• رسومات بيانية مذهلة III ، عشاق الأرقام
• تسلسل OEIS A002487 (سلسلة ستيرن ثنائية الذرات (أو تسلسل ستيرن-بروكوت)) .