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

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

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

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

Διατύπωση προβλήματος

Αριθμοί από το 1 έως το 9999 και ο αντίστοιχος συνολικός χρόνος τερματισμού τους

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

Διάστημα επανάληψης για εισόδους από το 2 έως 10 εκατομμύρια

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

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

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

$f(n)=\{\begin{array}{cc}n/2,& \text{αν }nmod2=0\\ 3n+1,& \text{αν }nmod2=1\end{array}$

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

$a_i=\{\begin{array}{cc}n& \text{για }i=0\\ f(a_{i-1})& \text{για }i>0\end{array}$

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

Το μικρότερο 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 Πρότυπο: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, ... Πρότυπο: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, ... Πρότυπο: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, ... Πρότυπο:OEIS

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

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

Απεικονίσεις

• 
  Κατευθυνόμενος γράφος που δείχνει τις τροχιές για μικρούς αριθμούς στον χάρτη της ακολουθίας. Η εικασία Κόλατζ ισοδυναμεί με την πρόταση ότι όλα τα μονοπάτια τελικά καταλήγουν στο 1.
• 
  Κατευθυνόμενος γράφος που δείχνει τις τροχιές των αριθμών μέχρι το 1000.
• 
  Ο άξονας x των τετμημένων αντιστοιχεί στον αριθμό έναρξης και ο άξονας y των τεταγμένων δείχνει τον μεγαλύτερο αριθμό που φτάνει η ακολουθία.

Κύκλοι

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

Ο τύπος ενός κύκλου μπορεί να οριστεί χρησιμοποιώντας τον "συντομευμένο" ορισμό της συνάρτησης Κόλατζ, $f(n)=(3n+1)/2$ για περιττά n και$f(n)=n/2$ για άρτια n. Ένας κύκλος είναι μια ακολουθία $(a_0,a_1,\dots a_q)$ όπου$f(a_0)=a_1$, $f(a_1)=a_2$ και ούτω καθεξής, μέχρι$f(a_q)=a_0$ σε κλειστό βρόχο. Σύμφωνα με αυτό τον ορισμό, ο μόνος γνωστός κύκλος είναι ο τετριμμένος (1, 2). Αν και το 4 είναι μέρος του τετριμμένου κύκλου για την αρχική συνάρτηση Κόλατζ, δεν ανήκει στον κύκλο της "συντομευμένης" συνάρτησης (1, 2). 

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

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

Υποστηρικτικά επιχειρήματα

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

Πειραματικές αποδείξεις

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

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

Ένα πιθανοτικό ευρεστικό επιχείρημα

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

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

Αυστηρά όρια

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

Εναλλακτικές διατυπώσεις της εικασίας

Αντίστροφη

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

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

$R(n)=\{\begin{array}{cc}\{2n\}& \text{αν }nmod6=0,1,2,3,5\\ \{2n,(n-1)/3\}& \text{αν }nmod6=4\end{array}$

Έτσι, αντί να αποδείξουμε ότι όλοι οι θετικοί ακέραιοι καταλήγουν τελικά στο 1, μπορούμε να προσπαθήσουμε να αποδείξουμε ότι το 1 οδηγεί σε όλους τους θετικούς ακεραίους. Για κάθε ακέραιο $n$, $nmod2=1$ αν και μόνον αν (ανν) $(3n+1)mod6=4$. Ισοδύναμα, $[(n-1)/3]mod2=1$ ανν $nmod6=4$. Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο αν εξαιρέσουμε τον βρόχο 1-2-4 (τον αντίστροφο του κύκλου (4, 2, 1) της αρχικής συνάρτησης f όπως ορίζεται στην ενότητα Διατύπωση του προβλήματος αυτού του άρθρου).

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

$R(n)=\{\begin{array}{cc}\{2n\}& \text{αν }nmod3=0,1\\ \{2n,(2n-1)/3\}& \text{αν }nmod3=2\end{array}$

Για κάθε ακέραιο n, $nmod2=1$ ανν $[(3n+1)/2]mod3=2$. Ισοδύναμα, $[(2n-1)/3]mod2=1$ ανν $nmod3=2$. Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο, αν εξαιρέσουμε τον βρόχο 1-2 (τον αντίστροφο του κύκλου (2, 1) της "συντομευμένης" συνάρτησης).

Εναλλακτικά, αντικαταστήστε το 3n+1 με το n' / H(n'), όπου n' = 3n+1 και H(n') είναι η μεγαλύτερη δύναμη του 2 που διαιρεί το n' (χωρίς να αφήνει υπόλοιπο). Η προκύπτουσα συνάρτηση f είναι μια απεικόνιση από περιττούς αριθμούς σε περιττούς αριθμούς. Τώρα, ας υποθέσουμε ότι για κάποιον περιττό αριθμό n, εφαρμογή αυτής της συνάρτησης k φορές καταλήγει στον αριθμό 1 (δηλαδή $f^k(n)=1$). Τότε στο δυαδικό σύστημα, ο αριθμός n μπορεί να γραφτεί ως συνένωση των συμβολοσειρών w_k w_k-1 ... w₁, όπου κάθε w_h είναι πεπερασμένo και συνεχόμενo τμήμα της αναπαράστασης του 1 / 3^h. Η αναπαράσταση του n ως εκ τούτου περιέχει το επαναλαμβανόμενο τμήμα του 1 / 3^h, όπου κάθε επαναλαμβανόμενο τμήμα μπορεί να περιστρέφεται και έπειτα να αναπαράγεται μέχρι έναν πεπερασμένο πλήθος δυαδικών ψηφίων. Αυτό συμβαίνει μόνο στη δυαδική αναπαράσταση. Σύμφωνα με την εικασία, κάθε δυαδική συμβολοσειρά 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

Ακολουθία ισοτιμίας

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

$f(n)=\{\begin{array}{cc}n/2& \text{αν }nmod2=0\\ (3n+1)/2& \text{αν }nmod2=1\end{array}$

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

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

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

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

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

Σύστημα ετικετών

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

$f(n)=\{\begin{array}{cc}n/2& \text{αν }nmod2=0\\ (3n+1)/2& \text{αν }nmod2=1\end{array}$

οι ακολουθία χαλαζιού μπορεί να υπολογιστεί από το εξαιρετικά απλό σύστημα 2-ετικετών με κανόνες παραγωγής a→ bc, b → a, c → aaa. Σε αυτό το σύστημα, ο θετικός ακέραιος 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 φορές στις θέσεις k₀, ..., k_m-1, τότε το μοναδικό κλάσμα που παράγει αυτό τον κύκλο ισοτιμίας είναι

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

$\frac{3^3{2}^0+3^2{2}^2+3^1{2}^3+3^0{2}^6}{2^7-3^4}=\frac{151}{47},$

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

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

(0 1 1 0 0 1 1) → $\frac{3^3{2}^1+3^2{2}^2+3^1{2}^5+3^0{2}^6}{2^7-3^4}=\frac{250}{47}$

(1 1 0 0 1 1 0) → $\frac{3^3{2}^0+3^2{2}^1+3^1{2}^4+3^0{2}^5}{2^7-3^4}=\frac{125}{47}$

(1 0 0 1 1 0 1) → $\frac{3^3{2}^0+3^2{2}^3+3^1{2}^4+3^0{2}^6}{2^7-3^4}=\frac{211}{47}$

(0 0 1 1 0 1 1) → $\frac{3^3{2}^2+3^2{2}^3+3^1{2}^5+3^0{2}^6}{2^7-3^4}=\frac{340}{47}$

(0 1 1 0 1 1 0) → $\frac{3^3{2}^1+3^2{2}^2+3^1{2}^4+3^0{2}^5}{2^7-3^4}=\frac{170}{47}$

(1 1 0 1 1 0 0) → $\frac{3^3{2}^0+3^2{2}^1+3^1{2}^3+3^0{2}^4}{2^7-3^4}=\frac{85}{47}$

Επίσης, για μοναδικότητα, η ακολουθία ισοτιμίας θα πρέπει να είναι "πρώτη", δηλαδή, μη κατατμήσιμη σε πανομοιότυπες υπο-ακολουθίες. Για παράδειγμα, η ακολουθία ισοτιμίας (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) → $\frac{3^3{2}^0+3^2{2}^1+3^1{2}^4+3^0{2}^5}{2^8-3^4}=\frac{125}{175}$

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

(1 1 0 0) → $\frac{3^1{2}^0+3^0{2}^1}{2^4-3^2}=\frac{5}{7}.$

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

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

Κυκλικά όρια

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

Επανάληψη σε πραγματικούς ή μιγαδικούς αριθμούς

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

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

${\displaystyle }$$f(z)=\frac{1}{2}z{\cos }^2\left(\frac{\pi }{2}z\right)+(3z+1){\sin }^2\left(\frac{\pi }{2}z\right)$

το οποίο απλοποιείται σε $\frac{1}{4}(2+7z-(2+5z)\cos (\pi z))$.

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

${\displaystyle }$$f(z)=\frac{1}{2}z{\cos }^2\left(\frac{\pi }{2}z\right)+\frac{(3z+1)}{2}{\sin }^2\left(\frac{\pi }{2}z\right)$

που απλοποιείται σε${\displaystyle }$$\frac{1}{4}(1+4z-(1+2z)\cos (\pi z))$.

Το φράκταλ του Κόλατζ

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

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

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

Βελτιστοποιήσεις

Αντιστάθμιση χρόνου-χώρου

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

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

Οι πίνακες c και d είναι υπολογισμένοι εκ των προτέρων για όλους τους πιθανούς αριθμούς b μήκους k-bit, όπου d(b) είναι το αποτέλεσμα της εφαρμογής της συνάρτησης f, k φορές στο b και c(b) είναι ο αριθμός των περιττών αριθμών που συναντούν στη διαδρομή. Για παράδειγμα, αν 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}.

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

Περιορισμοί με υπόλοιπα

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

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

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

Συνάρτηση Συρακουσών

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

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

• $\mathrm{\forall }k\in I,f(4k+1)=f(k)$. (Επειδή $3(4k+1)+1=12k+4=4(3k+1)$ )
• Γενικότερα: Για όλα τα $p\ge 1$ και περιττά $h$, $f^{p-1}(2^{p}h-1)=2\cdot 3^{p-1}h-1$ (Εδώ $f^{p-1}$ συμβολίζει τη επαναληπτική σύνθεση συνάρτησης.)
• Για όλα τα περιττά $h$, $f(2h-1)\le \frac{3h-1}{2}$

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

Μη αποφασίσιμες γενικεύσεις

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

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

$g(n)=a_{i}n+b_i,nmodP=i$

όπου $a_0,b_0,\dots ,a_{P-1},b_{P-1}$ είναι ρητοί αριθμοί οι οποίοι επιλέγονται έτσι ώστε η $g(n)$ να δίνει πάντα ακέραια τιμή.

Η συνάρτηση Κόλατζ δίνεται από $P=2$, $a_0=1/2$, $b_0=0$,$a_1=3$, $b_1=1$. Ο Conway απέδειξε ότι το πρόβλημα:

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

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

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

Τροποποιώντας την προϋπόθεση με αυτό τον τρόπο μπορεί να κάνει το πρόβλημα πιο δύσκολο ή πιο εύκολο να λυθεί (διαισθητικά, είναι πιο δύσκολο να δικαιολογηθεί μια θετική απάντηση, αλλά μπορεί να είναι πιο εύκολο να δικαιολογηθεί η αρνητική). Οι Kurtz και Simon απέδειξαν ότι το παραπάνω πρόβλημα είναι στην πραγματικότητα μη αποφασίσιμο και ακόμα υψηλότερα στην αριθμητική ιεραρχία, και πιο συγκεκριμένα είναι ${\mathrm{\Pi }}_2^0$-πλήρες. Αυτό το επίπεδο δυσκολίας ισχύει ακόμη και αν κάποιος περιορίσει την κλάση των συναρτήσεων g σταθεροποιώντας το modulo συντελεστή P στο 6480.

Η Απόλυτη Πρόκληση: Το  πρόβλημα 3x+1

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

Δείτε επίσης

• Ημιομάδα 3''x''+1
• Αριθμητική υπολοίπων

Εξωτερικοί σύνδεσμοι

• Η σελίδα 3x+1 του Keith Matthews: Επισκόπηση προόδου μαζί με διάφορα προγράμματα.
• Ένα έργο κατανεμημένου υπολογισμου BOINC) που επιβεβαιώνει την εικασία Κόλατζ για μεγάλες τιμές.
• Ένα σε εξελίξη έργο κατανεμημένου υπολογισμου του Eric Roosendaal επιβεβαιώνει την εικασία Κόλατζ για όλο και μεγαλύτερες τιμές.
• Άλλο ένα σε εξέλιξη έργο κατανεμημένου υπολογισμου του Tomás Oliveira e Silva που συνεχίζει να επιβεβιώνει την εικασία Κόλατζ (με λιγότερες στατιστικές από τη σελίδα του Eric Roosendaal's, αλλά με μεγαλύτερη πρόοδο).
• Μία διαδραστική εφαρμογή που χρησιμοποιεί υψηλής ακρίβειας αριθμιτική.
• Πρότυπο:MathWorld
• Πρότυπο:Planetmath reference.
• Πρότυπο:YouTube.
• Μονοπάτια Κόλατζ από τον Jesse Nochella, διαδραστική εφαρμογή στο Wolfram.
• Collatz cycles? Περί κύκλων, πολύ βασικό, περιέχει μερικούς ασυνήθιστους κύκλους (HTML).
• Collatz cycles? Περί βρόχων, συμπυκνωμένο κείμενο, μάλλον βασικό (PDF).
• Μία διαδραστική εφαρμογή της ακολουθίας Κόλατζ για τον αριθμό 2Πρότυπο:Sup + 1 σε βάση 2.