Αναζήτηση μεγάλων πρώτων αριθμών

Η αναζήτηση μεγάλων πρώτων αριθμών ασχολείται με την εύρεση ολοένα και μεγαλύτερων αριθμών οι οποίοι διαθέτουν τις ιδιότητες των πρώτων αριθμών, δεν διαιρούνται δηλαδή με κανέναν άλλο αριθμό ως διαιρέτη τους παρά μόνο τον εαυτό τους και το 1. Παρότι έχει αποδειχθεί μαθηματικά ήδη κατά την αρχαιότητα από τον Ευκλείδη πως οι πρώτοι αριθμοί είναι άπειροι, η αναζήτηση ολοένα και μεγαλύτερων πρώτων αριθμών είναι διαχρονική, και εξακολουθούν να υπάρχουν πολλοί ερευνητές οι οποίοι συνεχίζουν να αναζητούν όλο και μεγαλύτερους πρώτους αριθμούς. Ειδικά με την συστηματική χρήση ηλεκτρονικών υπολογιστών από τα μέσα του 20ού αιώνα και έπειτα, ο ρυθμός και συχνότητα εύρεσης έχει αυξηθεί κατά πολύ σε σχέση με πριν. Οι περισσότεροι από τους μεγάλους πρώτους αριθμούς είναι πρώτοι αριθμοί Μερσέν της μορφής 2^ν-1 (όπου και ο ν είναι πρώτος). Παρότι από την θεωρητική μαθηματική άποψη η εύρεση ολοένα και μεγαλύτερων αριθμών δεν έχει κάποια ιδιαίτερη σημασία, εκτός από την ανθρώπινη περιέργεια η αναζήτηση είναι χρήσιμη στην επιστήμη υπολογιστών ως προς την βελτιστοποίηση αλγορίθμων και ως προς την δοκιμή των δυνατοτήτων επεξεργαστικής δύναμης, ενώ χρησιμεύουν και για την εύρεση νέων τέλειων αριθμών βάσει του τύπου 2^k-1(2^k-1).^[1]

Aναζήτηση[Επεξεργασία | επεξεργασία κώδικα]

Μέθοδοι[Επεξεργασία | επεξεργασία κώδικα]

Ήδη από τον 3ο αιώνα π.Χ. υπήρχε η μέθοδος του κόσκινου του Ερατοσθένη για την εύρεση μικρών πρώτων αριθμών, ενώ ο Ευκλείδης δημιούργησε το θεμελιώδες θεώρημα της αριθμητικής σύμφωνα με το οποίο ο κάθε αριθμός μπορεί να εκφραστεί ως γινόμενο 2 πρώτων αριθμών εάν δεν είναι πρώτος ο ίδιος.

Η σύγχρονη μέθοδος που χρησιμοποιείται για την εύρεση μεγάλων πρώτων αριθμών είναι συνήθως ο γρήγορος μετασχηματισμός Φουριέ με υλοποίηση της εξέτασης πρώτου αριθμού Λούκας-Λέιμερ για πρώτους αριθμούς Μερσέν.^[2]^[3]

GIMPS και EFF[Επεξεργασία | επεξεργασία κώδικα]

Το 1997 ιδρύθηκε το εγχείρημα Μεγάλη διαδικτυακή αναζήτηση πρώτων αριθμών Μερσέν (Great Internet Mersenne Prime Search, GIMPS) το οποίο χρησιμοποιεί την κατανεμημένη υπολογιστική ισχύ χιλιάδων υπολογιστών παγκοσμίως οι οποίοι ανήκουν σε άτομα που συμμετέχουν εθελοντικά στο εγχείρημα και εγκαθιστούν την εφαρμογή στον υπολογιστή τους. Έως το 2018 μέσω του εγχειρήματος είχαν ανακαλυφθεί οι 16 μεγαλύτεροι πρώτοι αριθμοί Μερσέν. Ως επιβράβευση ο οργανισμός που διαχειρίζεται το εγχείρημα προσφέρει το ποσό των 3.000 δολαρίων ΗΠΑ στο άτομο του οποίου ο υπολογιστής θα βρει κάποιον νέο πρώτο αριθμό Μερσέν.^[4]

Ο οργανισμός Electronic Frontier Foundation για την προάσπιση των διαδικτυακών ελευθεριών, προσφέρει επίσης βραβείο για την εύρεση μεγάλων πρώτων αριθμών με το ποσό των 150.000 δολαρίων εφόσον βρεθεί κάποιος ο οποίος αποτελείται από 100 εκατομμύρια ψηφία. Επιπλέον προσφέρει 250.000 δολάρια εάν βρεθεί πρώτος αριθμός αποτελούμενος από ένα δισεκατομμύριο ψηφία.^[5]

Ο μεγαλύτερος γνωστός[Επεξεργασία | επεξεργασία κώδικα]

Έως τον Νοέμβριο του 2023 ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν ο 2^82.589.933 − 1, αριθμός που διαθέτει συνολικά 24.862.048 ψηφία. Ανακαλύφθηκε τον Δεκέμβριο του 2018 από το GIMPS.^[6]

Ιστορική εξέλιξη[Επεξεργασία | επεξεργασία κώδικα]

Η ιστορική εξέλιξη των μεγαλύτερων γνωστών πρώτων αριθμών είναι όπως παρακάτω.^[7] Όπου M_n= 2ⁿ − 1 ο αριθμός είναι πρώτος αριθμός Μερσέν. Σχετικά με τους αρχικούς γνωστούς μεγάλους πρώτους αριθμούς παρατίθενται μόνο όσοι έχουν αναφερθεί σε γραπτά, ανεξάρτητα από τις μεθόδους του Ευκλείδη (Θεμελιώδες θεώρημα αριθμητικής) και του Ερατοσθένη (Κόσκινο του Ερατοσθένη).

Αριθμοί	Συμβολισμός	Συνολικά ψηφία αριθμού	Έτος εύρεσης	Σημειώσεις
7	7	1	~400 π.Χ.	γραπτά στοιχεία πως ήταν γνωστός στον Φιλόλαο^[8]
127	M₇	3	~300 π.Χ.	γραπτά στοιχεία πως ήταν γνωστός στον Ευκλείδη^[9]^[10]
8.191	M₁₃	4	1456	Ανώνυμος
131.071	M₁₇	6	1460	Ανώνυμος
524.287	M₁₉	6	1588	Από τον Πιέτρο Κατάλντι
6.700.417	${\tfrac {2^{32}+1}{641}}$	7	1732	Από τον Λέοναρντ Όιλερ
2.147.483.647	M₃₁	10	1772	Από τον Λέοναρντ Όιλερ
67.280.421.310.721	${\tfrac {2^{64}+1}{274177}}$	14	1855	Από τον Τόμας Κλάουζεν
2¹²⁷ -1	M₁₂₇	39	1876	Από τον Εντουάρ Λυκά
20.988.936,65.....2.593.863.921	${\tfrac {2^{148}+1}{17}}$	44	1951 (α)	Από την Αιμέ Φεριέ, ο μεγαλύτερος πρώτος αριθμός που βρέθηκε χωρίς χρήση ηλεκτρονικού υπολογιστή
180×(M₁₂₇)²+1	180×(M₁₂₇)²+1	79	1951 (β)	Από τον υπολογιστή EDSAC του πανεπιστημίου του Καίμπρητζ (Μίλερ και Ουίλερ)
2⁴⁴²³ -1	M₄₄₂₃	1.332	1961	IBM 7090 (Αλεξάντερ Χόρβιτς)
2¹⁹⁹³⁷ -1	M₁₉₉₃₇	6.002	1971	IBM 360/91 (Μπράιαντ Τάκερμαν)
2⁸⁶²⁴³ -1	M₈₆₂₄₃	25.962	1982	Cray 1 (Ντέιβιντ Σλόουινσκι)
2⁷⁵⁶⁸³⁹ -1	M₇₅₆₈₃₉	227.832	1992	Cray 2 (Ντέιβιντ Σλόουινσκι και Πωλ Κέιτζ)
2^13466917-1	M_13466917	4.053.946	2001	GIMPS (Cameron, Woltman, Kurowski)
2^57885161 – 1	M_57885161	17.425.170	2013	GIMPS (Cooper, Woltman, Kurowski, et al)
2^74207281 – 1	M_74207281	22.338.618	2016	GIMPS (Cooper, Woltman, Kurowski, Blosser, et al)
2^77232917 – 1	M_77232917	23.249.425	2017	GIMPS (Pace Jonathan)
2^82589933 − 1	M_82589933	24.862.048	2018	GIMPS (Laroche Patrick)

Οι δέκα μεγαλύτεροι γνωστοί[Επεξεργασία | επεξεργασία κώδικα]

Από τον μεγαλύτερο προς τον μικρότερο:

Κατάταξη	Αριθμός	Ανακάλυψη	Αριθμός ψηφίων	Σχόλια
1	2^82589933 – 1	2018	24.862.048
2	2^77232917 – 1	2017	23.249.425	^[11]
3	2^74207281 – 1	2016	22.338.618	^[12]
4	2^57885161 – 1	2013	17.425.170	^[13]
5	2^43112609 – 1	2008	12.978.189	^[14]
6	2^42643801 – 1	2009	12.837.064	^[15]
7	2^37156667 – 1	2008	11.185.272	^[14]
8	2^32582657 – 1	2006	9.808.358	^[16]
9	10223 × 2^31172165 + 1	2016	9.383.761	^[17]
10	2^30402457 – 1	2005	9.152.052	^[18]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Caldwell, Chris K. «All even perfect numbers are a power of two times a Mersenne prime». primes.utm.edu. Ανακτήθηκε στις 9 Ιανουαρίου 2018.
↑ «GIMPS - The Math - PrimeNet». www.mersenne.org (στα Αγγλικά). Ανακτήθηκε στις 9 Ιανουαρίου 2018.
↑ «Average running time of the fast Fourier transform». Journal of Algorithms 1 (2): 187–208. 1980-06-01. doi:10.1016/0196-6774(80)90022-X. ISSN 0196-6774. https://www.sciencedirect.com/science/article/pii/019667748090022X.
↑ «GIMPS Legalese - PrimeNet». www.mersenne.org (στα Αγγλικά). Ανακτήθηκε στις 9 Ιανουαρίου 2018.
↑ «EFF Cooperative Computing Awards» (στα αγγλικά). Electronic Frontier Foundation. 2008-02-29. https://www.eff.org/awards/coop. Ανακτήθηκε στις 2018-01-09.
↑ «50th Known Mersenne Prime Discovered». www.mersenne.org. Ανακτήθηκε στις 4 Ιανουαρίου 2018.
↑ Caldwell, Chris. «The Largest Known Prime by Year: A Brief History». Prime Pages. Ανακτήθηκε στις 20 Ιανουαρίου 2016.
↑ Harris, H. S. The Reign of the Whirlwind, 1999 (p.252)
↑ Nicomachus' "Introduction to Arithmetic" translated by Martin Luther D'Ooge (p.52)
↑ «Euclid's Elements, Book IX, Proposition 36».
↑ «GIMPS Project Discovers Largest Known Prime Number: 2^77.232.917-1». mersenne.org. Great Internet Mersenne Prime Search. Ανακτήθηκε στις 3 Ιανουαρίου 2018.
↑ «GIMPS Project Discovers Largest Known Prime Number: 2^74.207.281-1». mersenne.org. Great Internet Mersenne Prime Search. Αρχειοθετήθηκε από το πρωτότυπο στις 7 Ιανουαρίου 2018. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.
↑ «GIMPS Discovers 48th Mersenne Prime. 2^57.885.161-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 5 Φεβρουαρίου 2013. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.
↑ ^14,0 ^14,1 «GIMPS Discovers 45th and 46th Mersenne Primes. 2^43.112.609-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 15 Σεπτεμβρίου 2008. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.
↑ «GIMPS Discovers 47th Mersenne Prime. 2^42.643.801-1 is newest. but not the largest. known Mersenne Prime». mersenne.org. Great Internet Mersenne Prime Search. 12 Απριλίου 2009. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.
↑ «GIMPS Discovers 44th Mersenne Prime. 2^32.582.657-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 11 Σεπτεμβρίου 2006. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.
↑ «PrimeGrid's Seventeen or Bust Subproject» (PDF). primegrid.com. PrimeGrid. Ανακτήθηκε στις 30 Σεπτεμβρίου 2017.
↑ «GIMPS Discovers 43rd Mersenne Prime. 2^30.402.457-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 24 Δεκεμβρίου 2005. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Κατάλογος των μεγαλύτερων γνωστών πρώτων αριθμών - primes.utm.edu
Great Internet Mersenne Prime Search (GIMPS) - mersenne.org

[1] Caldwell, Chris K. «All even perfect numbers are a power of two times a Mersenne prime». primes.utm.edu. Ανακτήθηκε στις 9 Ιανουαρίου 2018.

[2] «GIMPS - The Math - PrimeNet». www.mersenne.org (στα Αγγλικά). Ανακτήθηκε στις 9 Ιανουαρίου 2018.

[3] «Average running time of the fast Fourier transform». Journal of Algorithms 1 (2): 187–208. 1980-06-01. doi:10.1016/0196-6774(80)90022-X. ISSN 0196-6774. https://www.sciencedirect.com/science/article/pii/019667748090022X.

[4] «GIMPS Legalese - PrimeNet». www.mersenne.org (στα Αγγλικά). Ανακτήθηκε στις 9 Ιανουαρίου 2018.

[5] «EFF Cooperative Computing Awards» (στα αγγλικά). Electronic Frontier Foundation. 2008-02-29. https://www.eff.org/awards/coop. Ανακτήθηκε στις 2018-01-09.

[M77232-6] «50th Known Mersenne Prime Discovered». www.mersenne.org. Ανακτήθηκε στις 4 Ιανουαρίου 2018.

[computerhistory-7] Caldwell, Chris. «The Largest Known Prime by Year: A Brief History». Prime Pages. Ανακτήθηκε στις 20 Ιανουαρίου 2016.

[8] Harris, H. S. The Reign of the Whirlwind, 1999 (p.252)

[9] Nicomachus' "Introduction to Arithmetic" translated by Martin Luther D'Ooge (p.52)

[Euclid-10] «Euclid's Elements, Book IX, Proposition 36».

[M77232917-11] «GIMPS Project Discovers Largest Known Prime Number: 2^77.232.917-1». mersenne.org. Great Internet Mersenne Prime Search. Ανακτήθηκε στις 3 Ιανουαρίου 2018.

[M74207281-12] «GIMPS Project Discovers Largest Known Prime Number: 2^74.207.281-1». mersenne.org. Great Internet Mersenne Prime Search. Αρχειοθετήθηκε από το πρωτότυπο στις 7 Ιανουαρίου 2018. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[M57885161-13] «GIMPS Discovers 48th Mersenne Prime. 2^57.885.161-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 5 Φεβρουαρίου 2013. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[M43112609-14] 14,0 ^14,1 «GIMPS Discovers 45th and 46th Mersenne Primes. 2^43.112.609-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 15 Σεπτεμβρίου 2008. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[M42643801-15] «GIMPS Discovers 47th Mersenne Prime. 2^42.643.801-1 is newest. but not the largest. known Mersenne Prime». mersenne.org. Great Internet Mersenne Prime Search. 12 Απριλίου 2009. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[M32582657-16] «GIMPS Discovers 44th Mersenne Prime. 2^32.582.657-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 11 Σεπτεμβρίου 2006. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[SOB31172165-17] «PrimeGrid's Seventeen or Bust Subproject» (PDF). primegrid.com. PrimeGrid. Ανακτήθηκε στις 30 Σεπτεμβρίου 2017.

[M30402457-18] «GIMPS Discovers 43rd Mersenne Prime. 2^30.402.457-1 is now the Largest Known Prime». mersenne.org. Great Internet Mersenne Prime Search. 24 Δεκεμβρίου 2005. Ανακτήθηκε στις 29 Σεπτεμβρίου 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]