Πιθανότητα τυχαίας επιλογής ενός πρωτεύοντος αριθμού

Η θεωρία αριθμών είναι κλάδος μαθηματικά που ασχολείται με το σύνολο των ακέραιων αριθμών. Περιοριζόμαστε κάπως κάνοντας αυτό, καθώς δεν μελετάμε απευθείας άλλους αριθμούς, όπως παράλογα. Ωστόσο, άλλοι τύποι πραγματικούς αριθμούς είναι μεταχειρισμένα. Επιπλέον, το θέμα της πιθανότητας έχει πολλές συνδέσεις και διασταυρώσεις με τη θεωρία αριθμών. Μία από αυτές τις συνδέσεις έχει να κάνει με τη διανομή του πρώτοι αριθμοί. Πιο συγκεκριμένα μπορούμε να ρωτήσουμε, ποια είναι η πιθανότητα ότι ένας τυχαία επιλεγμένος ακέραιος από 1 έως Χ είναι ένας πρωταρχικός αριθμός;

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

Προσπαθούμε να προσδιορίσουμε την πιθανότητα επιλογής ενός πρώτου αριθμού. Επομένως, πρέπει να κατανοήσουμε τον ορισμό ενός πρώτου αριθμού. Ένας πρώτος αριθμός είναι ένας θετικός ακέραιος που έχει ακριβώς δύο παράγοντες. Αυτό σημαίνει ότι οι μόνοι διαιρέτες πρωταρχικών αριθμών είναι ένας και ο ίδιος ο αριθμός. Έτσι τα 2,3 και 5 είναι τα πρωταρχικά, αλλά τα 4, 8 και 12 δεν είναι πρωταρχικά. Σημειώνουμε ότι επειδή πρέπει να υπάρχουν δύο παράγοντες σε ένα πρωταρχικό αριθμό, ο αριθμός 1 είναι δεν πρωταρχική.

Η λύση αυτού του προβλήματος είναι απλή για τους μικρούς αριθμούς Χ. Το μόνο που πρέπει να κάνουμε είναι να μετρήσουμε απλώς τους αριθμούς των αρχικών τιμών που είναι μικρότερα ή ίσα με Χ. Διαχωρίζουμε τον αριθμό των αρχικών τιμών μικρότερων ή ίσων με Χ με τον αριθμό Χ.

Για παράδειγμα, για να βρούμε την πιθανότητα να επιλέξουμε ένα πρότυπο από το 1 έως το 10 απαιτεί να διαιρέσουμε τον αριθμό των αρχικών τιμών από 1 σε 10 με 10. Οι αριθμοί 2, 3, 5, 7 είναι πρωταρχικοί, οπότε η πιθανότητα επιλογής ενός prime είναι 4/10 = 40%.

Η πιθανότητα να επιλεγεί ένα πρότυπο από το 1 έως το 50 μπορεί να βρεθεί με παρόμοιο τρόπο. Τα πρωτεύοντα που είναι μικρότερα από 50 είναι: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 και 47. Υπάρχουν 15 πριμοδοτήσεις μικρότερες ή ίσες με 50. Έτσι, η πιθανότητα τυχαίας επιλογής ενός προτύπου είναι 15/50 = 30%.

Αυτή η διαδικασία μπορεί να διεξαχθεί με απλή μέτρηση των αρχικών τιμών, εφόσον έχουμε έναν κατάλογο των πρώτων. Για παράδειγμα, υπάρχουν 25 αρχικές τιμές μικρότερες ή ίσες με 100. (Έτσι, η πιθανότητα ότι ένας τυχαία επιλεγμένος αριθμός από 1 έως 100 είναι πρωταρχικός είναι 25/100 = 25%.) Ωστόσο, εάν δεν έχουμε λίστα των αρχικών τιμών, θα μπορούσε να είναι υπολογιστικά δύσκολο να καθοριστεί το σύνολο των πρώτων αριθμών που είναι μικρότεροι ή ίσοι με ένα δεδομένο αριθμός Χ.

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

Το θεώρημα του πρώτου αριθμού δηλώνει ότι υπάρχουν περίπου Χ / ln (Χ) πρωτεύοντες αριθμοί που είναι μικρότεροι ή ίσοι με Χ. Εδώ ln (Χ) δηλώνει τον φυσικό λογάριθμο του Χ, ή με άλλα λόγια ο λογάριθμος με βάση του ο αριθμός μι. Ως αξία του Χ αυξάνει την προσέγγιση, βελτιώνεται, με την έννοια ότι βλέπουμε μείωση του σχετικού σφάλματος μεταξύ του αριθμού των αρχικών τιμών μικρότερου από Χ και την έκφραση Χ / ln (Χ).

Μπορούμε να χρησιμοποιήσουμε το αποτέλεσμα του θεώρημα του πρώτου αριθμού για να λύσουμε το πρόβλημα που προσπαθούμε να αντιμετωπίσουμε. Γνωρίζουμε από το θεώρημα του πρώτου αριθμού ότι υπάρχουν περίπου Χ / ln (Χ) πρωτεύοντες αριθμοί που είναι μικρότεροι ή ίσοι με Χ. Επιπλέον, υπάρχουν συνολικά Χ θετικούς ακέραιους μικρότερους ή ίσους προς Χ. Επομένως, η πιθανότητα ότι ένας τυχαία επιλεγμένος αριθμός σε αυτό το εύρος είναι πρωταρχικός είναι (Χ / ln (Χ) ) /Χ = 1 / ln (Χ).

Τώρα μπορούμε να χρησιμοποιήσουμε αυτό το αποτέλεσμα για να προσεγγίσουμε την πιθανότητα τυχαίας επιλογής ενός πρώτου αριθμού από τον πρώτο δισεκατομμύριο ακεραίων. Υπολογίζουμε τον φυσικό λογάριθμο ενός δισεκατομμυρίου και βλέπουμε ότι το ln (1.000.000.000) είναι περίπου 20.7 και το 1 / ln (1.000.000.000) είναι περίπου 0.0483. Έτσι έχουμε περίπου 4,83% πιθανότητα να επιλέξουμε τυχαία έναν prime αριθμό από το πρώτο δισεκατομμύριο ακέραιους.