تسلسل هوفستادتر

تُعرف متواليات هوفستاتر الشكلية (R و S) بأنها زوج من متواليات الأعداد الصحيحة المتكاملة على النحو التالي: ^{[ 1 ] [ 2 ]}

${\displaystyle {\begin{aligned}R(1)&=1,\ S(1)=2;\\R(n)&=R(n-1)+S(n-1),\quad n>1,\end{aligned}}}$

مع التسلسل${\displaystyle S(n)}$تُعرَّف بأنها سلسلة متزايدة تمامًا من الأعداد الصحيحة الموجبة غير الموجودة في${\displaystyle R(n)}$الحدود القليلة الأولى من هذه المتتاليات هي

R : 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260,  ... (التسلسل A005228 في OEIS )

S : 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25,  ... (التسلسل A030124 في OEIS )

يتم تعريف تسلسل هوفستاتر G على النحو التالي: ^{[ 3 ] [ 4 ]}

${\displaystyle {\begin{aligned}G(0)&=0,\\G(n)&=nG{\big (}G(n-1){\big )},\quad n>0.\end{aligned}}}$

الحدود القليلة الأولى من هذه المتتالية هي

0، 1، 1، 2، 3، 3، 4، 4، 5، 6، 6، 7، 8، 8، 9، 9، 10، 11، 11، 12، 12،  ... (التسلسل A005206 في OEIS )

يتم تعريف تسلسل هوفستاتر H على النحو التالي: ^{[ 3 ] [ 5 ]}

${\displaystyle {\begin{aligned}H(0)&=0,\\H(n)&=nH{\Big (}H{\big (}H(n-1){\big )}{\Big )},\quad n>0.\end{aligned}}}$

الحدود القليلة الأولى من هذه المتتالية هي

0، 1، 1، 2، 3، 4، 4، 5، 5، 6، 7، 7، 8، 9، 10، 10، 11، 12، 13، 13، 14،  ... (التسلسل A005374 في OEIS )

يتم تعريف تسلسلات هوفستاتر الأنثوية ( F ) والذكرية ( M ) على النحو التالي: ^{[ 3 ] [ 6 ]}

${\displaystyle {\begin{aligned}F(0)&=1,\ M(0)=0;\\F(n)&=nM{\big (}F(n-1){\big )},\quad n>0,\\M(n)&=nF{\big (}M(n-1){\big )},\quad n>0.\end{aligned}}}$

الحدود القليلة الأولى من هذه المتتاليات هي

F : 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13,  ... (التسلسل A005378 في OEIS )

M : 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12,  ... (التسلسل A005379 في OEIS )

يتم تعريف متتالية هوفستاتر Q على النحو التالي: ^{[ 3 ] [ 7 ]}

${\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}nQ(n-1){\big )}+Q{\big (}nQ(n-2){\big )},\quad n>2.\end{aligned}}}$

الحدود القليلة الأولى من المتتالية هي

1، 1، 2، 3، 3، 4، 5، 5، 6، 6، 6، 8، 8، 8، 10، 9، 10، 11، 11، 12،  ... (التسلسل A005185 في OEIS )

أطلق هوفستاتر على حدود المتتالية اسم "أعداد Q"؛ ^{[ 3 ]} وبالتالي فإن عدد Q الذي يساوي 6 هو 4. ويُعدّ عرض متتالية Q في كتاب هوفستاتر أول ذكر معروف لمتتالية ما وراء فيبوناتشي في الأدب. ^{[ 8 ]}

بينما تُحدد حدود متتالية فيبوناتشي بجمع الحدين السابقين لها، فإن الحدين السابقين لعدد Q يُحددان مدى الرجوع في متتالية Q للعثور على الحدين المراد جمعهما. وبالتالي، تعتمد مؤشرات حدود الجمع على متتالية Q نفسها.

لا يُعدّ Q (1)، وهو العنصر الأول في المتتالية، أحد الحدين اللذين يُضافان لإنتاج عنصر لاحق؛ بل يُستخدم فقط ضمن فهرس في حساب Q (3). ^{[ 9 ]}

على الرغم من أن حدود متتالية Q تبدو وكأنها تتدفق بشكل عشوائي، ^{[ 3 ] [ 10 ] [ 11 ] [ 12 ]،} إلا أنه يمكن تجميع حدودها، كما هو الحال في العديد من متتاليات ما وراء فيبوناتشي، في مجموعات من الأجيال المتتالية. ^{[ 13 ] [ 14 ]} في حالة متتالية Q، يحتوي الجيل k على ^2k عنصرًا. ^{[ 15 ]} علاوة على ذلك، وبما أن g هو الجيل الذي ينتمي إليه عدد Q، فإن الحدين اللذين يُجمعان لحساب عدد Q، واللذين يُطلق عليهما اسم "الوالدين"، يقعان في الغالب في الجيل g - 1، وقليل منهما فقط في الجيل g - 2، ولا يقعان أبدًا في أي جيل أقدم. ^{[ 16 ]}    

معظم هذه النتائج عبارة عن ملاحظات تجريبية، إذ لم يُثبت شيء يُذكر عن متتالية Q حتى الآن. ^{[ 17 ] [ 18 ] [ 19 ]} ولا يُعرف على وجه التحديد ما إذا كانت المتتالية مُعرَّفة جيدًا لجميع قيم n ؛ أي ما إذا كانت المتتالية "تنتهي" عند نقطة ما لأن قاعدة توليدها تحاول الإشارة إلى حدود تقع نظريًا على يسار الحد الأول Q (1). ^{[ 12 ] [ 17 ] [ 19 ]}

بعد مرور 20 عامًا على وصف هوفستاتر لأول مرة لمتتالية Q ، استخدم هو وجريج هوبر الحرف Q لتسمية تعميم متتالية Q نحو عائلة من المتتاليات، وأعادوا تسمية متتالية Q الأصلية في كتابه إلى متتالية U. ^{[ 19 ]}

يتم تعميم متتالية Q الأصلية عن طريق استبدال n  −  1 و n  −  2 بـ n  − r و n − s على التوالي. ^{[ 19 ]}   

وهذا يؤدي إلى عائلة التسلسل

${\displaystyle Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(nr))+Q_{r,s}(n-Q_{r,s}(ns)),\quad n>s,\end{cases}}}$

حيث s  ≥  2 و r  < s . 

عندما تكون ( r , s ) = (1,2)، فإن متتالية Q الأصلية تنتمي إلى هذه العائلة. حتى الآن، لا تُعرف سوى ثلاث متتاليات من عائلة Q( _{r , s)} ، وهي متتالية U التي تكون فيها ( r , s ) = (1,2) (وهي متتالية Q الأصلية )؛ ^{[ 19 ]} ومتتالية V التي تكون فيها ( r , s ) = (1,4)؛ ^{[ 20 ]} ومتتالية W التي تكون فيها ( r , s ) = (2,4). ^{[ 19 ]} المتتالية V فقط، التي لا تتصرف بشكل فوضوي مثل المتتاليات الأخرى، هي التي ثبت أنها لا "تموت". ^{[ 19 ]} وكما هو الحال مع متتالية Q الأصلية ، لم يُثبت شيء يُذكر بشكل قاطع حول متتالية W حتى الآن. ^{[ 19 ]}

الحدود القليلة الأولى من متتالية V هي

1، 1، 1، 1، 2، 3، 4، 5، 5، 6، 6، 7، 8، 8، 9، 9، 10، 11، 11، 11، ... (التسلسل A063882 في OEIS )

الحدود القليلة الأولى من متتالية W هي

1، 1، 1، 1، 2، 4، 6، 7، 7، 5، 3، 8، 9، 11، 12، 9، 9، 13، 11، 9، ... (التسلسل A087777 في OEIS )

بالنسبة للقيم الأخرى ( r ، s ) فإن المتتاليات "تموت" عاجلاً أم آجلاً، أي أنه يوجد n يكون فيه Q _{r ، s} ( n ) غير معرف لأن n − Q _{r ، s} ( n − r ) < 1. ^{[ 19 ]}      

في عام 1998، اقترح كلاوس بين ، العالم في جامعة مونستر (ألمانيا) والذي كان على اتصال وثيق مع هوفستاتر، تعميمًا آخر لتسلسل Q الخاص بهوفستاتر والذي أطلق عليه بين اسم تسلسلات F. ^{[ 21 ]}

تُعرَّف عائلة متواليات Pinn F _{i , j على النحو التالي:}

${\displaystyle F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\F_{i,j}(ni-F_{i,j}(n-1))+F_{i,j}(nj-F_{i,j}(n-2)),\quad n>2.\end{cases}}}$

وهكذا أدخل بين ثوابت إضافية i و j تعمل على تحريك فهرس حدود المجموع من الناحية المفاهيمية إلى اليسار (أي أقرب إلى بداية المتتالية). ^{[ 21 ]}

يبدو أن متتاليات F التي يكون فيها ( i , j ) = (0,0)، (0,1)، (1,0)، و(1,1)، والتي يمثل أولها متتالية Q الأصلية، هي فقط المتتاليات المُعرَّفة جيدًا. ^{[ 21 ]} على عكس Q (1)، فإن العناصر الأولى من متتاليات Pinn F _{i , j} ( n ) هي حدود مجاميع تُستخدم في حساب العناصر اللاحقة من المتتاليات عندما يكون أي من الثوابت الإضافية يساوي  1.

الحدود القليلة الأولى من متتالية Pinn F _0,1 هي

1، 1، 2، 2، 3، 4، 4، 4، 5، 6، 6، 7، 8، 8، 8، 8، 9، 10، 10، 11، ... (التسلسل A046699 في OEIS )

• بالاموهان، ب.؛ كوزنيتسوف، أ.؛ تاني، ستيفان م. (27-06-2007)، "حول سلوك أحد متغيرات متتالية هوفستاتر Q" (ملف PDF) ، مجلة متتاليات الأعداد الصحيحة ، 10 (7)، واترلو، أونتاريو (كندا): جامعة واترلو: 71، رمز Bibcode : 2007JIntS..10...71B ، ISSN 1530-7638 .
• إيمرسون، ناثانيال د. (17-03-2006)، "عائلة من متواليات ميتا-فيبوناتشي مُعرَّفة بواسطة علاقات تكرارية متغيرة الرتبة" (ملف PDF) ، مجلة متواليات الأعداد الصحيحة ، 9 (1)، واترلو، أونتاريو (كندا): جامعة واترلو، ISSN 1530-7638 .
• هوفستاتر، دوغلاس (1980)، غودل، إيشر، باخ: ضفيرة ذهبية أبدية ، دار بنجوين للنشر، رقم ISBN 0-14-005579-7.
• بين، كلاوس (1999)، "النظام والفوضى في متتالية هوفستاتر Q(n)"، التعقيد ، 4 (3): 41-46 ، arXiv : chao-dyn/9803012v2 ، Bibcode : 1999Cmplx...4c..41P ، doi : 10.1002/(SICI)1099-0526(199901/02)4:3 < 41::AID-CPLX8 > 3.0.CO ; 2-3.
• بين، كلاوس (2000)، "مُتَماثِل فوضوي مُشابه لمتتالية كونواي التكرارية"، الرياضيات التجريبية ، 9 (1): 55-66 ، arXiv : cond-mat/9808031 ، Bibcode : 1998cond.mat..8031P ، doi : 10.1080/10586458.2000.10504635 ، S2CID 13519614 .