סדרת קונוויי

סדרת קונוויי, או בשמה האנגלי 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 תתפתח כך:

$\ d,1d,111d,311d,13211d,111312211d,31131122211d,\ldots$

גם סדרות אלו נקראות סדרות קונוויי, אולם לעיתים השם "סדרת קונוויי" מתייחס דווקא לסדרה המתפתחת במקרה d=3.

ניתן גם להתחיל את הסדרה גם מרצף ספרות כלשהו. הרצף ממנו מתחילים את הסדרה קרוי ה"גרעין" שלה.

באופן פורמלי ניתן להגדיר את סדרת קונווי כך: מגדירים את אופרטור קונוויי המחזיר את הרצף $C(a_{1}^{n_{1}}a_{2}^{n_{2}}\ldots a_{k}^{n_{k}})=n_{1}a_{1}n_{2}a_{2}\ldots n_{k}a_{k}$, כאשר $a^{n}$ הוא סימן מוסכם לרצף של $n$ ספרות $a$ רצופות. כמו כן מניחים שבהצגה הנ"ל לכל ספרה $a_{i}$ מתקיים $a_{i}\neq a_{i+1}$. סדרת קונווי עם גרעין d היא $C_{1}=d,\ C_{n+1}=C(C_{n})$. סדרת קונוויי הסטנדרטית מתקבלת כאשר $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.

קצב גידול

גרף של אורך האיברים בסדרות קונווי על סקאלה לוגריתמית. הסדרות באיור נבדלות בגרעין שלהן: כחול - 1, סגול - 13, אדום - 23 וירוק - 312.

השורשים של הפולינום של קונווי במישור המרוכב. קבוע קונוויי הוא השורש החיובי היחיד.

מסקנה פשוטה מהמשפט הקוסמולוגי היא אפיון קצב הגידול של אורך האיברים בסדרת קונוויי. את הקשרים בין 92 היסודות הפשוטים ניתן לייצג כמטריצה 92×92 $A$. הערך של $a_{ij}$ במטריצה יהיה האורך הכולל של המופעים של היסוד ה-$i$ בהתפתחות של היסוד ה-$j$, לחלק לאורך היסוד ה-$j$. כלומר, $a_{ij}=c_{ij}l_{i}/l_{j}$, כאשר $c_{ij}$ הוא מספר המופעים של היסוד ה-$i$ בהתפתחות של היסוד ה-$j$ ו-$l_{k}$ הוא האורך של היסוד ה-$k$.

נייצג איבר של סדרת קונוויי כווקטור $v$, 92-ממדי שהקואורדינאטה ה-$i$ שלו היא האורך של היסוד ה-$i$ כפול מספר המופעים שלו באיבר. האורך של האיבר בסדרה הוא סכום הקואורדינאטות ב-$v$. לפי המשפט הקוסמולוגי, האורך של האיבר הבא בסדרה תלוי רק בהתפתחות של כל אחד מן היסודות המופיעים בו, ולכן הווקטור המייצג את האיבר הבא יהיה $Av$. והאיבר שלאחריו יהיה $A(Av)$, ובאופן כללי האיבר ה-n לאחריו יהיה $A^{n}v$.

מכאן שהאורך של איבר מתקבל על ידי פתרון נוסחת נסיגה לינארית מסדר 92, וניתן לבטא אותו במונחים של חזקות הערכים העצמיים של המטריצה. האיברים בסדרה יגדלו אסימפטוטית כמו חזקות של הערך המוחלט של הערך העצמי הגדול ביותר בערכו המוחלט. המטריצה $A$ היא מטריצה דלילה, ולכן חישוב הפולינום האופייני שלה אינו מסובך. מתקבל פולינום ממעלה 92 עם גורם אי-פריק (מעל הרציונליים) ממעלה 71:

${\begin{aligned}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{aligned}}$

השורש המקסימלי של הפולינום הוא גם השורש החיובי היחיד שלו, וזהו הערך העצמי המבוקש. הערך קרוי קבוע קונוויי, הוא מספר אי רציונלי ואלגברי מדרגה 71, שערכו $\lambda =1.303577269\ldots$. כאמור, היחס בין האורכים של שני אברים סמוכים בסדרת קנוויי שואף ל-$\lambda$, כלומר האורך של איברי הסדרה גדל בכ-30% בכל דור. מכיוון שהמשקל של היסודות הטרנס-אורניים באיברים גדולים של הסדרה זניח, המסקנה הזו נכונה לכל סדרת קונוויי עם כל גרעין, למעט במקרה המנוון בו הגרעין הוא d=22.

קישורים חיצוניים

• סדרת קונוויי (המתחילה ב-1), באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
• סדרת קונוויי, באתר MathWorld (באנגלית)
• המשפט הקוסמולוגי וטבלת המחרוזות האטומיות, באתר MathWorld (באנגלית)
• הוכחה של המשפט הקוסמולוגי
• הסבר על קצב הגידול