Ζεύγη σχετικά πρώτων αριθμών.

Ιστοσελίδα · #1

Να βρεθεί το πλήθος των ζεύγων των σχετικά πρώτων αριθμών (n,m)

ώστε : $1\leq n \leq m \leq 20.$

#2

Επαναφορά!

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #3

polysot έγραψε: Τετ Φεβ 27, 2013 1:22 am Να βρεθεί το πλήθος των ζεύγων των σχετικά πρώτων αριθμών ώστε : $1\leq n \leq m \leq 20.$

Ζητάμε το $\displaystyle {\rm \sum_{i=1}^{20}\phi(i)}$ το οποίο μετά από πράξεις (και χρήση του $\displaystyle {\rm \phi (n)=n\sum_{i=1}^{l}(1-\dfrac{1}{p_i})$ όπου $\rm p_i,i=1,2,..l$ οι πρώτοι διαιρέτες του $\rm n$ ) το άθροισμα προκύπτει $\rm 128$ .

Υ.γ Ξέρει κανείς αν υπάρχει κάποιος τύπος για το $\displaystyle {\rm \sum_{i=1}^{n}\phi(i)}$ ; (απλά θα γλιτώναμε λίγες

πράξεις)

#4

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ έγραψε: Κυρ Απρ 12, 2020 4:59 pm Υ.γ Ξέρει κανείς αν υπάρχει κάποιος τύπος για το $\displaystyle {\rm \sum_{i=1}^{n}\phi(i)}$ ; (απλά θα γλιτώναμε λίγες πράξεις)

Υπάρχουν ασυμπτωτικοί τύποι. Ισχύει ότι $\displaystyle \sum_{i=1}^{n}\phi(i) \sim \frac{3n^2}{\pi^2}$ . Δηλαδή $\displaystyle \lim_{n \to \infty} \frac{\pi^2}{3n^2} \sum_{i=1}^{n}\phi(i) = 1$

Ισοδύναμα έχουμε $\displaystyle \lim_{n \to \infty} \frac{\sum_{i=1}^{n} \phi(i)}{\sum_{i=1}^{n} i} = \frac{6}{\pi^2}$

Αν και δεν είναι απόλυτα ακριβές συνήθως λέμε ότι αν επιλέξουμε τυχαία δύο αριθμούς, η πιθανότητα να είναι πρώτοι μεταξύ τους είναι $\frac{6}{\pi^2}$

Summand · #5

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ έγραψε: Κυρ Απρ 12, 2020 4:59 pm Ξέρει κανείς αν υπάρχει κάποιος τύπος για το ; (απλά θα γλιτώναμε λίγες πράξεις)

Δεν είμαι ειδήμων, αλλά, απ' όσο ξέρω, δεν υπάρχει κλειστός τύπος για το $\varphi (n)$ . Ουσιαστικά αν υπήρχε, θα υπήρχε τρόπος να γνωρίζουμε "γρήγορα" την ανάλυση σε πρώτους παράγοντες μεγάλων αριθμών οι οποίοι χρησιμοποιούνται στην κρυπτογραφία κλπ.

Φιλικά

Ζεύγη σχετικά πρώτων αριθμών.

Ζεύγη σχετικά πρώτων αριθμών.

Re: Ζεύγη σχετικά πρώτων αριθμών.

Re: Ζεύγη σχετικά πρώτων αριθμών.

Re: Ζεύγη σχετικά πρώτων αριθμών.

Re: Ζεύγη σχετικά πρώτων αριθμών.

Μέλη σε σύνδεση