جايزهي صدهزار دلاري براي عدد اول مرسن 10 ميليون رقمی
اعداد به شکل Mn=2n-1 که اول باشند, عدد مرسن مي گويند. اولين اعداد مرسن کوچک عبارتند از: 3, 7, 31, 127, 8191, 131071, 2147483647 و ... که متناظر هستند با ... ,89 ,61 ,31 ,19 ,17 ,13 ,7 ,5 ,3 ,2 =n اعداد مرسن ابتدا به خاطر خواص قابل توجهشان مطالعه مي شدند که اين بود که هر عدد مرسن با يک عدد کامل رابطه داشت. وِلش يک تاريخچه بزرگ اعداد مرسن را نگه داري کرد. حدس زده شده است که اعداد مرسن نامتناهي هستند. در نمودار اعداد مرسن Mp با p ≤ ln x, خطي که از بين نقاط مي گذرد, بهترين خط تقريبي را با ln x 409/2 به ما مي دهد. اگر خط محدود به گذشتن از ميان نقاط نمودار نشد, بهترين نمودار, ln x (03/0±50/2) + (31/0±10/1-) هست. تاريخچه پيداکردن اعداد مرسن, با اشتباهات در محاسبه, بسيار چالش انگيز است. براي مثال, کشف سال 1963 که 211213-1 اول است, به وسيله بسته هاي پستي مخصوص ساخته شده با مُهرِ فرستاده شده از يوبرانا, ايلينيوس اعلام شد. وُلتمن, يک شبکه تحقيقاتي توزيع شده در اينترنت را برپا کرد که به GIMPS (Great Internet Mersenne Prime Search) معروف است و هر يک از صدها داوطلب آن, از کامپيوترهاي شخصي خود براي انجام دادن گوشه اي از تحقيقات استفاده مي کنند. در 17 نوامبر 2003, يکي از داوطلبان GIMPS کشف چهلمين عدد مرسن را گزارش داد و اين کشف, پس از آن تأييد شد. تقريباً شش ماه پس از آن, کشف چهل و يکمين عدد مرسن توسط يکي از داوطلبان اين شبکه اعلام شد. چهل و دومين عدد ناشناخته مرسن نيز در 18 فوريه 2005 اعلام شد و توان آن در 26 فوريه منتشر شد. تلاش هاي داوطلبان GIMPS, اين پروژه محاسباتي توزيع شده را تبديل به کاشف هشت عدد بزرگ تر اعداد مرسن نمود. در واقعيت, تا فوريه 2005, شرکت کنندگان GIMPS, تمام توان هاي زير 9,889,900 را امتحان کرده بودند و دو بار چک کرده بودند و همه توان هاي پايين تر از 15,130,000 را دست کم يک بار امتحان کرده بودند. قضيه ها و فرمول ها قضيه1: اگر Mn اول باشد, n نيز بايد خود اول باشد. اثبات: فرض کنيم به ازاي n مرکبي, 2n-1 اول است؛ در اين صورت, مي توان n را به صورت ضرب دو عدد غير يک n = rs نوشت؛ پس: 2n -1 = 2rs -1 = (2r)s -1s = (2r -1)(…) پس اگر s زوج باشد, طبق اتحاد مزدوج و اگر فرد باشد طبق اتحاد چاق و لاغر (لاگرانژ) به عوامل اول تجزيه مي شود و اول نيست؛ پس به تناقض مي رسيم و n بايد اول باشد. اعداد مرسن و رابطه با اعداد کامل واضح است که اعداد مرسن به صورت 2n-1, در مبناي دو به صورت (100…0-1)2 است که برابر (11…1)2 است (تعداد يک ها برابر n است). تعريف: عدد کامل عددي است که با مجموع مقسوم عليه هاي خود, به جز خودش, برابر باشد؛ مانند: 6=3+2+1 و 28=14+7+4+2+1 قضيه2: هر عدد کامل به صورت 2n-1(2n-1) است که 2n-1 اول است. پس يافتن هر عدد مرسن در واقع يافتن يک عدد کامل است و اثبات چندان سختي ندارد. براي مثال به نمايش چهار عدد نخست کامل در مبناي دو توجه مي کنيم: 1+10+11 = 110 1+10+1000+111+1110 = 11100 1+10+100+1000+10000+11111+111110+1111100+11111000 = 111110000 اگر دقت کنيد, 11=1-22 , 111=1-23 , 11111=1-25 , همگي بايد اول باشند؛ زيرا در غير اين صورت, خود اين عدد تجزيه مي شود؛ در نتيجه, تعداد مقسوم عليه هاي عدد کاملِ آن بيشتر شده و مجموع آن ها از خود عدد بيشتر مي شود و ديگر عدد کامل نيست. پس اين ها اعداد مرسن هستند و متعاقباً توان هاي آن ها اول است. پس با يافتن هر عدد کامل, مي توان يک عدد مرسن جديد پيدا کرد. آزمايش لوکاس- لمر تقسيم آزمايشي اکثراً براي تصديق مرکب بودن يک عدد مرسن اول پنهان استفاده مي شود. اين آزمايش, فوراً نشان مي دهد که Mp به ازاي p=11,23,83,131,179,191,239,251 مرکب است (به ترتيب با عوامل اول 23, 47, 167, 263, 359, 383, 479 و 503). يک آزمايش بسيار قدرتمند اوليه براي شناسايي Mp آزمايش لوکاس- لمر است: اگر n ≡ 3 به پيمانه 4 و n اول باشد, در اين صورت 2n+1 | Mn , اگر 2n+1 اول باشد. همچنين اين درست است که عوامل اول 2p-1 بايد شکل 2kp+1 داشته باشند که k يک عدد مثبت طبيعي است و در عين حال شکل 8n+1 يا 8n-1 را داشته باشد (آسپنسکي و هيسلت 1939). يک عامل اول p از يک عدد مرسن Mq = 2q-1 (چه اول و چه مرکب), در صورتي عدد ويفريچ اول است که p2 | 2q-1 . بنابراين, يک عدد مرسن نمي تواند عدد ويفريچ اول باشد. نظريه ها و سؤالات حل نشده اعداد مرسن آيا عدد کامل فرد وجود دارد؟ ما مي دانيم که تمام اعداد کامل, به صورت حاصل ضرب يک عدد اول مرسن تواني از دو مي باشد؛ اما در مورد اعداد فرد کامل چه طور؟ اگر اين عدد يکي است, در اين صورت, به صورت حاصل ضرب يک مربع کامل در يک عدد اول به توان فرد مي باشد, اين عدد بر حداقل هشت عدد اول بخش پذير است و حداقل 37 عامل اول دارد (لزومي ندارد که متمايز باشند)؛ اين عدد حداقل در مبناي اعشاري 300 رقم دارد؛ و يک مقسوم عليه اول بزرگ تر از 1020 دارد. آيا تعداد اعداد مرسن بي نهايت است؟ جواب اين است که احتمالاً بله (زيرا سري هارمونيک بي نهايت است). آيا تعداد اعداد مرسن مرکب بي نهايت است؟ يولر نشان داد که: نظريه: اگر k>1 باشد و p = 4k+3 اول باشد, در اين صورت 2p+1 نيز اول است, اگر و تنها اگر باقي مانده تقسيم 2p بر 2p+1 برابر 1 باشد. همچنين اگر p = 4k+3 باشد و 2p+1 اول باشد, در اين صورت عدد مرسن 2p-1 مرکب است (و به نظر مي آيد که اين حدس منطقي باشد که تعداد اعداد اولي که به ازاي p به صورت 2p+1 باشد, بي نهايت باشد). حدس جديد مرسن بيتمن, سلفريج و واگستاف, حدس زير را زده اند: فرض کنيم p هر عدد طبيعي فرد باشد؛ در اين صورت اگر دو شرط اول - که در زير آمده است- برقرار باشد, گزاره سوم برقرار خواهد بود: 1( 1-/+k2 = p يا 3-/+k4 = p 2( 1-p2 عدد اول باشد (بديهي است که عدد مرسن اول است.). 3( 3/(1+p2) عددي اول است. توجه داشته باشيد که اين حدس چگونه به حدس قبلي وابسته است. اين سؤال بيشتر از اين که يک حدس باشد (که ما حدس مي زنيم درست باشد.), در زمره سؤال هاي جواب داده نشده است (که ما جواب آن را نمي دانيم.). به راحتي مي توان نشان داد که اگر مربع عدد اول p بر يک عدد مرسن تقسيم شود, در اين صورت p يک عدد اول ويفريچ است و اين اعداد کمياب هستند! فقط دو عدد شناخته شده اند که زير 4,000,000,000,000 هستند و هيچ کدام از اين مربع ها بر يک عدد مرسن بخش پذير نيستند. اگر دنباله اي به اين صورت باشد که Ap = 2Ap-1-1 و A0=2, آيا همه اين دنباله اول هستند؟ به قول ديکـسون کاتـالان, در پاسخ اين سؤال در سال 1876, به لوکاس اظهـار داشــت که 2127-1 (A4), به اين ترتيب اول است. اين اعداد در اين دنباله خيلي سريع, بزرگ مي شوند: C0 = 2 (اول) C1 = 3 (اول) C2 = 7 (اول) C3 = 127 (اول) C4 = 170141183460469231731687303715884105727 (اول) C5 > 1051217599719369681879879723386331576246 (آيا اين عدد اول است؟) به نظر مي آيد احتمال اين خيلي کم باشد که A5 (يا چند عدد بزرگ تر از اين دنباله) اول باشد؛ به طوري که به مثال ديگري از «قانون قوي عددهاي کوچک» جُوي, شک نمي رود. توجه داشته باشيد که اگر يک عدد زوج و مرکب در اين دنباله پيدا شود, طبق نظريه اول, تمام اعداد بعدي مرکب خواهند بود. (لاندن کورت نول به من گفت که او از برنامه اش استفاده مي کند تا جست و جو کند که A5, مقسومٌ عليه اول کوچک تر از 1051 دارد يا نه.)
نظريه ها و سؤالات حل نشده اعداد مرسن
آيا عدد کامل فرد وجود دارد؟
ما مي دانيم که تمام اعداد کامل, به صورت حاصل ضرب يک عدد اول مرسن تواني از دو مي باشد؛ اما در مورد اعداد فرد کامل چه طور؟
اگر اين عدد يکي است, در اين صورت, به صورت حاصل ضرب يک مربع کامل در يک عدد اول به توان فرد مي باشد, اين عدد بر حداقل هشت عدد اول بخش پذير است و حداقل 37 عامل اول دارد (لزومي ندارد که متمايز باشند)؛ اين عدد حداقل در مبناي اعشاري 300 رقم دارد؛ و يک مقسوم عليه اول بزرگ تر از 1020 دارد.
آيا تعداد اعداد مرسن بي نهايت است؟
جواب اين است که احتمالاً بله (زيرا سري هارمونيک بي نهايت است).
آيا تعداد اعداد مرسن مرکب بي نهايت است؟
يولر نشان داد که:
نظريه: اگر k>1 باشد و p = 4k+3 اول باشد, در اين صورت 2p+1 نيز اول است, اگر و تنها اگر باقي مانده تقسيم 2p بر 2p+1 برابر 1 باشد.
همچنين اگر p = 4k+3 باشد و 2p+1 اول باشد, در اين صورت عدد مرسن 2p-1 مرکب است (و به نظر مي آيد که اين حدس منطقي باشد که تعداد اعداد اولي که به ازاي p به صورت 2p+1 باشد, بي نهايت باشد).
حدس جديد مرسن
بيتمن, سلفريج و واگستاف, حدس زير را زده اند:
فرض کنيم p هر عدد طبيعي فرد باشد؛ در اين صورت اگر دو شرط اول - که در زير آمده است- برقرار باشد, گزاره سوم برقرار خواهد بود:
1( 1-/+k2 = p يا 3-/+k4 = p
2( 1-p2 عدد اول باشد (بديهي است که عدد مرسن اول است.).
3( 3/(1+p2) عددي اول است.
توجه داشته باشيد که اين حدس چگونه به حدس قبلي وابسته است.
اين سؤال بيشتر از اين که يک حدس باشد (که ما حدس مي زنيم درست باشد.), در زمره سؤال هاي جواب داده نشده است (که ما جواب آن را نمي دانيم.). به راحتي مي توان نشان داد که اگر مربع عدد اول p بر يک عدد مرسن تقسيم شود, در اين صورت p يک عدد اول ويفريچ است و اين اعداد کمياب هستند! فقط دو عدد شناخته شده اند که زير 4,000,000,000,000 هستند و هيچ کدام از اين مربع ها بر يک عدد مرسن بخش پذير نيستند.
اگر دنباله اي به اين صورت باشد که Ap = 2Ap-1-1 و A0=2, آيا همه اين دنباله اول هستند؟
به قول ديکـسون کاتـالان, در پاسخ اين سؤال در سال 1876, به لوکاس اظهـار داشــت که 2127-1 (A4), به اين ترتيب اول است.
اين اعداد در اين دنباله خيلي سريع, بزرگ مي شوند:
C0 = 2 (اول)
C1 = 3 (اول)
C2 = 7 (اول)
C3 = 127 (اول)
C4 = 170141183460469231731687303715884105727 (اول)
C5 > 1051217599719369681879879723386331576246 (آيا اين عدد اول است؟)
به نظر مي آيد احتمال اين خيلي کم باشد که A5 (يا چند عدد بزرگ تر از اين دنباله) اول باشد؛ به طوري که به مثال ديگري از «قانون قوي عددهاي کوچک» جُوي, شک نمي رود. توجه داشته باشيد که اگر يک عدد زوج و مرکب در اين دنباله پيدا شود, طبق نظريه اول, تمام اعداد بعدي مرکب خواهند بود. (لاندن کورت نول به من گفت که او از برنامه اش استفاده مي کند تا جست و جو کند که A5, مقسومٌ عليه اول کوچک تر از 1051 دارد يا نه.)
گروه (EFF (Electronic Frontier Foundation پيشنهاد يك جايزه $100000 داده است. اين جايزه به نخستين فرد يا گروهي كه بتوانند يك عدد اول مرسن 10 ميليون رقمي پيدا نمايند، داده خواهد شد.
البته اگر شما چنين عددي را به كمك نرمافزار پيدا كنيد اين جايزه با قوانين خاصي كه در سايت زيرآمده به شما پرداخت خواهد شد.
http://www.mersenne.org/prize.html
--------------------------------------------------------------------------------