زنگ‌تفريح شماره‌ي 65
نظريه‌ي اعداد - اعداد اول
ماشين توليد عددهاي اول كانوِي
تا به‌حال چند زنگ‌تفريح را به بحث عددهاي اول اختصاص داده‌ايم، مانند:
اين عددها تعريف ساده‌اي دارند و از آنجا كه هر عدد طبيعي به طور يكتا به عددهاي اول تجزيه مي‌شود، عددهاي اول نقشي اساسي را در نظريه‌ي اعداد به خود اختصاص داده‌اند. اما با شناخته شدن نقش اساسي اين عددها در رياضيات، سوال‌هاي زيادي در مورد آنها مطرح شد كه بيشتر آنها بدون جواب مانده‌اند و يا اينكه يافتن پاسخ براي آنها سال‌هاي زيادي وقت برده است. شايد معروف‌ترين اين سوال‌ها، سوال ساده‌ي گلدباخ (Goldbach) است:
«آيا هر عدد زوج بزرگ‌تر از 2 حاصل‌جمع دو عدد اول است؟»
سوالي كه بي‌پاسخ مانده است. و يا حدس عددهاي اول دوقلو كه عبارت است از اينكه:
«بيشمار عدد اول موجودند كه حاصل‌جمع آنها با 2 نيز عددي اول است.»
درستي يا نادرستي اين حدس نيز هنوز اثبات نشده است. و سوال‌هاي زياد ديگر. حتماً زنگ‌تفريحي را به صورت خاص به معرفي تعدادي از اين سوال‌هاي اختصاص خواهم داد.
 |
جان كانوِي |
اما سوال ديگري كه در مورد عددهاي اول هميشه مطرح بوده پيدا كردن فرمولي است كه عددهاي اول را به ما معرفي كند. اين موضوع نيز مورد مناقشه است، يعني بعضي به دنبال كشف آنند و بسياري از رياضي‌دانان نيز اميدي به يافتن اين فرمول ندارند. در اين موضوع نيز حتماً در آينده به بحث خواهيم پرداخت.
اما روشي كه بتوان به‌وسيله‌ي آن عددهاي اول را پيدا كرد، روش معروف غربال اراتُستن است. در اين زنگ‌تفريح قصد دارم شما را با روشي ديگر براي يافتن عددهاي اول معرفي كنم. روشي كه به بازي كانوي يا ماشين توليد عددهاي اول كانوي (Conway’s prime-producing machine) يا فِرَكترَن (Fractran) معروف است.
فركترن نام الگوريتمي است كه با استفاده از تعدادي متناهي كسر، عددهاي مختلف را به عنوان ورودي مي‌گيرد و خروجي آن نيز عددي طبيعي است. كسرهاي زير را در نظر بگيريد (براي راحتي در محاسبه، به هر كسر يك حرف نسبت مي‌دهيم):
الگوريتم به اين صورت عمل مي‌كند كه عددي طبيعي را مي‌گيرد، و در اولين كسر از چپ كه حاصل‌ضرب آن با عدد ورودي عددي طبيعي شود، ضرب مي‌كند. همين عمل را براي عدد حاصل انجام مي‌دهد و الگوريتم ادامه پيدا مي‌كنيد. اما ادعايي كه كانوي مي‌كنيد اين است كه اگر با عدد 2 به عنوان ورودي اول شروع كنيم، الگوريتم خروجي جالب توجهي خواهد داشت. همان‌گونه كه در زير مي‌بينيد، پس از 19 مرحله به عدد 4، يعني 22 رسيده‌ايم:
آن‌چه جان ه. كانوي (John H. Conway) ادعا كرده است اين است كه توان‌هاي عدد 2 كه در اين الگوريتم حاصل مي‌شوند، فقط توان‌هاي اول عدد دو هستند! البته تاكيد مي‌كنم كه اين فرمول براي محاسبه‌ي عددهاي اول محسوب نمي‌شود و در واقع روش پنهاني غربال اراتستن است.
داستان اين كسرها به همين‌جا ختم نشد. در سال 1999 ميلادي، دِوين كيلمينستِر (Davin Kilminster) ده كسر زير را پيدا كرد كه با شروع كردن از عدد 10 و اجراي الگوريتم فركترن، توان‌هاي اول عدد 10 را به ما خواهد داد:
البته او بعداً تعداد اين كسرها را به نُه كسر زير تقليل داد:
