סדרת קונוויי
סדרת קונוויי, או בשמה האנגלי Look-and-say sequence (בתרגום מילולי: סדרת ראה ואמור), היא סדרה שהוצגה ונותחה על ידי המתמטיקאי הבריטי ג'ון הורטון קונוויי במאמרו The Weird and Wonderful Chemistry of Audioactive Decay משנת 1986.
תחילתה של הסדרה:
- 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,...
הגדרת הסדרה
הסדרה מוגדרת באופן רקורסיבי באמצעות הכלל הבא: בכל שלב מסתכלים על האיבר הקודם בסדרה ומקריאים בקול את ספרותיו כך שלכל רצף של ספרות זהות מקריאים קודם את אורך הרצף (כמה ספרות מופיעות בו) ואז את הספרה. רצף הספרות אותו אומרים בקול הוא האיבר הבא בסדרה. בפירוט:
- האיבר הראשון מוגדר כ-"1".
- באיבר הראשון יש מופע 1 של 1 ולכן האיבר השני הוא "11" (בקול: פעם אחת אחד).
- באיבר השני יש 2 מופעים של 1 ולכן האיבר השלישי הוא "21" (בקול: פעמיים אחד).
- באיבר השלישי יש מופע 1 של 2 ומופע 1 של 1 ולכן האיבר הרביעי הוא "1211" (בקול: פעם אחת שתיים ופעם אחת אחד).
- באיבר הרביעי יש מופע 1 של 1, לאחריו מופע 1 של 2 ואז 2 מופעים של 1 ולכן האיבר החמישי הוא "111221" (בקול: פעם אחת אחד, פעם אחת שתיים ופעמיים אחד).
- באיבר החמישי יש 3 מופעים של 1, 2 מופעים של 2 ומופע 1 של 1 ולכן האיבר השיש הוא "312211" (בקול: שלוש פעמים אחד, פעמיים שתיים ופעם אחת אחד). וכן הלאה.
במקום 1 ניתן להתחיל את הסדרה בספרה אחרת. במקרה כזה סדרה שמתחילה בספרה d שאינו 1 תתפתח כך:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d,\ldots}
גם סדרות אלו נקראות סדרות קונוויי, אולם לעיתים השם "סדרת קונוויי" מתייחס דווקא לסדרה המתפתחת במקרה d=3.
ניתן גם להתחיל את הסדרה גם מרצף ספרות כלשהו. הרצף ממנו מתחילים את הסדרה קרוי ה"גרעין" שלה.
באופן פורמלי ניתן להגדיר את סדרת קונווי כך: מגדירים את אופרטור קונוויי המחזיר את הרצף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(a_1^{n_1}a_2^{n_2}\ldots a_k^{n_k}) = n_1a_1n_2a_2\ldots n_ka_k} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^n} הוא סימן מוסכם לרצף של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ספרות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} רצופות. כמו כן מניחים שבהצגה הנ"ל לכל ספרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i \ne a_{i+1}} . סדרת קונווי עם גרעין d היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1 = d,\ C_{n+1} = C(C_n)} . סדרת קונוויי הסטנדרטית מתקבלת כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1 = 1} .
תכונות
לכל גרעין נתון, האורך של איברי הסדרה (מספר הספרות באיבר) הולך ומתארך לאינסוף, למעט במקרה שהגרעין הוא 22, אז הסדרה מתנוונת ונהיית קבועה: 22, 22, 22.... זוהי תוצאה של המשפט הקוסמולוגי כמפורט להלן.
בסדרה שגרעינה הוא ספרה יחידה, כל הספרות המופיעות (למעט האחרונה שהיא תמיד d) הן 1, 2 או 3. הסיבה היא שלא יכול להופיע רצף של יותר משלוש ספרות זהות ברצף, שכן משמעות הדבר היא כי ספרו את אותה ספרה שלא ברצף. לדוגמה "41" לא יכול להופיע, כי משמעו שקדם לו "1111" שלו קדם "11" שאמור להיות מתורגם ל-"21".
המשפט הקוסמולוגי
המשפט הקוסמולוגי של קונוויי הוא משפט בסיסי לגבי סדרות קונוויי שמאפשר לחקור את תכונותיהן. המשפט קובע שקיים מספר קבוע N כך שהחל מהאיבר N, כל איברי סדרת קונוויי (עם גרעין כלשהו) מורכבים מרצף של תת-מחרוזות מתוך רשימה ידועה וסופית, ושכל תת-מחרוזת ממשיכה ומתפתחת באופן בלתי תלוי בשאר התת-מחרוזות.
התת-מחרוזות הבסיסיות מהן ניתן ליצור את כל איברי סדרות קונוויי מכונים "יסודות". ישנם 92 יסודות המופיעים בסדרת קונוויי הסטנדרטית (עם גרעין 1), והם נקראים על שם 92 היסודות הכימיים הראשונים בטבלה המחזורית. סדרות קונוויי עם גרעין הכולל ספרה שאינה 1, 2 או 3 כוללות גם יסודות נוספים "טרנס-אורניים". יש שני יסודות טרנס-אורניים לכל ספרה גדולה מ-3.
האיבר השני של סדרת קונוויי שגרעינה הוא אחד היסודות נקרא ה"התפתחות" של היסוד הזה. למשל היסוד "ניקל" הוא המחרוזת "11133112" וההתפתחות שלו היא "31232112", מחרוזת שהיא בעצמה צירוף של "אבץ", שהוא "312" ו"קובלט", שהוא "32112". היסודות נבנים כך שההתפתחות של כל יסוד היא צירוף של יסודות. היסוד ה-92 "אורניום" הוא המחרוזת "3". היסוד ה-91 "פרוטקטיניום" הוא ההתפתחות של "אורניום", כלומר הוא "13". היסוד ה-90 תוריום הוא ההתפתחות של "פרוטקטיניום". באופן הזה בונים את כל היסודות, כאשר כל יסוד מוכל (אבל לא תמיד שווה ל-) בהתפתחות של היסוד העוקב לו. התהליך נעצר כאשר מגיעים ליסוד השני "הליום" שההתפתחות שלו מורכבת כולה מיסודות גדולים יותר. לבסוף מוסיפים את היסוד הראשון "מימן", שהוא "22", השווה להתפתחות של עצמו. טבלה של כל היסודות וההתפתחות שלהם ניתן למצוא כאן.
המשפט הקוסמולוגי קובע שכל איבר של סדרת קונוויי (החל ממקום מסוים) ניתן לפרק לסדרה של יסודות, ושהאיבר הבא בסדרה מתקבל על ידי החלפת כל יסוד בהתפתחות שלו.
כמו הוכחת משפט ארבעת הצבעים, הוכחת המשפט הקוסמולוגי מבוססת על רדוקציה למספר סופי של מקרים פרטיים ובדיקתם על ידי מחשב. ידוע שערכו של N המופיע בניסוח המשפט הוא לכל היותר 29, והוא כנראה 24 (לדיון מפורט ראו [1]). כאשר מדובר בסדרת קונווי הסטנדרטית מספיק לקחת N=8.
קצב גידול
מסקנה פשוטה מהמשפט הקוסמולוגי היא אפיון קצב הגידול של אורך האיברים בסדרת קונוויי. את הקשרים בין 92 היסודות הפשוטים ניתן לייצג כמטריצה 92×92 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . הערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{ij}} במטריצה יהיה האורך הכולל של המופעים של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} בהתפתחות של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} , לחלק לאורך היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} . כלומר, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{ij} = c_{ij}l_i/l_j} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{ij}} הוא מספר המופעים של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} בהתפתחות של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l_k} הוא האורך של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} .
נייצג איבר של סדרת קונוויי כווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} , 92-ממדי שהקואורדינאטה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} שלו היא האורך של היסוד ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} כפול מספר המופעים שלו באיבר. האורך של האיבר בסדרה הוא סכום הקואורדינאטות ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} . לפי המשפט הקוסמולוגי, האורך של האיבר הבא בסדרה תלוי רק בהתפתחות של כל אחד מן היסודות המופיעים בו, ולכן הווקטור המייצג את האיבר הבא יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Av} . והאיבר שלאחריו יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(Av)} , ובאופן כללי האיבר ה-n לאחריו יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^nv} .
מכאן שהאורך של איבר מתקבל על ידי פתרון נוסחת נסיגה לינארית מסדר 92, וניתן לבטא אותו במונחים של חזקות הערכים העצמיים של המטריצה. האיברים בסדרה יגדלו אסימפטוטית כמו חזקות של הערך המוחלט של הערך העצמי הגדול ביותר בערכו המוחלט. המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} היא מטריצה דלילה, ולכן חישוב הפולינום האופייני שלה אינו מסובך. מתקבל פולינום ממעלה 92 עם גורם אי-פריק (מעל הרציונליים) ממעלה 71:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} x^{71} &&- x^{69} &&- 2x^{68} &&- x^{67} &&+ 2x^{66} &&+ 2x^{65} &&+ x^{64} &&- x^{63} &&- x^{62} \\ -x^{61} &&- x^{60} &&- x^{59} &&+ 2x^{58} &&+ 5x^{57} &&+ 3x^{56} &&- 2x^{55} &&- 10x^{54} &&- 3x^{53} \\ -2x^{52} &&+ 6x^{51} &&+ 6x^{50} &&+ x^{49} &&+ 9x^{48} &&- 3x^{47} &&- 7x^{46} &&- 8x^{45} &&- 8x^{44} \\ +10x^{43} &&+ 6x^{42} &&+ 8x^{41} &&- 5x^{40} &&- 12x^{39} &&+ 7x^{38} &&- 7x^{37} &&+ 7x^{36} &&+ x^{35} \\ -3x^{34} &&+ 10x^{33} &&+ x^{32} &&- 6x^{31} &&- 2x^{30} &&- 10x^{29} &&- 3x^{28} &&+ 2x^{27} &&+ 9x^{26} \\ -3x^{25} &&+ 14x^{24} &&- 8x^{23} &&- 7x^{21} &&+ 9x^{20} &&+ 3x^{19} &&- 4x^{18} &&- 10x^{17} &&- 7x^{16} \\ +12x^{15} &&+ 7x^{14} &&+ 2x^{13} &&- 12x^{12} &&- 4x^{11} &&- 2x^{10} &&+ 5x^9 &&+ x^7 &&- 7x^6 \\ +7x^5 &&- 4x^4 &&+ 12x^3 &&- 6x^2 &&+ 3x &&- 6 \end{align}}
השורש המקסימלי של הפולינום הוא גם השורש החיובי היחיד שלו, וזהו הערך העצמי המבוקש. הערך קרוי קבוע קונוויי, הוא מספר אי רציונלי ואלגברי מדרגה 71, שערכו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda = 1.303577269\ldots} . כאמור, היחס בין האורכים של שני אברים סמוכים בסדרת קנוויי שואף ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} , כלומר האורך של איברי הסדרה גדל בכ-30% בכל דור. מכיוון שהמשקל של היסודות הטרנס-אורניים באיברים גדולים של הסדרה זניח, המסקנה הזו נכונה לכל סדרת קונוויי עם כל גרעין, למעט במקרה המנוון בו הגרעין הוא d=22.