Προβλήματα Μαθηματικών

2 Δεκεμβρίου, 2014

Euler Φ

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 7:00 μμ

Το πρόβλημα προτείνει ο Κωνσταντίνος Κουρουζίδης.

Υπάρχει μονότονη ακολουθία από φυσικούς n_1<n_2<\cdots<n_i<\cdots,
τέτοια ώστε \phi(n_1)=\phi(n_2)=\cdots=\phi(n_i)=\cdots όπου \phi είναι η αριθμητική συνάρτηση του Euler;

31 Σχόλια »

  1. Ωραίο θέμα. Γεγονός είναι πως η απάντηση είναι ξεκάθαρα «Οχι» κι αυτό το παίρνουμε εμείς των «εφαρμοσμένων» ως δεδομένο,χωρίς να το διερευνήσουμε αρκούντως και να το αιτιολογήσουμε. Έτυχε παλιότερα -σε μια «άλλη» ζωή…- να ασχοληθώ με εφαρμογές της συνάρτησης totient του Όυλερ/Γκάους και πραγματικά συχνά χρειάζεται να έχουμε μια ιδέα για το μέγεθος του φ(n) για μεγάλο n. Nα πω τη μαύρη αλήθεια, το αποτέλεσμα που θυμόμουν από μνήμης είναι πως για κάποιον πρώτο p υπάρχουν ακριβώς φ(p-1) primitive roots μόντουλο p, αλλά πόσες είναι αυτές;
    Και επίσης πως το βασικό (που έχει πρακτικό αντίκρυσμα δηλαδή και εφαρμοσιμότητα) είναι «πόσο μικρό μπορεί να είναι το φ(n)/n για μεγάλες τιμές του n ? H ερώτηση για το ΄»πόσο μεγάλο» παραλείπεται καθώς θεωρούμε προφανές το ότι το φ(n)/n πλησιάζει ασυμπτωτικά το 1 για n μεγάλον πρώτο.
    Εδώ όμως τίθεται ως ερώτημα κάτι πιο άμεσο για το φ, το μέγεθός του σε «απόλυτη» θεώρηση. Αυξάνεται δηλαδή απεριόριστα το φ(n) όσο αυξάνεται απεριόριστα το n; Ισχύει δηλαδή lim (n στο άπειρο)φ(n)= άπειρο; ή (απολύτως ισοδύναμα νομίζω, το ερώτημα που τίθεται είναι):
    Για οποιονδήποτε «μεγάλο» θετικό ακέραιο K ,υπάρχουν πεπερασμένως πολλοί n, τέτοιοι ώστε φ(n)<ίσον Κ ,ή όχι;
    Να ομολογήσω πως ανέτρεξα σε σκονισμένα κιτάπια και σε ηλεκιτάπια και η απόδειξη (εφόσον είναι σωστή,όπως νομίζω ότι είναι) που ακολουθεί δεν μπορεί σε καμιά περίπτωση να θεωρηθεί δικιά μου πρωτότυπη ιδέα, αλλά απλά σύνθεση και κατανόηση ιδεών άλλων και παρουσίασή τους από μένα:
    Ένας οποιοσδήποτε φυσικός είτε θα διαιρείται από κάποιον πρώτο p ,είτε θα διαιρείται από κάποια δύναμη κάποιου p: p^a , είτε και τα δύο προηγούμενα ταυτόχρονα. Αν θεωρήσουμε ένα σύνολο Σ(Α ,Β) των φυσικών n που διαιρούν μόνο πρώτους με p K!^K, τότε ο n διαιρείται είτε από ένα πρώτο p>Κ, είτε από το p^(K+1) και έχουμε:
    φ(n) ≥ φ(p) = p − 1 ≥ Κ για την 1η περίπτωση
    φ(n) ≥ φ(p^Κ+1)=p^K *(p-1) ≥ p^K >K για τη δεύτερη.
    Δείχτηκε λοιπό πως αν το n>(Κ!)^Κ, τότε φ(n) ≥ Κ . Q.E.D.

    YΓ. Συγγνώμη για την αγγλική ορολογία σε κάποια σημεία, αλλά δεν κατέχω σε βάθος τη δόκιμη ελληνική (η οποία νομίζω ότι είναι και φτωχή/ελλειπής, ειδικά στη modular αριθμητική,παρεμπιπτόντως)

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — 3 Δεκεμβρίου, 2014 @ 2:20 μμ

  2. Μπουρδουκλωμένο βγήκε! To γνωστό θέμα με τις γωνιώδεις αγκύλες της γουορντπρες…
    Κάνω αλλη μία προσπάθεια με περίφραση:

    Ένας οποιοσδήποτε φυσικός είτε θα διαιρείται από κάποιον πρώτο p ,είτε θα διαιρείται από κάποια δύναμη κάποιου p: p^a , είτε και τα δύο προηγούμενα ταυτόχρονα. Αν θεωρήσουμε ένα σύνολο Σ(Α ,Β) των φυσικών n που διαιρούν μόνο πρώτους με p μικρότερο ή ίσον Α και για τους οποίους ισχύει: ordp(n) μικρότερο ή ίσο του B για όλους τους πρώτους p. Tότε, το σύνολο Σ(Α,Β) είναι ένα πεπερασμένο (finite) σύνολο. Eχει το πολύ (Β+1)^Α στοιχεία, και το μεγαλύτερο στοιχείο του είναι μικρότερο από το οικείο γινόμενο Π ,δηλαδή μικρότερο ή ίσον του (Α!)^Β.
    Δεν είμαι σίγουρος αν το εξηγώ ικανοποιητικά. Δεν υπάρχει πρώτος παράγοντας του n ,μεγαλύτερος του Κ+1. Και οι διακριτοί πρώτοι παράγοντες του n ανήκουν σε ένα πεπερασμένο σύνολο. n=p1^a1 *p2^a2*…*pi^ai για θετικά a(i) ήτοι φ(n)=φ(p1^a1)*φ(p2^a2)*…*φ(pi ^ ai), ήτοι:
    φ(n)=Π(1 ώς i )pi^(ai -1)*(pi -1).
    Για κάθε pi υπάρχουν ΠΕΠΕΡΑΣΜΕΝΩΣ ΠΟΛΛΕΣ επιτρεπτές επιλογές για τις τιμές των εκθετών a(i) ,εφόσον για κάθε pi ισχύει:
    φ(n)μεγαλ. ή ίσον pi^(ai-1)(pi -1)μεγαλύτερο ή ίσον K (για αρκούντως μεγάλα ai)
    Aνακεφαλαιωτικά και ανά περίπτωση λοιπόν,και για αρκετά μεγάλο n, έστω ας πούμε n μεγαλύτερο από K!^K τότε ο n διαιρείται είτε από ένα πρώτο p μεγ. Κ, είτε από το p^(K+1) και έχουμε:
    φ(n) ≥ φ(p) = p − 1 ≥ Κ για την 1η περίπτωση
    φ(n) ≥ φ(p^Κ+1)=p^K *(p-1) ≥ p^K >K
    Δείχτηκε λοιπό πως αν το n>(Κ!)^Κ, τότε φ(n) ≥ Κ . Q.E.D.

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — 3 Δεκεμβρίου, 2014 @ 2:33 μμ

  3. Καλημέρα. Γιώργο θα ήθελα να σε παρακαλέσω να μας εξηγήσεις ξανά όσο το δυνατόν πιο απλά, με λόγια, τη μεθοδολογία σου, όλα τα βήματα που σε οδήγησαν να βρεις το τελικό σου αποτέλεσμα. Ουσιαστικά βρίσκεις, υποθέτοντας εξαρχής ότι γνωρίζουμε τη τιμή που παίρνει η συνάρτηση Φ σε όλα τα πεπερασμένα στο πλήθος στοιχεία της ακολουθίας (στους υπολογισμούς σου θεωρείς ότι γνωρίζεις αρχικά ότι Φ(n_i)=Κ για κάθε i), ένα φυσικό (που εξαρτάται από το Κ) τέτοιο ώστε στο διάστημα των ακεραίων από αυτόν τον αριθμό ( το (Κ!)^Κ ) και πέρα, να είναι αδύνατον να υπάρχει κάποιο στοιχείο της ακολουθίας. Ως εκ τούτου συμπεραίνεις ότι κάθε τέτοια ακολουθία είναι πεπερασμένη.
    Χρησιμοποιείς στους υπολογισμούς σου τον κλειστό τύπο που μας δίνει το Φ(n) όταν γνωρίζουμε τους πρώτους παράγοντες του n;
    Επίσης δεν κατάλαβα τί είναι το Σ(Α, Β) και τί σημαίνει ordp(n).
    Ευχαριστώ.
    Κωνσταντίνος

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 4 Δεκεμβρίου, 2014 @ 6:01 πμ

  4. Εναλλακτικός τρόπος απόδειξης. Προσπαθήστε να κατασκευάσετε ένα κάτω φράγμα της αριθμητικής συνάρτησης του Euler. Ποια ιδιότητα πρέπει να πληρεί το κάτω αυτό φράγμα;
    Υπενθύμιση: Φ(n)=|{x: 0<χ<n; (χ,n)=1}|, όπου (χ,n) είναι ο μέγιστος κοινός διαιρέτης του χ με του n.
    Κατασκευάστε το κάτω φράγμα από το μηδέν. Δεν είναι ανάγκη να είναι το infimum. Φθάνει να πληρεί μια βασική προϋπόθεση.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 4 Δεκεμβρίου, 2014 @ 7:33 πμ

  5. Kωνσταντίνε, το επιχείρημά μου είναι ουσιαστικά ότι κάποιος φυσικός n για τον οποίον ισχύει: \varphi (n) =N δεν έχει κανέναν πρώτο παράγοντα μεγαλύτερο από Ν+1. Αυτό φαίνεται με την εξής απαγωγή εις άτοπο. Έστω πως p αυτός ο πρώτος,δηλαδή ο μικρότερος πρώτος μεγαλύτερος από Ν+1.Aν υπήρχε πρώτος διαιρέτης του n,έστω q με q \geq p τότε: n= q^{k} . m για k \geq 1 και m,q μεταξύ τους πρώτοι (ο q δεν διαιρεί τον m). Θα είχαμε: \varphi(n) = \varphi(q^k) \cdot \varphi(m) \geq q-1 \geq p-1 > N . Άτοπο.
    Εφόσον λοιπόν δεν υπάρχει τέτοιος πρώτος παράγων, οι διακριτοί πρώτοι παράγοντες του n ανήκουν σε ένα πεπερασμένο σύνολο, ας πούμε πως είναι οι : p_1, p_2, p_{3}, \cdots , p_{m}
    Έχουμε λοιπόν n = p_1^{a_1} \cdot p_2^{a_2} . \cdots . p_m^{a_m} ήτοι \varphi(n) = \varphi(p_1^{a_1}) \cdot \varphi(p_2^{a_2}) \cdot \cdots \cdot \varphi(p_m^{a_m}) . Iσχύει δηλαδή: \varphi(n) = \Pi_{i=1}^m p_i^{a_i - 1}(p_i - 1)
    ή αλλιώς για κάθε πρώτο ισχύει p_i, \varphi(n) \geq p_i^{a_i-1}(p_i - 1) > N για ικανοποιητικώς μεγάλο a(i).
    Aυτό δείχνει ότι για κάθε πρώτο p(i) υπάρχουν πεπερασμένως πολλές επιλογές για τις τιμές των εκθετών α στην παραγοντοποίηση.
    Αρα το σύνολο όλων των n για τους οποίους ισχύει: \varphi(n) = N είναι υποσύνολο πεπερασμένου συνόλου, άρα και το ίδιο πεπερασμένο. Και βεβαίως (όσο και να μην είναι ίσως πολύ αυστηρό αυτό..) για κάθε φυσικό Ν ,υπάρχει κάποιος μεγαλύτερός του n του οποίου το φ είναι ίσο με Ν. Αρα του n τείνοντος στο άπειρο,τείνει υποχρεωτικά και το φ(n) στο άπειρο.
    Είμαστε σε όλα εντάξει τώρα; Αντιλαμβάνομαι βεβαίως πως το lower bound ( (N!)^{N} ) που αναφέρω στο πρώτο σχόλιο δεν είναι και ..ό,τι καλύτερο ,αλλά είναι αναμφισβήτητα ένα κάτω φράγμα. Ίσως άχρηστο στην «πράξη» μιας κι ας πούμε για να υπολογίσουμε όλους τους n για τους οποίους φ(n) μικρότερο ή ίσο του 5 ,θα έπρεπε να τσεκάρουμε μέχρι το 120^5= 248832*10^5 🙂

    Ελπίζω πως το επιχείρημα είναι τώρα σαφές . Ήθελα να αποφύγω γνωστά κάτω φράγματα για τη συνάρτηση φ.
    Ας πούμε το \frac{ \varphi (n)*loglog(n)}{n} \geq e^{- \gamma } - \epsilon που ισχύει για κάθε έπσιλον θετικό και μεγάλα n (γ η σταθερά Όυλερ-Μασκερόνι ) καθώς είναι και γνωστά και υπάρχει μεγάλος όγκος αναφορών και στο δίκτυο, και παραείναι «τεχνικά» για τα γούστα και τις δυνάμεις μου.

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — 4 Δεκεμβρίου, 2014 @ 11:16 πμ

  6. Συμφωνώ με το αποτέλεσμα του Γ. Ριζόπουλου, με βάση την εξής ανάλυση:
    Αν Π(ν) είναι το πλήθος των πρώτων που είναι μικρότεροι ή ίσοι του ν (prime counting function) και Σ(ν) το πλήθος των πρώτων που εμφανίζονται με θετικό εκθέτη στην παραγοντική παράσταση του ν, τότε για κάθε φυσικό ν≥2 θα πρέπει να ισχύει: Φ(ν) ≥ Π(ν)-Σ(ν), αφού το πλήθος των σχετικά πρώτων με τον ν που είναι μικρότεροί του περιλαμβάνει τουλάχιστον όλους τους πρώτους που είναι μικρότεροί του, εκτός από αυτούς που εμφανίζονται στην παραγοντική του παράσταση.
    Ως γνωστόν, για ν->∞, limΠ(ν)=lim(ν/logν).
    Το πλήθος των πρώτων που εμφανίζονται στην παραγοντική παράσταση του ν δεν μπορεί να είναι μεγαλύτερο από έναν αριθμό x, τέτοιον ώστε 2^x=ν ==> x = logν/log2. Δηλαδή Σ(ν) ≤ logν/log2
    Επομένως, για ν->∞, limΦ(ν) ≥ lim[Π(ν)-Σ(ν)] ≥ lim(ν/logν-logν/log2) = ∞.
    Κατά συνέπεια, για οποιαδήποτε αυστηρώς αύξουσα ακολουθία φυσικών ν, η συνάρτηση Φ(ν) δεν φράσσεται από κάτω και έτσι δεν μπορεί όλες οι τιμές της Φ(ν) να ταυτίζονται σε μια πεπερασμένη τιμή.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 4 Δεκεμβρίου, 2014 @ 2:23 μμ

  7. Ορθότερα, οι τιμές της Φ(ν) δεν είναι δυνατό να περιοριστούν όλες κάτω από μια πεπερασμένη τιμή, επομένως ούτε να ταυτιστούν σε μια πεπερασμένη τιμή.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 4 Δεκεμβρίου, 2014 @ 3:56 μμ

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

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 4 Δεκεμβρίου, 2014 @ 8:27 μμ

  9. Θα ήθελα να θέσω κάποια ερωτήματα.
    1) Ισχύει ότι για κάθε φυσικό ας πούμε, κ_i, υπάρχει ένας άλλος φυσικός, ν_i, έτσι ώστε να έχουμε Φ(ν_i)=κ_i.

    Πώς μπορεί να αποδειχθεί κάτι τέτοιο; Υπάρχει κάτι σαν αντίστροφη συνάρτηση της Φ;

    2) Είναι η Φ επί στους φυσικούς;

    Ευχαριστώ.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 1 Μαΐου, 2015 @ 11:30 μμ

  10. Το 2) και το 1) είναι τα ίδια ερωτήματα.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 2 Μαΐου, 2015 @ 1:17 πμ

  11. H συνάρτηση Φ δεν είναι ούτε επί ,ούτε 1-1. Το δεύτερο είναι προφανές (π.χ φ(16)=φ(20)=φ(24)=8 ). Για το «επί», δεν υπάρχει ας πούμε ν με Φ(ν)=3 .
    (το βεβαιώνει το Wolphramalpha. https://www.wolframalpha.com/input/?i=%CF%86%28n%29%3D3 πώς αποδεικνύεται τώρα αυτό αυστηρά, θέλει λίγη σκέψη…)

    Μου αρέσει!

    Σχόλιο από George Rizopulos — 3 Μαΐου, 2015 @ 9:56 μμ

  12. Yποθέτω πως το prime counting function π(ν)=ν/ln(ν) που αναφέρει πιο πάνω ο Θανάσης, μάλλον κάνει τη δουλειά…

    Μου αρέσει!

    Σχόλιο από George Rizopulos — 3 Μαΐου, 2015 @ 10:07 μμ

  13. Ναι, είναι προφανές (άμεσο από τον τύπο της Φ) ότι η εξίσωση Φ(n)=p, όπου p πρώτος (εκτός του 2) δεν έχει λύσεις.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 3 Μαΐου, 2015 @ 10:43 μμ

  14. Ή ακόμη πιο γενικά Φ(n)=χ, όπου χ περιττός δεν έχει λύση.
    Τώρα αν υπάρχει κάποιο θεώρημα , πλήρης χαρακτηρισμός του πότε Φ(n)=οποιοσδήποτε άρτιος, έχει λύση δεν γνωρίζω. Ή αν υπάρχουν κάποια αντιπαραδείγματα, αν είναι πεπερασμένα ή όχι. Μάλλον είναι δύσκολο θέμα.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 3 Μαΐου, 2015 @ 11:02 μμ

  15. Ωστόσο μπορεί να είναι εύκολο χρησιμοποιώντας την πολλαπλασιαστικότητα της Φ με επαγωγή να δειχθεί ότι υπάρχει λύση στην εξίσωση που αναφέρω πιο πάνω για άρτιους.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 4 Μαΐου, 2015 @ 12:04 πμ

  16. Φαντάζομαι πως το ζητούμενο δεν είναι να δειχθεί ότι η φ(ν)=χ έχει λύση/εις για οποιονδήποτε άρτιο χ. Π.χ. νομίζω ότι η φ(ν)=14 δεν έχει λύση.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 4 Μαΐου, 2015 @ 11:22 πμ

  17. Γενικότερα, η Φ(ν)=2p, όπου p πρώτος, έχει νομίζω λύσεις, αν και μόνο αν ο 2p+1 είναι επίσης πρώτος (η απόδειξη είναι απλή και υπάρχει εδώ: http://arxiv.org/pdf/1207.4446.pdf).
    Στην περίπτωση 14=2*7, ο 2*7+1=15 δεν είναι πρώτος, οπότε δεν υπάρχει φυσικός ν τέτοιος ώστε Φ(ν)=14. Ομοίως, για 34=2*17, ο 34+1=35 δεν είναι πρώτος, οπότε ούτε η Φ(ν)=34 έχει λύση.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 4 Μαΐου, 2015 @ 2:51 μμ

  18. Ευχαριστώ. Καλή αναφορά.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 4 Μαΐου, 2015 @ 7:25 μμ

  19. Ευχαριστώ με τη σειρά μου. Ας δώσουμε λοιπόν και μια εναλλακτική απάντηση / απόδειξη στο αρχικό πρόβλημα:
    Αν m φυσικός, άρτιος ή ο 1, τότε όλοι οι φυσικοί n για τους οποίους φ(n)=m είναι περιορισμένοι σε κάποιο διάστημα (m, A(m)], όπου A(m) = m*Π[p/(p-1)], για όλους τους p πρώτους και p-1 διαιρέτες του m. Επομένως το σύνολο των φυσικών n με φ(n)=m είναι πεπερασμένο ή κενό. Συνέπεια αυτού είναι ότι είναι αδύνατο να υπάρχει γνησίως αύξουσα ακολουθία άπειρων στο πλήθος φυσικών n που να έχουν όλοι ίσες τιμές φ(n).

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 5 Μαΐου, 2015 @ 9:06 πμ

  20. Ας θεωρηθεί το παραπάνω σχόλιό μου ως απλή υποσημείωση στην απόδειξη του φίλου Γ. Ριζόπουλου, ο οποίος τα είπε φυσικά όλα, his own way!!

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 5 Μαΐου, 2015 @ 10:54 πμ

  21. Η άσκηση μπορούσε να διατυπωθεί πιο απλά, χωρίς να αναφέρουμε ακολουθίες ως εξής: Για κάθε Μ \in \nats, υπάρχουν πεπερασμένοι θετικοί ακέραιοι που ικανοποιούν την εξίσωση \phi(n)=M. Όπως έχουμε δει η εικόνα της \phi αποτελείται από το 1 και άρτιους (μάλιστα όχι όλους). Οπότε το ‘‘πεπερασμένοι θετικοί ακέραιοι’’ συμπεριλαμβάνει και το 0, εκεί που δεν υπάρχει λύση της εξίσωσης.
    Η απόδειξη του κύριου Ριζόπουλου είναι εξαιρετική.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 5 Μαΐου, 2015 @ 3:24 μμ

  22. Για κάθε Μ στους φυσικούς, υπάρχουν…

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 5 Μαΐου, 2015 @ 3:25 μμ

  23. Θανάση, στο σχόλιο 6 λες ότι Φ(ν) >=Π(ν)-Σ(ν) , για κάθε φυσικό ν>=2. Όμως είναι γνωστό ότι η συνάρτηση Π(ν) πέφτει έξω και από τις δύο προοπτικές.

    Πώς τροποποιείται το επιχείρημα;
    Ευχαριστώ.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 6 Μαΐου, 2015 @ 8:20 μμ

  24. Είναι όλα up to big – O , που λέμε;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 6 Μαΐου, 2015 @ 8:51 μμ

  25. Κωνσταντίνε, δεν καταλαβαίνω ακριβώς το ερώτημά σου, αλλά θα προσπαθήσω να εξηγήσω όσο καλύτερα μπορώ την ανισοϊσότητα Φ(ν) ≥ Π(ν) – Σ(ν):
    Π(ν) είναι το πλήθος των πρώτων που είναι ≤ν
    Σ(ν) είναι το πλήθος των πρώτων που είναι παράγοντες του ν, άρα δεν είναι σχετικά πρώτοι με τον ν,
    Φ(ν) είναι το πλήθος των φυσικών που είναι ≤ν και σχετικά πρώτοι με τον ν.
    Νομίζω ότι ο Φ(ν) περιλαμβάνει τουλάχιστον Π(ν)-Σ(ν) πρώτους, εξ ού και η ανισοϊσότητα.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 7 Μαΐου, 2015 @ 4:51 μμ

  26. Το πλήθος των πρώτων όμως, δηλαδή η συμπεριφορά της συνάρτησης Π(ν) δεν είναι γνωστή νομίζω για μικρά ν. Μόνο η ασυμπτωτική της συμπεριφορά.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 7 Μαΐου, 2015 @ 6:31 μμ

  27. Η σχέση Φ(ν) ≥ Π(ν) – Σ(ν) ισχύει νομίζω για κάθε πεπερασμένο ν ανεξαιρέτως και ανεξαρτήτως της συμπεριφοράς της Π(ν) για μικρά ν. Ο συλλογισμός στηρίζεται στη συμπεριφορά της Π(ν) για ν->∞ σύμφωνα με το θεώρημα των πρώτων αριθμών, ότι δηλαδή lim[Π(ν)/(ν/logν)]=1.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 8 Μαΐου, 2015 @ 9:08 πμ

  28. Ευχαριστώ. Τέλος μπορείς να μας εξηγήσεις τί είναι στο 19. το Π[p/(p-1)] ; Φαντάζομαι αυτό το Π πρέπει να είναι γινόμενο.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 8 Μαΐου, 2015 @ 9:49 πμ

  29. Σωστά, είναι γινόμενο και σχηματίζεται ως εξής:
    Παίρνουμε τον αριθμό m και βρίσκουμε όλους τους διαιρέτες του, μαζί και τους 1 και m. Προσθέτουμε το 1 σε κάθε έναν από αυτούς και ελέγχουμε αν το αποτέλεσμα της άθροισης είναι πρώτος. Αν ναι, τον κρατάμε και έτσι έχουμε τους πρώτους p1, p2, p3 κ.ο.κ.
    Σχηματίζουμε τώρα το γινόμενο [p1/(p1-1)]*[p2/(p2-1)]*[p3/(p3-1)]*…
    Αυτό είναι το Π[p/(p-1)], για όλους τους p πρώτους και p-1 διαιρέτες του m.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 8 Μαΐου, 2015 @ 10:34 πμ

  30. Γιώργο θα ήθελα να σε ρωτήσω κάτι πάνω στη λύση σου. Είχες γράψει:

    …Και βεβαίως (όσο και να μην είναι ίσως πολύ αυστηρό αυτό..) για κάθε φυσικό Ν ,υπάρχει κάποιος μεγαλύτερός του n του οποίου το φ είναι ίσο με Ν.

    Μπορείς να μου εξηγήσεις τί εννοείς σε παρακαλώ; Αν γνωρίζουμε γενικά ότι ισχύει φ(n)=N, συμπεραίνουμε από αυτό ότι το n δεν έχει πρώτο παράγοντα μεγαλύτερο από το N+1. Αυτό εσύ το είπες και το απέδειξες.
    Αν συνδυάσουμε τις δύο αυτές προτάσεις έχουμε αντίφαση. Απλά παίρνουμε τον μεγαλύτερο φυσικό »n» που ικανοποιεί την εξίσωση φ(n)=N.

    Ευχαριστώ εκ των προτέρων.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 10 Μαΐου, 2015 @ 12:22 πμ

  31. Συγνώμη. Μάλλον εννοούσες ότι μπορούμε να πετύχουμε οποιοδήποτε »μεγάλο φυσικό» (εικόνα της φ) δηλαδή, για αρκετό μεγάλο input.

    Εξάλλου αν ίσχυε αυτό που είπα πριν, θα κατέρρεε η άσκηση.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 10 Μαΐου, 2015 @ 12:46 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.