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

Ιουλίου 5, 2008

Θαυμάσιες περίοδοι

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 3:39 πμ

Έχετε προσέξει ότι για οποιοδήποτε ακέραιο n που δεν είναι πολλαπλάσιο του 7, η ακολουθία ψηφίων 142857 επαναλαμβάνεται περιοδικά στη δεκαδική αναπαράσταση του \frac{n}{7}; Ας συμφωνήσουμε να λέμε τέτοιες ακολουθίες ψηφίων  «θαυμάσιες περιόδους». Δηλαδή μια ακολουθία από m ψηφία στο δεκαδικό σύστημα θα ονομάζεται θαυμάσια περίοδος μήκους m αν υπάρχει ένας ακέραιος k ώστε η ακολουθία αυτή να επαναλαμβάνεται περιοδικά στη δεκαδική αναπαράσταση του \frac{n}{k} για όλα τα n που δεν είναι πολλαπλάσια του k. Βρείτε όλες τις θαυμάσιες περιόδους μήκους το πολύ 20.

Advertisements

8 Σχόλια »

  1. Υπάρχουν μόλις τρείς διαφορετικές «θαυμάσιες περίοδοι» μήκους μικρότερου από 20. Αυτές είναι για τα k=7, για k=17 και για k=19.

    Οι περίοδοι είναι οι ακόλουθοι:
    142857
    0588235294117647
    052631578947368421.

    Καποια πρώτα συμπεράσματα από αυτήν την αναζήτηση:
    Α)Ουσιατικά το πρόβλημα δεν είναι να βρεθεί μια «θαυμάσια περίοδος», άλλα το ποιοί αριθμοί k μπορούν να παράγουν τέτοιες περιόδους.
    Β)Αποδεικνύεται εύκολα ότι το k δεν μπορεί να έχει διαιρέτες που να μην παράγουν οι ίδιοι θαυμάσιες περιόδους.
    Γ)Δεν εχω αποδείξει ακόμα, αλλα φαίνεται πολύ πιθανό να ισχύει κάτι πολύ ισχυρότερο: τα k να είναι υποχρεωτικά πρώτοι.
    Δ)Ακόμα και έτσι: οι 3, 11, 13 δεν παράγουν «θαυμάσιες περιόδους», αλλά είναι πρώτοι. Γιατί;

    Δεν ξέρω πόσο εύκολα είναι τα παραπάνω ερωτήματα (ειδικά το Δ — το Γ πιστεύω με λίγο ψάξιμο πρέπει να αποδυκνύεται). Πάντως φαίνεται ότι έχουν κάποιο ενδιαφέρον. Θα το ψάξω λοιπόν!

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 5, 2008 @ 4:58 πμ

  2. nefelh:

    Ταχύτατη ανταποκρίση! Πράγματι αυτές (και οι κυκλικές μεταθέσεις τους) είναι όλες οι περίοδοι μήκους το πολύ 20. Αναφορικά με τις παρατηρήσεις σου τώρα:

    Α) Φυσικά, το πρόβλημα είναι να βρείς ποιοι k παράγουν τέτοιες περιόδους.

    Β) Αν θεωρήσουμε ότι οι 2 και 5 παράγουν τη θαυμάσια περίοδο (μήκους 1) 0 τότε αυτό είναι σωστό. Επίσης είναι εύκολο να δούμε ότι αν ο k παράγει μια θαυμάσια περίοδο τότε την ίδια περίοδο παράγει και ο 2^a5^b k, για οποιοιαδήποτε a,b.

    Γ,Δ) Αν ο k δεν διαιρείται από το 2 ούτε από το 5 τότε πράγματι πρέπει να είναι πρώτος. Όπως όμως παρατήρησες αυτό δεν είναι αρκετό.

    Νέο ερώτημα

    Έστω k ακέραιος που παράγει μια θαυμάσια περίοδο και δεν διαιρείται από το 2 ή το 5.
    Δείξτε ότι ο k είναι πρώτος αριθμός.
    Ποια επιπλέον συνθήκη πρέπει να πληροί ο k;

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουλίου 5, 2008 @ 11:28 πμ

  3. Πράγματι, είναι σημαντική παράλειψη τα k=2 και k=5 που δίνουν δίνουν την «θαυμάσια περίοδο» 0.

    Όμως έχω κάποιες ενστάσεις για την συνέχεια.
    Η πρώτη ένσταση είναι ότι αν ο k δεν είναι πρώτος θα πρέπει να έχει πρώτους παράγοντες ΜΟΝΟΝ το 2 και το 5.

    Έστω k\not=2^a\cdot 5^b και παράγει μια «θαυμάσια περίοδο». Τότε το k'=k\cdot 2^a \cdot 5^b δεν παράγει καμία θαυμάσια περίοδο! Για να το δούμε αυτό αρκεί να πάρουμε n_1=2^a\cdot5^b και n_2=k. Για το n_1 η περίοδος που προκύπτει είναι η περίοδος που παράγει το k, ενώ για το n_2 η περίοδος είναι η «τεριμμένη».

    Αυτό ήταν το επιχείρημα που είχα στο μυαλό μου από την αρχή και εύκολα φαίνεται ότι με το ίδιο επιχείρημα μπορούμε να δείξουμε ότι αν το k δεν είναι πρώτος τότε είναι γινόμενο αριθμών που παράγουν την ίδια «θαυμάσια περίοδο».

    Άρα άν δεν είναι πρώτος τότε είναι δύναμη πρώτου ή της μορφής 2^a\cdot 5^b.

    Αρκεί τώρα να αποδείξουμε ότι δεν μπορεί να είναι ούτε δύναμη πρώτου.

    Παρατηρούμε το εξής: Ο μέγιστος αριθμών διαδοχικών μηδενικών σε μια «θαυμάσια περίοδο» που παράγεται από έναν αριθμό k είναι τα μηδενικά που βρίσκονται αμέσως μετά την υποδιαστολή στο δεκαδικό ανάπτυγμα του 1/k.

    Έστω k=p^a, όπου p πρώτος και a>1. Έστω επιπλέον ότι k>10. Η περίοδος του 1/k θα έχει περισσότερα διαδοχικά μηδενικά απ΄αυτήν του 1/p, άρα είναι διαφορετικές. ‘Ομως η περίοδος του \frac{p^{a-1}}{k}=\frac{1}{p} έιναι ίδια με την «θαυμάσια περίοδο» του p. Άρα το k δεν μπορεί να παράγει «θαυμάσια περίοδο».

    Άρα το k είναι υποχρεωτικά πρώτος ή της μορφής 2^a\cdot 5^b.
    —————————–

    Η δεύτερη ένσταση έχει να κάνει όχι με το k άλλα με τις «θαυμάσιες περιόδους».

    Αρχικά εγώ βρήκα τρεις, με διορθώσατε και βρήκατε τέσσερις… τώρα ισχυρίζομαι ότι είναι πέντε! Αν το 0 είναι θαυμάσια περίοδος, τότε γιατί όχι το 9; 😀

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 5, 2008 @ 10:35 μμ

  4. Κατ’ αρχάς στην παράγραφο 3 τα έκανα λίγο μαντάρα με την latex… Αντικαταστήστε την με την παρακάτω.

    Έστω k\not=2^a5^b και παράγει μια “θαυμάσια περίοδο”. Τότε το k'=2^a5^bk δεν παράγει καμία θαυμάσια περίοδο! Για να το δούμε αυτό αρκεί να πάρουμε n_1=2^a5^b και n_2=k. Για το n_1 η περίοδος που προκύπτει είναι η περίοδος που παράγει το k, ενώ για το n_2 η περίοδος είναι η “τεριμμένη”.

    Επιπλέον και πιο ουσιαστικό: η αποδειξη ολοκληρώνεται εξετάζοντας την ειδική περίπτωση p=7, όπου το επιχείρημα αποτελεί τροποποίηση του γενικού επιχειρήματος: στην «θαυμάσια περίοδο» του 7 δεν υπάρχει κανένα 0. Αντίθετα στην περίοδο του 1/49 υπάρχει τολάχιστον ένα 0, άρα το 49 δεν παράγει «θαυμάσια περίοδο». Άρα και καμιά δύναμη του 7 δεν παράγει «θαυμάσια περίοδο».

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 5, 2008 @ 10:43 μμ

  5. Και το επόμενο ερώτημα:

    Στον σώμα \mathbb{F}_p ορίζουμε τάξη του στοιχείου \not=0 τον ελάχιστο εκθέτη που θα πρέπει να υψώσουμε τον n για να μας δώσει την μονάδα και συμβολίζουμε {\rm ord}_pn.

    Στο πρόβλημά μας: Για να παράγει «θαυμάσια περίοδο» ένας πρώτος αριθμός p, πρέπει {\rm ord}_p10=p-1, δηλαδή το 10 να είναι γεννήτορας της πολλαπλασιαστικής ομάδας \mathbb{Z}_p^*.

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 5, 2008 @ 11:14 μμ

  6. Πω-πω! Απαράδεκτος! Πολλά τα λάθη στην latex… Στην δημοσίευση «at 10:35 μ.μ» αλλάξτε το
    \frac{p^{a-1}{k}}=\frac{1}{p}
    με αυτό:
    \frac{p^{a-1}}{k}=\frac{1}{p}.

    Ελπίζω τώρα να είναι όλα σωστά…

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 5, 2008 @ 11:31 μμ

  7. Δεκτές οι ενστάσεις σου nefelh. Πράγματι, με τον ορισμό που έδωσα, αν ο k παράγει μια μη τετριμμένη (0 ή 9) θαυμάσια περίοδο τότε ο 2^a5^b k δεν παράγει μια θαυμάσια περίοδο. Επίσης ο ορισμός έπρεπε να είναι πιο προσεκτικός ώστε να αποκλείει π.χ. το 142857142857 από το να είναι θαυμάσια περίοδος, να ταυτίζει τις κυκλικές μεταθέσεις θαυμάσιων περιόδων κτλ. Mea culpa. Ελπίζω όμως πώς όλοι καταλαβαίνουμε τι ψάχνουμε.

    Ας περάσουμε στα ουσιώδη. Η συνθήκη που βρήκες {\rm ord}_p 10=p-1 είναι ακριβώς αυτό που είχα υπόψιν μου. Είναι ικανή και αναγκαία για να παραγάγει ο p μια θαυμάσια περίοδο και το μήκος της θαυμάσιας περιόδου είναι p-1. Έχεις απόδειξη;

    Ακόμη ένα νέο ερώτημα
    είναι αν μπορούμε να πούμε κάτι ακόμη γιαυτούς τους πρώτους. Π.χ. είναι άπειροι; Δεν ξέρω ποια είναι η απάντηση.

    Το επιχείρημά σου γιατί μια δύναμη πρώτου δεν παράγει θαυμάσια περίοδο είναι σωστό- μου πήρε όμως μερικά λεπτά να πειστώ γιατί. Μια ευκολότερη ίσως απόδειξη είναι ότι αν οι \frac{1}{m},\frac{1}{n} έχουν την ίδια περίοδο τότε για κάποιους φυσικούς r,s o
    \frac{10^r}{m}-\frac{10^s}{n} είναι ακέραιος. Παίρνοντας m=p, n=p^a βλέπει κανείς ότι πρέπει p^{a-1}/10^s.

    Και κάτι ακόμη για το μήκος της περιόδου του \frac{n}{k} με (n,k)=1. Έστω k=2^a5^b m με (m,10)=1. Αν m=1 ο \frac{n}{k} έχει πεπερασμένο δεκαδικό ανάπτυγμα και τετριμμένη περίοδο. Αν m\neq 1 τότε το μήκος της περιόδου του \frac{n}{k} είναι ο μικρότερος ακέραιος r>1 ώστε 10^r=1({\rm mod}m). Το θεώρημα του Euler: 10^{\varphi(m)}=1({\rm mod}m) μας εξασφαλίζει ότι το μήκος της περιόδου διαιρεί το \varphi(m).

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουλίου 6, 2008 @ 3:07 μμ

  8. Οι αριθμοί που εμφανίζονται περιοδικά στο 1/k είναι διαδοχικά οι αριθμοί 10^l\mod k για l=1,2,… . Το ερώτημα είναι ουσιαστικά πότε τα 10^l\mod k αρχίζουν να επαναλαμβάνονται. Αυτό συμβαίνει πρώτη φορά ακριβώς όταν βρεθούν δύο αριθμοί l_1,l_2 10^{l_1}\equiv10^{l_2}\mod k. Άρα τελικά αναζητάμε την ελάχιστη θετική τιμή ώστε 10^{l_1-l_2}\equiv 1\mod k.

    Ένας πιο απλος τρόπος που μπορεί να γίνει κατανοητός και απο αρχαρίους, είναι να κάνει την διαίρεση 1/κ με χαρτί και μολύβι. Εκεί πρέπει να εμφανίζονται διαδοχικά όλα τα δυνατά υπόλοιπα mod k. Το γιατί πρέπει να είναι εμφανές… Όπως καταλαβαίνετε κι εγώ αρχικά από εκεί ξεκίνησα την σκέψη μου πριν το θεωριτικοποιήσω.

    Το επιπλέον ερώτημα φαίνεται πραγματι πολυ ενδιφέρον. Η διαίσθηση λέει ότι θα υπάρχουν… τόσοι πρώτοι υπάρχουν εκεί εξω… Αλλά η διαίσθηση δεν μετράει παντα… 🙂

    Μου αρέσει!

    Σχόλιο από nefelh — Ιουλίου 6, 2008 @ 6:55 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: