Οι πρώτοι αριθμοί του Mersenne‏

Ο Martin Mersenne(Μερσέν) (1588-1648) ήταν ένας Γάλλος καλόγερος που τα ενδιαφέροντα του δεν περιορίζονταν μόνο σε θρησκευτικά θέματα! Λάτρευε τη μουσική και ήταν ο πρώτος που ανέπτυξε μια ολοκληρωμένη θεωρία αρμονίας. Ο Μερσέν ήταν αυτός που δημοσιοποίησε πολλούς από τους ισχυρισμούς του Φερμά λόγω της συχνής αλληλογραφία τους. Γενικά ο Μερσέν υπήρξε ένας από τους διακινητές των μαθηματικών ιδεών . Ο Μερσέν έδειχνε μεγάλο ενδιαφέρον για τους πρώτους αριθμούς (πρώτος είναι ένας αριθμός που διαιρείται μόνο με την μονάδα και τον εαυτό του, οι πρώτοι αποτελούν τον "δομικό λίθο" των άλλων αριθμών αλλά οι ανάλυση τους δεν μπορεί να γίνει μέσα σε μια παρένθεση γι' αυτό σταματώ εδώ) και στην προσπάθεια του να ανακαλύψει έναν τύπο που να τους παράγει έφτιαξε έναν μηχανισμό για την δημιουργία μεγάλων πρώτων που μας απασχολεί ακόμα και σήμερα….

Ο Mersenne είχε την ιδέα να δημιουργεί πρώτους απλά πολλαπλασιάζοντας το 2 πολλές φορές με τον εαυτό του και αφαιρώντας την μονάδα (2^N -1) για παράδειγμα 2 Χ 2 Χ 2 – 1 = 7. Σε αυτόν τον συλλογισμό παρατηρούμε πολλές ομοιότητες με την απόδειξη του Ευκλείδη για την απειρία των πρώτων αριθμών, δηλαδή πήρε τον αριθμό που διαιρείται με πολλούς αριθμούς και τον μετατόπισε κατά μια μονάδα με την ελπίδα ότι ο νέος αριθμός δεν θα διαιρείται με κανέναν. Γρήγορα κατάλαβε πως για να έχει κάποια τύχη αυτός ο τύπος θα έπρεπε και ο Ν να είναι πρώτος. Όμως το αντίστροφο δεν ισχύει δηλαδή αν ο Ν είναι πρώτος δεν σημαίνει πως και ο 2^N -1 πρέπει να είναι αναγκαστικά πρώτος. Για παράδειγμα για Ν=11 (πρώτος) έχουμε 2^N -1=2047 που δεν είναι πρώτος αφού π.χ. διαιρείται με το 23 (2047 ÷ 23 = 89).

Ο Mersenne είχε προβλέψει για ποιες τιμές του Ν ο 2^N -1 θα είναι πρώτος : 2 ,3 ,5 ,7 ,13 ,19 ,31 ,67 ,127 ,257

Ο αριθμός 2²⁵⁷ -1 είναι τόσο μεγάλος που δύσκολα κάποιος θα μπορούσε να αμφισβητήσει την πρόβλεψη του , έτσι ο Mersenne αισθανόταν μια ασφάλεια όταν έκανε αυτή διατύπωση(θα δούμε αν έκανε καλά……).

Το 1876 ο Γάλλος Μαθηματικός Eduard Lucas βρήκε τρόπο για να επαληθεύει αν κάποιοι αριθμοί Mersenne είναι πρώτοι. Με τη μέθοδο του απέδειξε πως ο Mersenne είχε παραλείψει από τον κατάλογο των αριθμών Ν, για τους οποίους ο 2^N -1 είναι πρώτος, τους 61 , 89 και 107 ενώ είχε συμπεριλάβει λανθασμένα το 67. Εδώ αξίζει να σημειώσουμε ,για να καταλάβουμε πόσο σημαντική ήταν η μέθοδός του, πως επαλήθευσε ότι είναι όντως πρώτος ο 2¹²⁷ -1 ένας αριθμός με ούτε λίγο ούτε πολύ 39 ψηφία!!! Παρόλα αυτά ο 2²⁵⁷ -1 παρέμενε έξω από τις δυνατότητες του Lukas.

Και θα παρέμενε έξω από τις δυνατότητες του κόσμου γενικά μέχρι να έρθει το 1930 ο Λεμέρ (σε ηλικία μόλις 25 ετών παρακαλώ) να βελτιώσει την μέθοδο του Λύκας .Η απόδειξη είναι απλή στην υλοποίηση της αλλά αποτελεί μυστήριο ακόμα και σήμερα η σύλληψη της. Έτσι ο Λεμέρ , αντιστρέφοντας το πρόβλημα, έδειξε πως ο 2^N -1 είναι πρώτος μόνο αν διαιρεί έναν άλλον αριθμό που ονομάστηκε Λύκας-Λεμέρ και συμβολίζεται με L_N .Η δημιουργία του αριθμού αυτού θα μπορούσαμε να πούμε πως μοιάζει με την ακολουθία Φιμπονάτσι (a_n=a_n-1+a_n-2) , δηλαδή η δημιουργία του επόμενου προκύπτει από τους προηγούμενους. Έτσι για να βρούμε τον L_N υψώνουμε τον προηγούμενο στο τετράγωνο και αφαιρούμε 2 δηλαδή : L_N =(L_N-1)² -2 Για παράδειγμα για Ν=3 θέτουμε σημείο εκκίνησης L₃=14.

Έτσι θα έχουμε L₄=194, L₅=37634, L₆=1416317955,…..

Για παράδειγμα ο 2⁵ -1=31 διαιρεί τον L₅=37634 άρα ο αριθμός Μερσέν 2⁵ -1είναι πρώτος. Με αυτό το απλό τεστ «έπεσε» και το τελευταίο κάστρο που είχε υψώσει ο Μερσέν και απόδείκτηκε ότι ο 2²⁵⁷ -1 δεν είναι πρώτος…! Από τι φάνηκε η λίστα του Μερσέν ήταν εμπειρική και το γεγονός αυτό αμαύρωσε λίγο την φήμη του.

Παρόλο που είχαν ελεγχθεί όλοι οι πρώτοι των προβλέψεων του Μερσέν το «κυνήγι» των μεγάλων αριθμών Μερσέν είχε μόλις αρχίσει.

Ο Λεμέρ το 1952 ,με την βοήθεια ενός υπολογιστή που κατασκεύασε για αυτό το σκοπό, ξεπέρασε τις υπολογιστικές ικανότητες του ανθρώπινου μυαλού βρίσκοντας τον 2⁶⁰⁷ -1 πρώτο. Μέσα σε έναν χρόνο ο Ραφαήλ Ρόμπινσον είχε ήδη καταρίψει άλλες τρεις φορές το ρεκόρ του , και ο μεγαλύτερος γνωστός πρώτος ήταν τώρα το 2^2.281 -1 !!!

Έτσι μπαίνοντας στην εποχή των υπολογιστών ,μέχρι τα μέσα του 1990, οι μεγάλες εταιρίες άρχισαν να εκμεταλλεύονται την ολοένα αυξανόμενη ισχύ των υπολογιστικών συστημάτων για την παραγωγή μεγάλων πρώτων του Μερσέν. Χαρακτηριστικό παράδειγμα είναι όταν οι Πολ Γκέιτζ και Ντέιβιντ Σλοβίνσκι με την βοήθεια του υπολογιστή Cray ,ενώ κατέρριπταν το ένα ρεκόρ μετά το άλλο, ανακοίνωσαν το 1996 τον έβδομο πρώτο τους τον 2^1.257.787 -1, έναν αριθμό με 378.632 ψηφία.

Σήμερα στην αναζήτηση των μεγάλων πρώτων του Μερσέν κυριαρχεί ποιος άλλος από το διαδίκτυο(Internet) με το γνωστό ως Great Internet Mersenne Prime Search (Μεγάλη διαδικτυακή έρευνα για πρώτους του Μερσέν) ή απλούστερα GIMPS . Ο εμπνευστής αυτού Γουόλτμαν στρατολογεί υπολογιστές από όλον τον κόσμο και εκμεταλλεύεται την υπολογιστική ισχύ τους βάζοντας τους να δουλεύουν παράλληλα.Ευχάριστη έκπληξη ήταν η ανακάλυψη , το 2001, από έναν Καναδό φοιτητή, με όνομα Μάικλ Κάμερον, με την χρήση του προσωπικού του υπολογιστή ότι ο 2^13.466.917 -1 είναι πρώτος – ( είναι ένας αριθμός 4 εκατομμύρια ψηφία). Μέχρι και την στιγμή που γράφονται αυτές οι γραμμές οι αριθμοί του Μερσέν που έχουν ανακαλυφθεί είναι 47 . Ο 47^ος είναι ο 2^42.643.801 -1 ένας αριθμός με 12.837.067 ψηφία , παράλληλα είναι και ο 2 μεγαλύτερος πρώτος που είναι γνωστός. Ο αριθμός αυτός ανακαλύφθηκε από τον Odd Magnar Strindmo από την Νορβηγία. Στο επόμενο Link παρουσιάζουμε την λίστα των πρώτων του Mersenne όπως διαμορφώνεται σήμερα http://en.wikipedia.org/wiki/Mersenne_prime .Όποιος θέλει μπορεί να λάβει μέρος στην έρευνα για να προσθέσει τον εαυτό του στο όνομα των εφευρετών αλλά και να κάνει δικό του το μεγάλο χρηματικό έπαθλο το οποίο συνοδεύει την ανακάλυψη του επόμενου μεγάλου πρώτου αριθμού .Περισσότερες πληροφορίες : http://www.mersenne.org/