Εικασία του Κόλατζ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

Η εικασία του Κόλατζ (αγγλικά: Collatz conjecture) είναι μια εικασία στα μαθηματικά η οποία πήρε την ονομασία της από τον Λόθαρ Κόλατζ (Lothar Collatz), ο οποίος την πρότεινε για πρώτη φορά το 1937. Η εικασία είναι επίσης γνωστή ως εικασία 3n+1, εικασία Ούλαμ από τον Στάνιλσαβ Ούλαμ (Stanislaw Ulam), πρόβλημα Κακουτάνι από τον Σιζούο Κακουτάνι (Shizuo Kakutani), εικασία Θουέιτς από τον Μπράιν Θουέιτς (Bryan Thwaites), αλγόριθμος του Χάσε από τον Χέλμουτ Χάσε (Helmut Hasse), ή πρόβλημα των Συρακουσών.[1] Η ακολουθία των αριθμών που εμπλέκονται αναφέρεται ως ακολουθία χαλαζιού (επειδή οι τιμές συνήθως υπόκεινται σε πολλαπλές καταβάσεις και αναβάσεις σαν τους κόκκους του χαλαζιού σε ένα σύννεφο,[2][3] είτε ως θαυμαστοί αριθμοί.[4]

Η εικασία συνοψίζεται ως εξής. Πάρτε οποιοδήποτε θετικό ακέραιο n. Αν ο n είναι άρτιος, διαιρέστε τον δια το 2, για να πάρετε το n/2. Εάν ο n είναι περιττός, πολλαπλασιάστε τον επί 3 και προσθέστε 1 για να πάρετε το 3n+1. Επαναλάβετε τη διαδικασία (η οποία έχει χαρακτηριστεί ως "Μισό Ή Τριπλό Συν Ένα", αγγλικά "Half Or Triple Plus One, HOTPO[5]) επ' αόριστον. Κατά την εικασία, από όποιο αριθμό κι αν ξεκινήσετε, θα καταλήξετε πάντα στο ένα.

Ο Πωλ Έρντος δήλωσε σχετικά με την εικασία του Κόλατζ: "Τα μαθηματικά μπορεί να μην είναι έτοιμα για τέτοια προβλήματα."[6] Επίσης, πρόσφερε $500 για την λύση του.[7]

Διατύπωση προβλήματος[Επεξεργασία | επεξεργασία κώδικα]

Αριθμοί από το 1 έως το 9999 και ο αντίστοιχος συνολικός χρόνος τερματισμού τους
Ιστόγραμμα των συνολικών χρόνων τερματισμού για τους αριθμούς 1 έως 100 εκατομμύρια. Ο συνολικός χρόνος τερματισμού είναι στον άξονα των x, η συχνότητα στον άξονα y. Σημειώστε ότι για όλους τους θετικούς ακέραιους το ιστόγραμμα θα είναι μια εντελώς διαφορετική, εκθετικά αυξανόμενη ακολουθία (δείτε #Αντίστροφη).
Διάστημα επανάληψης για εισόδους από το 2 έως 10 εκατομμύρια

Ας εξετάσουμε την ακόλουθη λειτουργία για έναν αυθαίρετο θετικό αριθμό:

  •  Αν ο αριθμός είναι άρτιος, τον διαιρούμε δια δύο.
  • Αν ο αριθμός είναι περιττός, τον τριπλασιάζουμε και προσθέτουμε ένα.

Mαθηματικά, η συνάρτηση ορίζεται ως εξής:

Ξεκινώντας από οποιονδήποτε θετικό ακέραιο n, με επαναληπτική εφαρμογή αυτής της συνάρτησης, σχηματίζεται μια ακολουθία αριθμών χρησιμοποιώντας το αποτέλεσμα του κάθε βήματος ως είσοδο για το επόμενο βήμα:

Η εικασία του Κόλατζ λέει ότι αυτή η ακολουθία θα τελικά καταλήξει στο ένα, ανεξάρτητα από το ποιος θετικός ακέραιος επιλέχθηκε αρχικά.

Το μικρότερο i, τέτοιο ώστε αi = 1 ονομάζεται χρόνος τερματισμού του n. Η εικασία υποστηρίζει ότι κάθε n έχει καλά ορισμένο χρόνο τερματισμού. Αν για κάποιο n, τέτοιο i δεν υπήρχε, θα λέγαμε ότι το  n έχει άπειρο χρόνο τερματισμού και η εικασία Κόλατζ θα ήταν ψευδής.

Για να είναι η εικασία ψευδής, πρέπει να βρεθεί κάποιος αριθμός εκκίνησης που θα οδηγεί σε ακολουθία που δεν περιέχει το 1. Μια τέτοια ακολουθία θα μπορούσε να περιέχει έναν επαναλαμβανόμενο κύκλο που δεν περιλαμβάνει το 1, ή θα μπορούσε να ανεβαίνει σε όλο και μεγαλύτερες τιμές δίχως όριο. Τέτοια ακολουθία δεν έχει βρεθεί.

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Ξεκινώντας με n = 6, προκύπτει η ακολουθία 6, 3, 10, 5, 16, 8, 4, 2, 1.

Το n = 19, παίρνει περισσότερο χρόνο για να φτάσει στο 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Η ακολουθία για n = 27 που καταγράφεται παρακάτω, χρειάζεται 111 βήματα (41 βήματα με περιττό αριθμό) και αναρριχάται ως το 9232 πριν κατηφορίσει στο 1.

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (ακολουθία A008884 στην OEIS)
Απεικόνιση της ακολουθίας με n=27. Στον άξονα των τετμημένων το βήμα και στον άξονα των τεταγμένων οι τιμές της ακολουθίας.

Αριθμοί με χρόνο τερματισμού μεγαλύτερο από οποιαδήποτε μικρότερη τιμή εκκίνησης σχηματίζουν μια αλληλουχία που αρχίζει με

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... (ακολουθία A006877 στην OEIS)

Αριθμοί των οποίων το μέγιστο σημείο της τροχιάς τους είναι μεγαλύτερο από κάθε μικρότερη τιμή εκκίνησης πάνε ως εξής:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (ακολουθία A006884 στην OEIS)

Ο αριθμός των βημάτων που χρειάζεται το n για να φτάσει το 1 είναι

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (ακολουθία A006577 στην OEIS)

Ο αρχικός αριθμός με τον μεγαλύτερο χρόνο τερματισμού μέχρι το 100 εκατομμύρια είναι ο 63.728.127, για τον οποίο η ακολουθία έχει 949 βήματα. Από τους αρχικούς αριθμούς μέχρι το 1 δισεκατομμύριο, ο 670.617.279 χρειάζεται 986 βήματα. Αντίστοιχα, μέχρι τα 10 δισεκατομμύρια, ο 9.780.657.631 έχει τη μεγαλύτερη ακολουθία με 1.132 βήματα.

Οι δυνάμεις με βάση το δύο συγκλίνουν γρήγορα γιατί το 2n υποδιπλασιάζεται σε n φορές και φτάνει στο 1, χωρίς ποτέ να αυξάνεται. Οι αριθμοί Μερσέν Mn χρειάζεται να αυξηθούν n φορές και συνήθως χρειάζονται περισσότερα βήματα για να φτάσουν το 1.

Απεικονίσεις[Επεξεργασία | επεξεργασία κώδικα]

Κύκλοι[Επεξεργασία | επεξεργασία κώδικα]

Κάθε αντιπαράδειγμα στην εικασία Κόλατζ θα έπρεπε να αποτελείται είτε από μία άπειρη αποκλίνουσα τροχιά ή ένα κύκλο διαφορετικό από τον τετριμμένο (4, 2, 1). Έτσι αν κάποιος μπορούσε να αποδείξει ότι αυτά τα είδη αντιπαραδειγμάτων είναι αδύνατο να υπάρχουν, τότε όλοι οι θετικοί ακέραιοι θα είχαν τροχιά που θα έφτανε στον τετριμμένο κύκλο. Ένα τέτοιο ισχυρό αποτέλεσμα δεν έχει αποδειχτεί, ωστόσο ορισμένοι τύποι κύκλων έχουν αποκλειστεί.

Ο τύπος ενός κύκλου μπορεί να οριστεί χρησιμοποιώντας τον "συντομευμένο" ορισμό της συνάρτησης Κόλατζ,  για περιττά n και για άρτια n. Ένας κύκλος είναι μια ακολουθία  όπου, και ούτω καθεξής, μέχρι σε κλειστό βρόχο. Σύμφωνα με αυτό τον ορισμό, ο μόνος γνωστός κύκλος είναι ο τετριμμένος (1, 2). Αν και το 4 είναι μέρος του τετριμμένου κύκλου για την αρχική συνάρτηση Κόλατζ, δεν ανήκει στον κύκλο της "συντομευμένης" συνάρτησης (1, 2). 

Ένας k-κύκλος είναι ένας κύκλος που μπορεί να χωριστεί σε 2k συνεχόμενες υποακολουθίες: k αύξουσες ακολουθίες περιττών αριθμών εναλλασσόμενες με k φθίνουσες ακολουθίες άρτιων αριθμών. Για παράδειγμα, εάν ο κύκλος αποτελείται από μια μοναδική αύξουσα ακολουθία περιττών αριθμών ακολουθούμενη από μία φθίνουσα ακολουθία άρτιων αριθμών, ονομάζεται 1-κύκλος.[8]

Ο Steiner (1977) απέδειξε ότι δεν υπάρχει 1-κύκλος, εκτός από τον τετριμμένο (1, 2).[9] Ο Simons (2004) χρησιμοποίησε την μέθοδο του Steiner για να αποδείξει ότι δεν υπάρχει 2-κύκλος. Οι Simons & de Weger (2003) επέκτειναν αυτήν την απόδειξη φτάνοντας μέχρι τους 68-κύκλους: δεν υπάρχει k-κύκλος με k = 68. Πέραν του 68, η μέθοδος αυτή δίνει άνω φράγματα για τα στοιχεία σε ένα τέτοιο κύκλο: για παράδειγμα, αν υπάρχει 75-κύκλος, τότε τουλάχιστον ένα στοιχείο του κύκλου είναι μικρότερο από 2385×250.[8] Όσο συνεχίζουν εξαντλητικές αναζητήσεις με υπολογιστές, τόσο αποκλείεται η ύπαρξη όλο και μεγαλύτερων κύκλων. Διαισθητικά, το επιχείρημα πάει ως εξής: δεν χρειάζεται να ψάχνουμε για κύκλους που έχουν το πολύ 68 τροχιές, όπου κάθε τροχιά αποτελείται από συνεχόμενα ανεβάσματα ακολουθούμενα από συνεχόμενα κατεβάσματα. Δείτε παρακάτω για μια ιδέα για το πώς θα μπορούσε κανείς να βρει άνω φράγμα για τα στοιχεία ενός κύκλου.

Υποστηρικτικά επιχειρήματα[Επεξεργασία | επεξεργασία κώδικα]

Αν και η εικασία Κόλατζ δεν έχει αποδειχθεί τυπικά, οι περισσότεροι μαθηματικοί που ασχολήθηκαν με το πρόβλημα πιστεύουν ότι η εικασία ισχύει, επειδή πειραματικές αποδείξεις και ευρεστικά επιχειρήματα την υποστηρίζουν.

Πειραματικές αποδείξεις[Επεξεργασία | επεξεργασία κώδικα]

Η εικασία έχει ελεγχθεί από τον υπολογιστή για όλες τις τιμές έως 260.[10] Όλες οι αρχικές τιμές που έχουν δοκιμαστεί μέχρι σήμερα καταλήγουν στην επανάληψη του κύκλου (4, 2, 1), που έχει μόνο τρεις όρους. Από αυτό το κάτω φράγμα για την τιμή εκκίνησης, έχει βρεθεί κατώτερο όριο για τον αριθμό των όρων επαναλαμβανόμενων κύκλων, εκτός του (4, 2, 1).[11] Όταν ανακαλύφθηκε αυτή η σχέση το 1981, ο τύπος έδωσε κάτω φράγμα με 35.400 όρους.[11]

Η απόδειξη που έδωσε ο υπολογιστής δεν είναι 'κανονική' απόδειξη ότι η εικασία Κόλατζ είναι αληθινή. Όπως φαίνεται σε διάφορες περιπτώσεις, όπως η εικασία Pólya, η εικασία Μέρτενς και ο αριθμός Skewes, μερικές φορές τα αντιπαραδείγματα για μια εικασία εντοπίζονται σε πολύ μεγάλους αριθμούς.

Ένα πιθανοτικό ευρεστικό επιχείρημα[Επεξεργασία | επεξεργασία κώδικα]

Αν κάποιος πάρει μόνο τους περιττούς αριθμούς με τη σειρά που παράγονται από την διαδικασία  του Κόλατζ, τότε κάθε περιττός αριθμός είναι, κατά μέσο όρο, μεγαλύτερος κατά τα 3/4 του προηγούμενου.[12] (Για την ακρίβεια, ο γεωμετρικός μέσος των λόγων των αποτελεσμάτων είναι 3/4.) Αυτό παράγει ένα ευρεστικό επιχείρημα ότι κάθε ακολουθία χαλαζιού θα πρέπει να φθίνει μακροπρόθεσμα, αν και αυτό δεν είναι απόδειξη για όλους τους κύκλους, παρά μόνον κατά της απόκλισης. Το επιχείρημα αυτό δεν είναι απόδειξη, επειδή υποθέτει ότι οι ακολουθίες χαλαζιού συναρμολογούνται από πιθανοτικά ασυσχέτιστα γεγονότα. (Ωστόσο, καθιερώνει αυστηρά ότι η 2-αδική επέκταση της συνάρτησης Κόλατζ  έχει δύο βήματα διαίρεσης για κάθε βήμα πολλαπλασιασμού για σχεδόν όλες τις 2-αδικές τιμές εκκίνησης.)

Αλλά ακόμη κι αν το πιθανοτικό επιχείρημα ήταν αυστηρό, αυτό πάλι θα συνεπαγόταν ότι η εικασία είναι σχεδόν σίγουρα αληθής για κάθε δεδομένο ακέραιο, που δεν συνεπάγεται απαραίτητα ότι είναι αληθής για όλους τους ακεραίους.

Αυστηρά όρια[Επεξεργασία | επεξεργασία κώδικα]

Αν και δεν γνωρίζουμε υπό την αυστηρή έννοια ότι όλοι οι θετικοί αριθμοί καταλήγουν στο 1 με την ακολουθία Κόλατζ, είναι γνωστό ότι πολλοί αριθμοί φτάνουν. Ειδικότερα, οι Krasikov και Lagarias έδειξαν ότι το πλήθος των ακεραίων στο διάστημα [1, x] που τελικά φτάνουν στο ένα είναι τουλάχιστον ανάλογο με το x0.84.[13]

Εναλλακτικές διατυπώσεις της εικασίας[Επεξεργασία | επεξεργασία κώδικα]

Αντίστροφη[Επεξεργασία | επεξεργασία κώδικα]

Τα πρώτα 21 επίπεδα του γράφου Κόλατζ όπως παράγεται από κάτω προς τα επάνω. Το γράφημα περιλαμβάνει όλους τους αριθμούς με μήκος τροχιάς 21 ή λιγότερο.

Υπάρχει και μια άλλη προσέγγιση για  να αποδειχθεί η εικασία, που χρησιμοποιεί την κάτω-προς-επάνω μέθοδο ανάπτυξης του λεγόμενου γράφου Κόλατζ. Ο γράφος Κόλατζ  είναι ένας γράφος που ορίζεται από την αντίστροφη σχέση

Έτσι, αντί να αποδείξουμε ότι όλοι οι θετικοί ακέραιοι καταλήγουν τελικά στο 1, μπορούμε να προσπαθήσουμε να αποδείξουμε ότι το 1 οδηγεί σε όλους τους θετικούς ακεραίους. Για κάθε ακέραιο , αν και μόνον αν (ανν) . Ισοδύναμα, ανν . Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο αν εξαιρέσουμε τον βρόχο 1-2-4 (τον αντίστροφο του κύκλου (4, 2, 1) της αρχικής συνάρτησης f όπως ορίζεται στην ενότητα Διατύπωση του προβλήματος αυτού του άρθρου).

Όταν η σχέση 3n+1 της συνάρτησης f αντικαθίσταται από τη "συντομευμένη" μορφή (3n+1)/2, ο γράφος Κόλατζ ορίζεται από την αντίστροφη σχέση,

Για κάθε ακέραιο n, ανν . Ισοδύναμα, ανν . Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο, αν εξαιρέσουμε τον βρόχο 1-2 (τον αντίστροφο του κύκλου (2, 1) της "συντομευμένης" συνάρτησης).

Εναλλακτικά, αντικαταστήστε το 3n+1 με το n' / H(n'), όπου n' = 3n+1 και H(n') είναι η μεγαλύτερη δύναμη του 2 που διαιρεί το n' (χωρίς να αφήνει υπόλοιπο). Η προκύπτουσα συνάρτηση f είναι μια απεικόνιση από περιττούς αριθμούς σε περιττούς αριθμούς. Τώρα, ας υποθέσουμε ότι για κάποιον περιττό αριθμό n, εφαρμογή αυτής της συνάρτησης k φορές καταλήγει στον αριθμό 1 (δηλαδή ). Τότε στο δυαδικό σύστημα, ο αριθμός n μπορεί να γραφτεί ως συνένωση των συμβολοσειρών wk wk-1 ... w1, όπου κάθε wh είναι πεπερασμένo και συνεχόμενo τμήμα της αναπαράστασης του 1 / 3h.[14] Η αναπαράσταση του n ως εκ τούτου περιέχει το επαναλαμβανόμενο τμήμα του 1 / 3h, όπου κάθε επαναλαμβανόμενο τμήμα μπορεί να περιστρέφεται και έπειτα να αναπαράγεται μέχρι έναν πεπερασμένο πλήθος δυαδικών ψηφίων. Αυτό συμβαίνει μόνο στη δυαδική αναπαράσταση.[15] Σύμφωνα με την εικασία, κάθε δυαδική συμβολοσειρά s που τελειώνει σε '1' μπορεί να επιτευχθεί με μια αναπαράσταση αυτής της μορφής (προθέτοντας μηδενικά '0' στο s).

Αφηρημένη μηχανή που υπολογίζει με βάση το δύο[Επεξεργασία | επεξεργασία κώδικα]

Επαναλαμβανόμενες εφαρμογές της συνάρτησης Κόλατζ μπορούν να αναπαρασταθούν ως μια αφηρημένη μηχανή που χειρίζεται συμβολοσειρές από δυαδικά ψηφία. Η μηχανή θα εκτελεί τα ακόλουθα τρία βήματα σε κάθε περιττό αριθμό, μέχρι να απομείνει το '1':

  1. Προσάρτησε '1' στα δεξιά της δυαδικής αναπαράστασης του αριθμού (οδηγεί στον αριθμό 2n+1).
  2. Πρόσθεσε τον παραπάνω αριθμό στον αρχικό αριθμό με δυαδική πρόσθεση (οδηγεί στο (2n+1) + n = 3n + 1).
  3. Αφαίρεσε όλα τα καταληκτικά '0' (δηλαδή επανειλημμένα διαιρεί δια δύο μέχρι το αποτέλεσμα να γίνει περιττό).

Αυτή η συνταγή ισοδυναμεί με τον υπολογισμό της ακολουθίας χαλαζιού στο δυαδικό σύστημα αρίθμησης.

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Ξεκινάμε με το 7 που στο δυαδικό σύστημα γράφεται 111. Προκύπτει η εξής ακολουθία χαλαζιού:

         111
        1111+
       10110
      10111+
     100010
    100011+
    110100
   11011+
  101000
 1011+
10000

Ακολουθία ισοτιμίας[Επεξεργασία | επεξεργασία κώδικα]

Για αυτή την ενότητα, θεωρήστε τη συνάρτηση Κόλατζ στην ελαφρώς τροποποιημένη της μορφή

Αυτό μπορεί να γίνει, διότι όταν το n είναι περιττό, το 3n + 1 είναι πάντα άρτιο.

Αν P(...) είναι η ισοτιμία του αριθμού, δηλαδή P(2n) = 0 και P(2n + 1) = 1, τότε μπορούμε να ορίσουμε την ακολουθία ισοτιμίας χαλαζιού (ή διάνυσμα ισοτιμίας) για έναν αριθμό n ως pi = P(ai), όπου a0 = n, και ένα ai+1 = f(ai).

Το ποια λειτουργία εκτελείται, (3n+1)/2 ή n/2, εξαρτάται από την ισοτιμία. Η ακολουθία ισοτιμίας είναι η ίδια με την αλληλουχία των λειτουργιών. 

Χρησιμοποιώντας αυτή τη μορφή για το f(n), μπορεί να αποδειχθεί ότι οι ακολουθίες ισοτιμίας για δύο αριθμούς m και n θα συμφωνούν στους πρώτους k όρους, αν και μόνον αν m και n είναι ισοδύναμα κατά modulo 2k. Αυτό συνεπάγεται ότι κάθε αριθμός είναι προσδιορίζεται μονοσήμαντα από την  ακολουθία ισοτιμίας του και  επιπλέον, ότι αν υπάρχουν πολλαπλοί κύκλοι στην ακολουθία χαλαζιού, τότε οι αντίστοιχοι κύκλοι ισοτιμίας πρέπει να είναι διαφορετικοί.[16][17]

Εφαρμόζοντας την  συνάρτηση f για k φορές στον αριθμό a·2k+b θα δώσει το αποτέλεσμα  a·3c + d, όπου d είναι το αποτέλεσμα της εφαρμογής της συνάρτησης f για k φορές στο b και το c είναι πόσοι περιττοί αριθμοί προέκυψαν κατά τη διαδικασία.

Σύστημα ετικετών[Επεξεργασία | επεξεργασία κώδικα]

Για την συνάρτηση Κόλατζ με τον τύπο

οι ακολουθία χαλαζιού μπορεί να υπολογιστεί από το εξαιρετικά απλό σύστημα 2-ετικετών με κανόνες παραγωγής abc, ba, caaa. Σε αυτό το σύστημα, ο θετικός ακέραιος n αντιπροσωπεύεται από μια σειρά από n a και η επανάληψη της λειτουργίας ετικέτας τερματίζεται σε οποιαδήποτε λέξη μήκους λιγότερου από 2 (προσαρμοσμένο από το De Mol.)

Η εικασία Κόλατζ ισοδύναμεί με τη δήλωση ότι αυτό το σύστημα ετικετών με μια αυθαίρετη πεπερασμένη συμβολοσειρά από a, όπως η αρχική λέξη, τελικά σταματά.

Επεκτάσεις σε ευρύτερα πεδία[Επεξεργασία | επεξεργασία κώδικα]

Επανάληψη σε όλους τους ακέραιους[Επεξεργασία | επεξεργασία κώδικα]

Μια προφανής επέκταση περιλαμβάνει όλους τους  ακέραιους, όχι μόνο τους θετικούς. Αφήνοντας στην άκρη τον τετριμμένο κύκλο 0 → 0, υπάρχουν συνολικά 4 γνωστοί μη-τετριμμένοι κύκλοι, στους οποίους καταλήγουν όλοι οι μη μηδενικοί ακέραιοι με την επαναληπτική εφαρμογή της f. Οι κύκλοι αυτοί παρατίθενται, ξεκινώντας με το γνωστό κύκλο για θετικά n.

Περιττές τιμές μαρκάρονται με έμφαση. Κάθε κύκλος παρουσιάζεται ξεκινώντας με το μέλος που έχει την μικρότερη απόλυτη τιμή (είναι πάντα περιττό).

Cycle Odd-value cycle length Full cycle length
1 → 4 → 2 → 1 1 3
−1 → −2 → −1 1 2
−5 → −14 → −7 → −20 → −10 → −5 2 5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 7 18

Η γενικευμένη εικασία Κόλατζ είναι ο ισχυρισμός ότι κάθε ακέραιος, με την επαναληπτική εφαρμογή της f, τελικά πέφτει σε έναν από τους τέσσερις μη-τετριμμένους κύκλους παραπάνω, ή είναι ο τετριμμένος κύκλος 0 → 0.

Επανάληψη με περιττούς παρονομαστές ή 2-αδικούς ακέραιους[Επεξεργασία | επεξεργασία κώδικα]

Η ακολουθία Κόλατζ  μπορεί να επεκταθεί σε (θετικούς ή αρνητικούς) ρητούς αριθμούς που έχουν περιττούς παρονομαστές όταν γραφτούν ως ανάγωγα κλάσματα. Ο αριθμός θεωρείται περιττός ή άρτιος ανάλογα με το αν το αριθμητής του κλάσματος είναι περιττός ή άρτιος. Σχετική είναι και η επέκταση της ακολουθίας Κόλατζ στο δακτύλιο των 2-αδικών ακεραίων, που περιέχει το δακτύλιο των ρητών με περιττούς παρονομαστές ως υπο-δακτύλιο.

Οι ακολουθίες ισοτιμίας όπως ορίστηκαν παραπάνω, δεν είναι πλέον μοναδικές στους ρητούς. Ωστόσο, μπορεί να αποδειχθεί ότι κάθε πιθανός κύκλος ισοτιμίας είναι η ακολουθία ισοτιμίας για ακριβώς ένα κλάσμα: αν ένας κύκλος έχει μήκος n και περιλαμβάνει περιττούς αριθμούς ακριβώς m φορές στις θέσεις k0, ..., km-1, τότε το μοναδικό κλάσμα που παράγει αυτό τον κύκλο ισοτιμίας είναι

 

 

 

 

(1)

Για παράδειγμα, ο κύκλος ισοτιμίας (1 0 1 1 0 0 1) έχει μήκος 7 και έχει 4 περιττούς αριθμούς στις θέσεις 0, 2, 3, και 6. Το μοναδικό κλάσμα που δημιουργεί αυτόν τον κύκλο ισοτιμίας

ενώ ο πλήρης κύκλος είναι: 151/47 → 250/47 → 125/47 → 211/47 → 340/47 → 170/47 → 85/47 → 151/47

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

(0 1 1 0 0 1 1) →
(1 1 0 0 1 1 0) →
(1 0 0 1 1 0 1) →
(0 0 1 1 0 1 1) →
(0 1 1 0 1 1 0) →
(1 1 0 1 1 0 0) →

Επίσης, για μοναδικότητα, η ακολουθία ισοτιμίας θα πρέπει να είναι "πρώτη", δηλαδή, μη κατατμήσιμη σε πανομοιότυπες υπο-ακολουθίες. Για παράδειγμα, η ακολουθία ισοτιμίας (1 1 0 0 1 1 0 0) μπορεί να χωριστεί σε δύο πανομοιότυπες υπο-ακολουθίες (1 1 0 0)(1 1 0 0). Υπολογίζοντας το κλάσμα της 8-ψήφιας  ακολουθίας έχουμε

(1 1 0 0 1 1 0 0) →

Αλλά όταν απλοποιηθεί στο ανάγωγο κλάσμα {5/7}, συμπίπτει με το κλάσμα της 4-ψήφιας υπο-ακολουθίας

(1 1 0 0) →

Και αυτό γιατί η 8-ψήφια ακολουθία ισοτιμίας στην πραγματικότητα αντιπροσωπεύει τα δύο κυκλώματα του βρόχου που ορίζεται από την 4-ψήφια ακολουθία ισοτιμίας.

Στο πλαίσιο αυτό, η εικασία Κόλατζ είναι ισοδύναμη με το να λέμε ότι (0 1) είναι ο μόνος κύκλος που δημιουργείται από  θετικούς ακέραιους αριθμούς (πχ, 1 και 2).

Κυκλικά όρια[Επεξεργασία | επεξεργασία κώδικα]

Η εξίσωση 1 μας δίνει επίσης μια ιδέα για το πώς μπορεί κανείς να αποδείξει ότι δεν υπάρχουν κύκλοι με συγκεκριμένα μήκη. Για έναν υποθετικό κύκλο μήκους n, ο αριθμητής φράσσεται άνω από το 3n - 2n (αυτό αντιστοιχεί σε ένα κύκλο με περιττούς αριθμούς μόνον). Ένα κάτω φράγμα για τον παρονομαστή μπορεί να ληφθεί θεωρώντας το n/m ως μια βέλτιστη κλασματική προσέγγιση του log(3)/log(2). Αυτά μαζί δίνουν ένα άνω φράγμα για το μοναδικό κλάσμα που παράγει ένα κύκλο μήκους n. Αν αυτό το άνω φράγμα είναι μικρότερο από τον μεγαλύτερο αριθμό για τον οποίο η εικασία έχει επαληθευτεί ότι ισχύει, τότε ένας κύκλος μήκους n είναι αδύνατος.

Επανάληψη σε πραγματικούς ή μιγαδικούς αριθμούς[Επεξεργασία | επεξεργασία κώδικα]

Γράφημα ιστού αράχνης για την τροχιά 10-5-8-4-2-1-2-1-2-1-... στην πραγματική συνιστώσα της απεικόνισης Κόλατζ (βελτιστοποιημένη με την αντικατάσταση "3n+1" με "(3n+1)/2")

Η απεικόνιση Κόλατζ μπορεί να θεωρηθεί ως περιορισμός στους ακέραιους της μιγαδικής απεικόνισης

το οποίο απλοποιείται σε .

Αν η τυπική απεικόνιση Κόλατζ που ορίστηκε παραπάνω βελτιστοποιηθεί, αντικαθιστώντας την σχέση 3n+1 με την "συντόμευση" (3n+1)/2, μπορεί να θεωρηθεί ως περιορισμός στους ακέραιους της μιγαδικής απεικόνισης

που απλοποιείται σε.

Το φράκταλ του Κόλατζ[Επεξεργασία | επεξεργασία κώδικα]

Η επανάληψη της βελτιστοποιημένης απεικόνισης παραπάνω στο μιγαδικό επίπεδο παράγει το φράκταλ του Κόλατζ.

Η επανάληψη κατά μήκος του άξονα των πραγματικών διερευνήθηκε από τον Chamberland[18] και στο επίπεδο των μιγαδικών από τους Letherman, Schleicher, and Wood.[19]

Φράκταλ της απεικόνισης Κόλατζ σε μια γειτονιά του πραγματικού άξονα

Βελτιστοποιήσεις[Επεξεργασία | επεξεργασία κώδικα]

Αντιστάθμιση χρόνου-χώρου[Επεξεργασία | επεξεργασία κώδικα]

Η ενότητα ακολουθία ισοτιμίας παραπάνω δίνει έναν τρόπο για να επιταχύνουμε την προσομοίωση της ακολουθίας. Για να μεταβούμε προς τα εμπρός k βήματα σε κάθε επανάληψη (χρησιμοποιώντας την συνάρτηση f από εκείνη την ενότητα), χωρίζουμε τον τρέχοντα αριθμό σε δύο μέρη, b (τα k λιγότερο σημαντικά δυαδικά ψηφία, ερμηνεύμενα ως ακέραιο) και a (τα υπόλοιπα ψηφία ως ακέραιο). Το αποτέλεσμα του άλματος εμπρός κατά k βήματα προκύπτει ως:

f k(a 2k + b) = a 3c(b) + d(b)

Οι πίνακες c και d είναι υπολογισμένοι εκ των προτέρων για όλους τους πιθανούς αριθμούς b μήκους k-bit, όπου d(b) είναι το αποτέλεσμα της εφαρμογής της συνάρτησης fk φορές στο b και c(b) είναι ο αριθμός των περιττών αριθμών που συναντούν στη διαδρομή.[20] Για παράδειγμα, αν k=5, μπορείτε να μεταβείτε 5 βήματα προς τα εμπρός για κάθε επανάληψη, διαχωρίζοντας τα 5 λιγότερο σημαντικά δυαδικά ψηφία του αριθμού και χρησιμοποιώντας:

c(0..31) = {0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5}
d(0..31) = {0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242}.

Αυτό απαιτεί 2k προεπεξεργασίες και αποθηκεύσεις για να επιταχύνει τον υπολογισμό κατά ένα συντελεστή k, αντισταθμίζοντας χρόνο με χώρο.

Περιορισμοί με υπόλοιπα[Επεξεργασία | επεξεργασία κώδικα]

Ειδικά για την αναζήτηση αντιπαραδείγματος στην εικασία Κόλατζ, η παραπάνω προεπεξεργασία οδηγεί σε μία ακόμη πιο σημαντική επιτάχυνση, που χρησιμοποιείται από τον Tomas Oliveira e Silva για να επιβεβαιώσει υπολογιστικά την εικασία Κόλατζ για μεγάλες τιμές του n. Εάν, για δεδομένα b και k, η ανισότητα

f k(a 2k+b) = a 3c(b) + d(b) < a 2k+b

ισχύει για όλα τα a, τότε το πρώτο αντιπαράδειγμα, αν υπάρχει, δεν μπορεί να είναι b mod 2k.[11] Έτσι, το πρώτο αντιπαράδειγμα πρέπει να είναι περιττός, επειδή f(2n)=n, μικρότερο του 2n και πρέπει να είναι 3 mod 4, επειδή f2(4n+1) = 3n+1, μικρότερο του 4n+1. Για κάθε αρχική τιμή a, η οποία δεν είναι ένα αντιπαράδειγμα για την εικασία Κόλατζ, υπάρχει ένα k για το οποίο μια τέτοια ανισότητα ισχύει, οπότε ο έλεγχος της εικασίας Κόλατζ για μια αρχική τιμή ισοδυναμεί με τον έλεγχο μιας ολόκληρης κλάσης σύγκλισης. Καθώς το k αυξάνεται, η αναζήτηση αρκεί να ελέγχει τα υπόλοιπα b που δεν εξαλείφθηκαν από τις μικρότερες τιμές του k. Μόνο ένα εκθετικά μικρό κλάσμα των υπολοίπων επιβιώνει.[16] Για παράδειγμα, τα μόνα επιζόντα υπόλοιπα mod 32 είναι 7, 15, 27, 31.

Συνάρτηση Συρακουσών[Επεξεργασία | επεξεργασία κώδικα]

Αν k είναι ένας περιττός ακέραιος, τότε ο 3k+1 είναι άρτιος και έτσι 3k+1 = 2ak' με k' περιττό και a≥1. Η συνάρτηση Συρακουσών είναι η συνάρτηση f από το σύνολο I των περιττών ακεραίων προς τον εαυτό του, για την οποία f(k)=k' (ακολουθία A075677 στην OEIS).

Μερικές ιδιότητες της συνάρτησης Συρακουσών είναι:

  • . (Επειδή )
  • Γενικότερα: Για όλα τα και περιττά , (Εδώ συμβολίζει τη επαναληπτική σύνθεση συνάρτησης.)
  • Για όλα τα περιττά ,

Η εικασία Κόλατζ είναι ισοδύναμη με τη δήλωση ότι, για όλα τα k στο I υπάρχει ένας ακέραιος n≥1, τέτοιος ώστε fn(k) = 1.

Μη αποφασίσιμες γενικεύσεις[Επεξεργασία | επεξεργασία κώδικα]

Το 1972, ο Τζον Χόρτον Κόνγουεϊ (John Horton Conway) απέδειξε ότι μια φυσική γενίκευση του προβλήματος Κόλατζ είναι αλγοριθμικά μη αποφασίσιμη.[21]

Συγκεκριμένα, εξέτασε συναρτήσεις της μορφής

όπου είναι ρητοί αριθμοί οι οποίοι επιλέγονται έτσι ώστε η να δίνει πάντα ακέραια τιμή.

Η συνάρτηση Κόλατζ δίνεται από , , ,, . Ο Conway απέδειξε ότι το πρόβλημα:

Δεδομένων των g και n, θα φτάσει η επαναληπτική ακολουθία gk(n) στο 1;

είναι μη αποφασίσιμη, εκφράζοντας το πρόβλημα τερματισμού με αυτόν τον τρόπο. Πιο κοντά στο πρόβλημα του Κόλατζ είναι το ακόλουθο καθολικά ποσοτικοποιημένο πρόβλημα:

Δεδομένης της g, η επαναληπτική ακολουθία gk(n) θα φθάσει στο 1, για όλα τα n>0;

Τροποποιώντας την προϋπόθεση με αυτό τον τρόπο μπορεί να κάνει το πρόβλημα πιο δύσκολο ή πιο εύκολο να λυθεί (διαισθητικά, είναι πιο δύσκολο να δικαιολογηθεί μια θετική απάντηση, αλλά μπορεί να είναι πιο εύκολο να δικαιολογηθεί η αρνητική). Οι Kurtz και Simon[22] απέδειξαν ότι το παραπάνω πρόβλημα είναι στην πραγματικότητα μη αποφασίσιμο και ακόμα υψηλότερα στην αριθμητική ιεραρχία, και πιο συγκεκριμένα είναι -πλήρες. Αυτό το επίπεδο δυσκολίας ισχύει ακόμη και αν κάποιος περιορίσει την κλάση των συναρτήσεων g σταθεροποιώντας το modulo συντελεστή P στο 6480.[23]

Η Απόλυτη Πρόκληση: Το  πρόβλημα 3x+1[Επεξεργασία | επεξεργασία κώδικα]

Αυτός ο τόμος,[24] επιμελημένος από τον Jeffrey Lagarias και δημοσιευμένος από την Αμερικανική Μαθηματική Εταιρεία, είναι μια συλλογή πληροφοριών σχετικά με την εικασία Κόλατζ, τις μεθόδους προσέγγισης και τις γενικεύσεις της. Περιλαμβάνει δύο επισκοπήσεις από τον επιμελητή και πέντε από άλλους συγγραφείς, σχετικά με την ιστορία του προβλήματος, τις γενικεύσεις, στατιστικές προσεγγίσεις και αποτελέσματα από την θεωρία υπολογισμού. Περιλαμβάνει, επίσης, ανατυπώσεις των πρώτων δημοσιεύσεων σχετικά με το θέμα (συμπεριλαμβανομένης μιας καταχώρισης από τον Λόθαρ Κόλατζ).

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

  1. Maddux, Cleborne D.. Johnson, D. Lamont (1997). Logo: A Retrospective. New York: Haworth Press, σελ. 160. ISBN 0-7890-0374-0. 
  2. Pickover, Clifford A. (2001). Wonders of Numbers. Oxford: Oxford University Press, σελ. 116–118. ISBN 0-19-513342-0. 
  3. «Hailstone Number». MathWorld. Wolfram Research. 
  4. Hofstadter, Douglas R. (1979). Gödel, Escher, Bach. New York: Basic Books, σελ. 400–402. ISBN 0-465-02685-0. 
  5. Friendly, Michael (1988). Advanced Logo: A Language for Learning. Hillsdale, New Jersey, USA: Lawrence Erlbaum Associates. ISBN 0-89859-933-4. 
  6. Guy, Richard K. (2004). Unsolved problems in number theory (3rd έκδοση). Springer-Verlag, "E17: Permutation Sequences". ISBN 0-387-20860-7. Zbl 1058.11001.  Cf pp. 336–337.
  7. R. K. Guy: Don't try to solve these problems, Amer. Math. Monthly, 90 (1983), 35–41. Ο Έρντος εννοεί ότι δεν υπάρχουν ισχυρά εργαλεία για το χειρισμό τέτοιων προβλημάτων.
  8. 8,0 8,1 Simons, J.; de Weger, B.; "Theoretical and computational bounds for m-cycles of the 3n+1 problem", Acta Arithmetica (on-line version 1.0, November 18, 2003), 2005.
  9. Steiner, R. P.; "A theorem on the syracuse problem", Proceedings of the 7th Manitoba Conference on Numerical Mathematics, pages 553–559, 1977.
  10. Silva, Tomás Oliveira e Silva. «Computational verification of the 3x+1 conjecture». Ανακτήθηκε στις 13 May 2015. 
  11. 11,0 11,1 11,2 Garner, Lynn E. «On The Collatz 3n + 1 Algorithm» (PDF). Ανακτήθηκε στις 27 March 2015. 
  12. Πρότυπο:Named ref section "A heuristic argument".
  13. Krasikov, Ilia; Lagarias, Jeffrey C. (2003). «Bounds for the 3x + 1 problem using difference inequalities». Acta Arithmetica 109 (3): 237–258. doi:10.4064/aa109-3-4. MR 1980260Πρότυπο:Inconsistent citations .
  14. Colussi, Livio (9 September 2011). «The convergence classes of Collatz function». Theoretical Computer Science 412 (39): 5409–5419. doi:10.1016/j.tcs.2011.05.056. 
  15. Hew, Patrick Chisan (7 March 2016). «Working in binary protects the repetends of 1/3h: Comment on Colussi's ‘The convergence classes of Collatz function’». Theoretical Computer Science 618: 135–141. doi:10.1016/j.tcs.2015.12.033. 
  16. 16,0 16,1 Jeffrey C. Lagarias (1985). The 3x + 1 problem and its generalizations. The American Mathematical Monthly 92(1): 3-23.
  17. Terras, Riho (1976), «A stopping time problem on the positive integers», Polska Akademia Nauk 30 (3): 241–252, http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf 
  18. Marc Chamberland. A continuous extension of the 3x+1 problem to the real line. Dynam. Contin. Discrete Impuls Systems 2: 4 (1996), 495–509.
  19. Simon Letherman, Dierk Schleicher, and Reg Wood: The (3n+1)-Problem and Holomorphic Dynamics. Experimental Mathematics 8: 3 (1999), 241–252.
  20. Scollo, Giuseppe (2007), «Looking for Class Records in the 3x+1 Problem by means of the COMETA Grid Infrastructure», Grid Open Days at the University of Palermo, http://www.dmi.unict.it/~scollo/seminars/gridpa2007/CR3x+1paper.pdf 
  21. Conway, John H. (1972), «Unpredictable Iterations», Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, σελ. 49–52 
  22. Kurtz, Stuart A.. Simon, Janos (2007). «The Undecidability of the Generalized Collatz Problem». Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007, σελ. 542–553. doi:10.1007/978-3-540-72504-6_49. ISBN 3-540-72503-2. http://books.google.com/books?id=mhrOkx-xyJIC&pg=PA542. 
  23. Ben-Amram, Amir M. (2015), «Mortality of iterated piecewise affine functions over the integers: Decidability and complexity», Computability 1 (1): 19–56, doi:10.3233/COM-150032 
  24. Lagarias, Jeffrey C., επιμ. (2010). The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. ISBN 978-0-8218-4940-8. Zbl 1253.11003. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]