مرکز کامپیوتر ایران | مرکز کامپیوتر ایران
عدد اول بعدی را کشف کنید و جایزه ۱۵۰ هزار دلاری برنده شوید!
ریاضیدانان علاقه مند به اعداد اول که با عنوان اتم های نامحدود در این علم شناخته می شوند و تنها بر خودشان و یک بخش پذیر هستند، در آستانه یک شگفتی قرار دارند.
مردم بر این باورند که محاسبه اعداد اول بزرگ و بزرگ تر در پی انگیزه های مالی صورت می گیرد، اما یکی از ریاضیدانان برتر جهان فکر می کند نظریه بردن اعداد اول به سطح بعدی می تواند از یک الگوریتم یونان باستان به نام غربال اراتوستن نشات گرفته باشد.
غربال اراتوستن همان طور که از اسمش پیداست، یک روش غربال ریاضی است که کمک می کند تا بتوان اعداد اول را تمیز داد. این روش غربال که طراحی و توسعه آن توسط اراتوستن از Cyrene- ریاضیدان یونانی و ستاره شناس (و مدیر سابق کتابخانه مشهور اسکندریه) – در حدود ۲۴۰ قبل از میلاد انجام شده، این امکان را فراهم آورده تا بتوان تمام اعداد اول بین یک مجموعه خاصی از اعداد را مشخص کرد.
می توان این کار را با نوشتن تمام اعداد (مثلا ۱ تا ۱۰۰) شروع و پس از آن شروع به خط زدن اعداد در یک ترتیب خاص کرد – به این صورت که از مضارب ۲ (به غیر از ۲) برای اولین بار شروع می کنیم و پس از آن مضارب ۳ و غیره. در نهایت، هر شماره باقی مانده بر روی برگه کاغذ که از دست خط زدن های شما جان سالم به در ببرد، یک عدد اول است!
این روش کمی برای استانداردهای امروزی سنگین به نظر می رسد (آخرین عدد اول کشف شده دارای ۲۲ میلیون رقم بود)، اما غربال اراتوستن را همچنین می توان به یک الگوریتم تبدیل کرد که کامپیوتر برای تشخیص اعداد دست به کار شود و شما تنها یک قهوه میل کنید! چطور است؟!
البته یک مشکل بزرگ راجع به این الگوریتم وجود دارد؛ این الگوریتم برای اجرا شدن حافظه بسیار زیادی را اشغال می کند و همین موضوع، باعث شده تا این روش در نظر ریاضیدانان مدرن ناکارامد به نظر بیاید.
اما در حال حاضر یک ریاضیدان برتر و موفق به نام هارالد هلفوگ یک راه برای ساده کردن غربال اراتوستن الگوریتم پیدا کرده است و معتقد است کلید اکتشافات اعداد اول در آینده در این موضوع نهفته است.
هارالد یک ریاضیدان اهل پرو از مرکز ملی فرانسه برای تحقیقات علمی و دانشگاه گوتینگن در آلمان است. او هنگامی که در سال ۲۰۱۳ یک مسئله ریاضی ۲۷۱ ساله به نام حدس ضعیف گلدباخ را حل کرد، در جهان ریاضی به شهرت فراوانی رسید.
در حال حاضر، با توجه به ماتیاس لوئی از آمریکا، هلفوگ یک نسخه بهبود یافته از غربال اراتوستن را پیدا کرده که حافظه بسیار کمتری از کامپیوتر اشغال می کند و روش کارامدتری است.
هلفوگ به لوئی گفت: مانند بسیاری از بچه های دیگر، من اعداد اول را در مدرسه ابتدایی با یک جدول یاد گرفتم؛ وقتی که ۱۰ سالم بود!
با درک این موضوع که باید راهی برای کارامد ترین کردن استفاده از این الگوریتم با کامپیوتر پیدا کرد، او با استفاده از چیزی به نام روش دایره، میزان حافظه مورد نیاز برای اجرای این الگوریتم در کامپیوتر را به شدت کاهش داد. به زبان ریاضی، به جای نیاز به N مقدار فضا، در حال حاضر تنها با مقدار ریشه مکعب N می توان این الگوریتم را اجرا کرد.
این مسئله شاید آن قدر ها قابل توجه نباشد، اما ریاضیدان ژان کارلوس از دانشگاه کرنل و دانشگاه لس آند که در تحقیق مشارکتی نداشته می نویسد: بیایید وانمود کنید که شما یک کامپیوتر هستید که برای ذخیره داده ها در حافظه خود از کاغذ استفاده می کنید. اگر برای محاسبه اعداد اول بین ۱ و ۱۰۰۰۰۰۰ دست به کار شوید، شما به ۲۰۰ بند کاغذ (۱۰۰۰۰ ورق) نیاز دارید و اما با استفاده از الگوریتم پیشنهاد شده توسط هلفوگ شما تنها به یک پنجم از یک بند (در حدود ۱۰۰ ورق) نیاز خواهید داشت که قابل تامل است.
این فشرده سازی شاید روند اجرایی الگوریتم را کمی کند تر کند، اما هلفوگ معتقد است کامپیوتر می تواند با استفاده از حافظه کش خود که از حافظه RAM کوچک تر اما سریع تر است، این کاهش سرعت را به خوبی جبران کند؛ به نوعی که به چشم نیاید.
اگرچه بسیاری تکنیک ها و الگوریتم های دیگر وجود دارد که ریاضیدانان با استفاده از آن ها به پیدا کردن اعداد اول می پردازند، اما آن چه روش غربال اراتوستن را از دیگر روش ها متمایز می کند این است که می توان از این روش برای انجام عملیاتی مانند اتحاد و تجزیه که اساس رمزنگاری مدرن است، بهره لازم را برد.
شاید همین روش ابزاری باشد که کمک می کند تا او عدد اول جدید بعدی را پیدا کند. با وجود جایزه ۱۵۰ هزار دلاری برای هر کس که اولین عدد اول ۱۰۰ میلیون رقمی را پیدا کند، این انگیزه در ریاضیدانان و دانشمندان وجود دارد که تمام سعی و تلاش خود را برای کشف این عدد پیدا کنند و از بهترین و کارامدترین الگوریتم ها در این پروسه بهره مند شوند.
منبع / کلیک
