el en el el en el el el en el uk es en es tr en en ru el el el el el el el el ru el el el el el el el el el el el el el el ru el el el el el en el el el el el el el el el el el el el el es en es el es es tr en es ru en el el en el el el en de el en de en el el el el el el en el el el el el el el el el el el el el el el el el el fr el el el en el el el el el el el el el el el el el el en de de el zh el el el el el el el el el en en de az el en el el en en el en el el en en el el el el el el en en el en el en el el el el el
Την περασμένη εβδομάδα, μιλώντας για την εικασία Collatz είδαμε ότι είχαμε πέσει σε ένα μαθηματικό τέλμα, κάνοντας συνεχώς παρατηρήσεις για το γράφημα Collatz και διάφορα μοτίβα που βλέπαμε σε αυτό, χωρίς όμως να έχουμε να παρουσιάσουμε κάτι το ιδιαίτερα σοκαριστικό – για να θυμηθείτε τι συζητήσαμε την προηγούμενη εβδομάδα, δείτε εδώ, ενώ για όλες τις δημοσιεύσεις της σειράς, δείτε εδώ. Αυτήν την εβδομάδα, όπως είχαμε υποσχεθεί, θα ασχοληθούμε λίγο με τους πρώτους αριθμούς και το πώς αυτοί μπορούν να μας βοηθήσουν στην εξιχνίαση της εικασίας.
Όπως ξέρουμε από το σχολείο, κάθε θετικός ακέραιος μπορεί να γραφτεί κατά μοναδικό τρόπο σαν γινόμενο διακεκριμένων πρώτων αριθμών – όπου πρώτοι λέγονται οι αριθμοί που δεν έχουν μη τετριμμένους διαιρέτες. Μάλιστα, αν αγνοήσουμε τις όποιες αλλαγές στη σειρά με την οποία γράφουμε τους πρώτους στο γινόμενο, αυτό το γινόμενο είναι μοναδικό. Εμείς, για δική μας ευκολία, θα υποθέτουμε – εκτός αν το αναφέρουμε ρητά – ότι οι πρώτοι που εμφανίζονται στο ανάπτυγμα ενός ακεραίου είναι όλοι διαφορετικοί μεταξύ τους, γραμμένοι σε αύξουσα σειρά και οι όποιοι εκθέτες εμφανίζονται είναι θετικοί (σε αυτό το τελευταίο θα διατηρήσουμε μία ελαστικότητα, ωστόσο). Έτσι, για παράδειγμα, αν γράψουμε:
Τώρα, πώς μπορεί το παραπάνω ανάπτυγμα να μας βοηθήσει στη μελέτη της εικασίας Collatz;
Λοιπόν, ας ασχοληθούμε αρχικά με τη συνήθη διατύπωση της εικασίας Collatz. Με βάση αυτή, ξεκινάμε με έναν θετικό ακέραιο αριθμό και αν αυτός είναι άρτιος τον υποδιπλασιάζουμε, ενώ αν είναι περιττός τον πολλαπλασιάζουμε επί 3 και προσθέτουμε 1. Στόχος μας είναι να φτάσουμε στη μονάδα – και η εικασία είναι ότι για κάθε αριθμό τελικά αυτό συμβαίνει. Επομένως, ας πάρουμε έναν θετικό ακέραιο αριθμό ο οποίος γράφεται σαν γινόμενο πρώτων ως εξής:
Το να εφαρμόσουμε τα βήματα του αλγορίθμου που μας παρουσιάζει ο Collatz συνίσταται στο να κάνουμε το εξής:
Αρχικά, αφαιρούμε όλα τα δυάρια από το ανάπτυγμα του αν υπάρχουν – δηλαδή, όσο είναι άρτιος, τον διαιρούμε με το 2.
Μόλις έχουμε ξεμείνει από δυάρια, πολλαπλασιάζουμε με το 3 – δηλαδή, βάζουμε ένα τριάρι στο ανάπτυγμα – και προσθέτουμε 1 στο τελικό αποτέλεσμα.
Επαναλαμβάνουμε τα δύο παραπάνω βήματα όσο χρειαστεί – ενδεχομένως και επ’ άπειρον.
Τώρα σε ό,τι έχει να κάνει με το πρώτο βήμα, αυτό είναι αρκετά απλό: απλώς εξαφανίζουμε όλα τα δυάρια. Τώρα, το επόμενο βήμα έχει δύο στάδια, εκ των οποίων το πρώτο – ο πολλαπλασιασμός με το 3 – είναι επίσης απλό, καθώς απλά επισυνάπτουμε ένα 3 στο ανάπτυγμα του αριθμού που έχουμε. Ως εδώ όλα καλά, καθώς προχωράμε με πολλαπλασιασμούς και διαιρέσεις που είναι συμβατές με την πολλαπλασιαστική φύση του αναπτύγματος ενός αριθμού σε γινόμενο πρώτων. Ωστόσο, τι συμβαίνει όταν προσθέτουμε 1;
Ουσιαστικά, το παραπάνω ερώτημα συνίσταται στο να απαντήσουμε το εξής:
Τι σχέση έχουν τα αναπτύγματα σε γινόμενο πρώτων δύο διαδοχικών ακεραίων αριθμών;
Ας πάρουμε, για αρχή, κάποια παραδείγματα:
Δε φαίνεται κάποιο ιδιαίτερο μοτίβο παραπάνω – και, πράγματι, δεν αναμέναμε να υπάρχει. Αν το καλοσκεφτούμε, το μόνο που ξέρουμε σίγουρα για τα αναπτύγματα δύο διαδοχικών ακεραίων, έστω είναι ότι δεν έχουν κανέναν κοινό παράγοντα. Πράγματι, αν ένας πρώτος διαιρεί τόσο τον όσο και τον τότε θα πρέπει να διαιρεί και τη διαφορά τους, άρα θα πρέπει ο να διαιρεί το 1, άτοπο, καθώς είναι πρώτος. Επομένως, σίγουρα, προσθέτοντας μία μονάδα εξαφανίζουμε όλους τους πρώτους που βρίσκονται στο ανάπτυγμά μας.
Επιπρόσθετα, για τη δική μας περίπτωση, όπου έχουμε τελικά στα χέρια μας έναν περιττό αριθμό, έστω γνωρίζουμε και ότι ο είναι άρτιος – καθώς είναι κατά ένα μεγαλύτερος από τον που είναι περιττός ως γινόμενο περιττών. Επομένως, έχουμε τουλάχιστον ένα δυάρι στο ανάπτυγμά μας και άρα θα κάνουμε τουλάχιστον έναν υποδιπλασιασμό ακόμα. Κι εδώ έρχεται ένα ακόμα ερώτημα να προστεθεί στη λίστα των αναπάντητων ερωτημάτων της σειράς:
Πόσους υποδιπλασιασμούς μπορούμε να κάνουμε μετά από κάθε «τριπλασιασμό» (+1);
Αυτό επίσης δεν είναι εύκολο να το διαπιστώσουμε χωρίς να έχουμε μία αρχική διαίσθηση των πραγμάτων, οπότε πρέπει να βρούμε έναν τρόπο να την αποκτήσουμε αυτή τη διαίσθηση. Και τι πιο απλό από το να αρχίσουμε να παίρνουμε αριθμούς και να τους τριπλασιάζουμε προσθέτοντας και μία μονάδα, μετρώντας στη συνέχεια πόσες φορές εμφανίζεται το 2 στο ανάπτυγμα του τελικού αποτελέσματος.
Γι’ αυτόν τον σκοπό γράψαμε το ακόλουθο script σε python:
import json from matplotlib import pyplot as plt def count_powers_of_2(n): powers = [] for i in range(1, 2 * n + 1, 2): j = 3 * i + 1 counter = 0 while j % 2 == 0: j /= 2 counter += 1 powers.append(counter) return powers def plot_frequencies(powers): x = [2 * i + 1 for i in range(len(powers))] plt.plot(x, powers, 'r-') plt.xlabel('n') plt.ylabel('# of 2s in 3n + 1') plt.savefig('powers_' + str(len(powers)) + '.png') if __name__ == '__main__': n = 20 powers = count_powers_of_2(n) with open('powers_' + str(n) + '.txt', 'w') as file: json.dump(powers, file) plot_frequencies(powers)
Στο παραπάνω δεν κάνουμε τίποτα το τρομερό πέρα από το το να παίρνουμε του n πρώτους περιττούς αριθμούς, να τους πολλαπλασιάζουμε επί 3 και να προσθέτουμε 1 και στη συνέχεια να εξετάζουμε πόσες φορές το αποτέλεσμα διαιρείται με το 2 – τουλάχιστον 1, όπως είδαμε και παραπάνω. Έτσι, κατασκευάζουμε μία λίστα την οποία μετά την απεικονίζουμε σε ένα διάγραμμα, όπως το παρακάτω – n=20:
Πόσες φορές διαιρείται ο 3n+1 με το 2;
Ή παρατηρούμε κάτι ενδιαφέρον. Φαίνεται ότι εναλλάξ πάμε από κάποιον μεγάλο αριθμό – όπου μεγάλος σημαίνει μεγαλύτερος του 1 εδώ – πίσω στο 1. Δηλαδή, ο αριθμός για φαίνεται να περιέχει ακριβώς μία δύναμη του 2. Αυτό που μόλις διατυπώσαμε δεν είναι παρά μία μικρή εικασία που ίσως μας φανεί χρήσιμο να εξετάσουμε αν μπορούμε να την αποδείξουμε. Λίγο πιο αυστηρά, αυτό που λέμε είναι ότι οι αριθμοί της μορφής για διαιρούνται ακριβώς μία φορά με το 2. Λίγο αναλυτικότερα, αν κάνουμε αρχικά πράξεις, έχουμε:
είναι πολλαπλάσια του 2 (προφανές) αλλά όχι και του 4. Ισοδύναμα, ότι οι αριθμοί:
δεν είναι πολλαπλάσια του 2, πράγμα επίσης προφανές, αφού ο είναι πάντοτε άρτιος. Επομένως, πράγματι, αναμένουμε συνεχώς να έχουμε αυτά τα σκαμπανεβάσματα σε κάθε γράφημα που θα σχεδιάσουμε. Τώρα, πριν προχωρήσουμε παρακάτω, ας δούμε τι μας λέει αυτή η μικρή μας διαπίστωση για τους αριθμούς Πρακτικά, κάθε φορά που φτάνουμε σε έναν τέτοιο περιττό αριθμό, αφού κάνουμε τον «τριπλασιασμό», θα μπορούμε αμέσως μετά να κάνουμε μόνο έναν υποδιπλασιασμό και, ως εκ τούτου, θα καταλήξουμε να έχουμε έναν αριθμό που είναι μεγαλύτερος από τον Αυτό τώρα είναι ιδιαίτερα σημαντικό, καθώς ένας τρόπος για να αντιμετωπίσουμε την εικασία Collatz είναι ο εξής:
Υποθέτουμε ότι έχουμε αποδείξει ότι η εικασία αληθεύει για κάποιους αριθμούς,
Αν θέλουμε να εξετάσουμε την ισχύ της εικασίας για τον τότε αρκεί να εξετάσουμε αν στην ακολουθία Collatz που παράγει ο εμφανίζεται σε κάποια φάση κάποιος αριθμός Αν ναι, τότε σταματάμε, καθώς από εκεί και μετά γνωρίζουμε ότι θα καταλήξουμε στη μονάδα.
Το παραπάνω θα αποτελούσε μία μορφή επαγωγικής απόδειξης της εικασίας του Collatz, ωστόσο, όπως φαντάζεστε, το δεύτερο βήμα είναι κάτι που ακόμα δεν έχουμε αποδείξει ότι είναι εφικτό – ή, αντίστοιχα, δεν έχουμε βρει αντιπαράδειγμα. Επομένως, δεδομένου ότι μας απασχολεί απλώς μία ανισοτική σχέση πλέον, έχει ιδιαίτερη σημασία το αν μετά από κάθε βήμα μας ο αριθμός που είχαμε μίκρυνε ή μεγάλωσε. Σαφώς, με τους υποδιπλασιασμούς οι αριθμοί μικραίνουν ενώ με τους «τριπλασιασμούς» μεγαλώνουν – και μάλιστα, περισσότερο από ότι μικραίνουν με έναν διπλασιασμό. Επομένως, έχει νόημα να εξετάσουμε μετά από κάθε «τριπλασιασμό» που κάνουμε πόσες φορές μπορούμε να υποδιπλασιάσουμε – και άρα, πόσο μικραίνει, τελικά, ο αριθμός που είχαμε στην αρχή.
Γενικά, για να αναιρέσουμε έναν «τριπλασιασμό» θα χρειαστούμε δύο διπλασιασμούς, καθώς, αν είναι ένας θετικός ακέραιος τότε:
με την ισότητα να ισχύει μάλιστα μόνο για Επομένως, οι αριθμοί σε μία ακολουθία Collatz που κάνουν«ζημιά» είναι ακριβώς εκείνοι οι οποίοι δεν επιτρέπουν να έχουμε παραπάνω από έναν – το ελάχιστο δυνατό – υποδιπλασιασμό μετά από τον «τριπλασιασμό» τους. Έτσι, θα θέλαμε να γνωρίζαμε περισσότερα γι’ αυτούς τους αριθμούς – ξέρουμε ήδη ποιοι είναι, καθώς είναι εύκολο να δούμε ότι δεν υπάρχουν άλλοι πέρα από τους Για παράδειγμα, εντάξει, το να συναντήσουμε έναν «κακό» αριθμό δεν είναι ίσως τόσο κακό αν μετά ακολουθεί ένας αριθμός ο οποίος δεν είναι δα και τόσο κακός. Επομένως, έχει νόημα να εξετάσουμε τις ακολουθίες τέτοιων αριθμών μέσα σε ακολουθίες Collatz. Υπάρχει το ενδεχόμενο να συναντήσουμε μία άπειρη τέτοια «κακή» ακολουθία; Αν όχι, πόσο μεγάλες μπορεί να είναι τέτοιες ακολουθίες «κακών» αριθμών;
Αυτά και άλλα πολλά την επόμενη φορά! Μέχρι τότε, καλή συνέχεια!
Η κεντρική εικόνα είναι ο πίνακας Τσάι της Mary Cassatt.
Διαβάστε επίσης: Τι λέει το Θεώρημα του Bolzano;
Ακολουθήστε το aftermathsgr στα social media:
Μαθηματικός, μάλλον... Προβολή όλων των δημοσιεύσεων από Aftermaths
Previous Τα σχήματα της εβδομάδας (8)
Next Λυμένα Παραδείγματα: Συναρτήσεις
Ο/Η Η εικασία Collatz (7) – aftermaths.gr λέει:
16 Οκτωβρίου 2021 στο 13:16
[…] να θυμηθείτε περισσότερα από όσα έχουμε πει δείτε εδώ και […]
Γράψτε το σχόλιο σας εδώ....
Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:
Ηλ. διεύθυνση (απαιτείται) Δεν θα εμφανιστεί δημόσια.
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. ( Αποσύνδεση /  Αλλαγή )
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. ( Αποσύνδεση /  Αλλαγή )
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. ( Αποσύνδεση /  Αλλαγή )
Ειδοποίηση μέσω mail για νέα σχόλια.
Να ειδοποιούμαι μέσω mail για νέα άρθρα.
Ακολούθησε το ιστολόγιο μέσω email
Μαζί με 513 ακόμα followers
Η καλή πράξη της ημέρας
Τεστάκι της Ημέρας #001 - Τι θυμόμαστε από το Γυμνάσιο;
Ασκήσεις στις Συναρτήσεις (Β' Λυκείου)
Τι λέει το Θεώρημα του Bolzano;
10 Επαναληπτικά Θέματα - Γ' ΕΠΑΛ
Ασκήσεις στην μονοτονία συναρτήσεων (Β' λυκείου)
Ασκήσεις στη Σύνθεση (Λύσεις)
Συναρτήσεις - Όρια - Συνέχεια
Διαφάνειες - Όρια/Παράγωγος (Γ' ΕΠΑΛ)
Ασκήσεις στις απόλυτες τιμές
Αξίωμα της πληρότητας (6)
Τίποτα στην τύχη (1)
Τεστάκι της ημέρας (176)
The Wumpus Project (1)
1-1 After-maths Collatz featured Fermat Horner Tikz Workshop Α' Γυμνασίου Α' Λυκείου ΑΕΠΠ Απόψεις Β' Λυκείου Γ' λυκείου Διδακτικό υλικό ΕΟΚ ΕΠΑΛ ΘΜΤ Μαθηματικά Φυσική άλγεβρα ακρότατα αλγόριθμοι αμπελοφιλοσοφία ανισότητες ανισώσεις αποδείξεις απόλυτη τιμή ασκήσεις γραφική παράσταση δευτεροβάθμιες διάμεσος διαγώνισμα διακύμανση διασπορά διαφάνειες δομή επανάληψης δομή επιλογής δυνάμεις εισαγωγή εκθετική εξισώσεις επανάληψη θεωρία λογαριθμική λυμένα παραδείγματα λύσεις μέση τιμή μαθηματικά μονοτονία ολοκλήρωμα πίνακες πανελλήνιες παράγωγος παραμετρικές παραστάσεις πιθανότητες πολυώνυμα πράξεις πραγματικοί αριθμοί προβλήματα πρωτοβάθμιες πρόοδοι ρίζες σημειώσεις στατιστική συνέχεια συναρτήσεις συστήματα συχνοτήτων σύνολα τεστ τριγωνομετρία φύλλο εργασίας όρια
Buy me a tea!
Οι οπλές του αγριόγιδου είναι τα τέσσερα δάκτυλα του βιολιστή. Πάνε στα τυφλά και δε λαθεύουν ούτε χιλιοστό. Χυμούν σε γκρεμούς, παιχνιδιάρες στην ανηφοριά, ακροβάτες στην κατηφοριά, είναι καλλιτέχνες τσίρκου για το θεωρείο των βουνών. Οι οπλές του αγριόγιδου γαντζώνονται στον αέρα. Ο ρόζος τους, μικρό μαξιλαράκι, όποτε θέλει λειτουργεί σαν σιγαστήρας, διαφορετικά το χωρισμένο στα δυο νύχι είναι καστανιέτα για φλαμένκο. Οι οπλές του αγριόγιδου είναι τέσσερις άσσοι σε τσέπες χαρτοκλέφτη. Μ' εκείνες η βαρύτητα είναι μια παραλλαγή σ' ένα θέμα, όχι ένας νόμος.