Προβολή πηγαίου κώδικα για τη σελίδα Εικασία του Κόλατζ

Η '''εικασία του Κόλατζ''' είναι μια [[εικασία]] στα [[μαθηματικά]] η οποία πήρε την ονομασία της από τον [[Λόθαρ Κόλατζ]] (''Lothar Collatz''), ο οποίος την πρότεινε για πρώτη φορά το [[1937]]. Η εικασία είναι επίσης γνωστή ως '''εικασία 3n+1''', '''εικασία Ούλαμ''' από τον [[Στανίσουαφ Ούλαμ]], '''πρόβλημα Κακουτάνι''' από τον [[Σιζούο Κακουτάνι]] (''Shizuo Kakutani''), '''εικασία Θουέιτς''' από τον [[Μπράιν Θουέιτς]] (''Bryan Thwaites''), '''αλγόριθμος του Χάσε''' από τον [[Χέλμουτ Χάσε]] (''Helmut Hasse''), ή '''πρόβλημα των Συρακουσών'''.<ref>{{cite book |title=Logo: A Retrospective |last=Maddux |first=Cleborne D. |authorlink= |author2=Johnson, D. Lamont |year=1997 |publisher=Haworth Press |location=New York |isbn=0-7890-0374-0 |page=160 |pages= }}</ref> Η ακολουθία των αριθμών που εμπλέκονται αναφέρεται ως '''ακολουθία χαλαζιού''' (επειδή οι τιμές συνήθως υπόκεινται σε πολλαπλές καταβάσεις και αναβάσεις σαν τους [[Χαλάζι|κόκκους του χαλαζιού]] σε ένα σύννεφο,<ref>{{cite book |title=Wonders of Numbers |last=Pickover |first=Clifford A. |year=2001 |publisher=Oxford University Press |location=Oxford |isbn=0-19-513342-0 |page= |pages=116–118 |url=https://archive.org/details/wondersofnumbers0000pick}}</ref><ref name="hn">{{cite web|title=Hailstone Number|url=http://mathworld.wolfram.com/HailstoneNumber.html|work=MathWorld|publisher=Wolfram Research}}</ref> είτε ως '''θαυμαστοί αριθμοί'''.<ref>{{cite book |title=[[Gödel, Escher, Bach]] |last=Hofstadter |first=Douglas R. |authorlink=Douglas Hofstadter |year=1979 |publisher=Basic Books |location=New York |isbn=0-465-02685-0 |page= |pages=[https://archive.org/details/godelescherbach00doug/page/400 400–402] |url= }}</ref>

Η εικασία συνοψίζεται ως εξής. Πάρτε οποιοδήποτε θετικό ακέραιο ''n''. Αν ο ''n'' είναι άρτιος, διαιρέστε τον δια το 2, για να πάρετε το ''n''/2. Εάν ο ''n'' είναι περιττός, πολλαπλασιάστε τον επί 3 και προσθέστε 1 για να πάρετε το 3''n''+1. Επαναλάβετε τη διαδικασία (η οποία έχει χαρακτηριστεί ως "Μισό Ή Τριπλό Συν Ένα", αγγλικά "Half Or Triple Plus One, HOTPO<ref>{{cite book |title=Advanced Logo: A Language for Learning|language=en|last=Friendly |first=Michael |year=1988 |publisher=Lawrence Erlbaum Associates |location=Hillsdale, New Jersey, USA |isbn=0-89859-933-4 |page= |pages= |url=https://archive.org/details/advancedlogolang0000frie}}</ref>) επ' αόριστον. Κατά την εικασία, από όποιο αριθμό κι αν ξεκινήσετε, θα καταλήξετε πάντα στο ένα.

Ο [[Πωλ Έρντος]] δήλωσε σχετικά με την εικασία του Κόλατζ: "Τα μαθηματικά μπορεί να μην είναι έτοιμα για τέτοια προβλήματα."<ref name="Guy (2004)"/> Επίσης, πρόσφερε $500 για την λύση του.<ref>R. K. Guy: Don't try to solve these problems, ''Amer. Math. Monthly'', '''90''' (1983), 35–41. Ο Έρντος εννοεί ότι δεν υπάρχουν ισχυρά εργαλεία για το χειρισμό τέτοιων προβλημάτων.</ref>

==Διατύπωση προβλήματος==
[[Αρχείο:Collatz-stopping-time.svg|δεξιά|μικρογραφία|311x311εσ|Αριθμοί από το 1 έως το 9999 και ο αντίστοιχος συνολικός χρόνος τερματισμού τους]]
[[Αρχείο:CollatzStatistic100million.png|class=cx-highlight|μικρογραφία|300x300εσ|Ιστόγραμμα των συνολικών χρόνων τερματισμού για τους αριθμούς 1 έως 100 εκατομμύρια. Ο συνολικός χρόνος τερματισμού είναι στον άξονα των x, η συχνότητα στον άξονα y. Σημειώστε ότι για όλους τους θετικούς ακέραιους το ιστόγραμμα θα είναι μια εντελώς διαφορετική, εκθετικά αυξανόμενη ακολουθία (δείτε [[#Αντίστροφη]]).]]
[[Αρχείο:Collatz-10Million.png|δεξιά|μικρογραφία|300x300εσ|Διάστημα επανάληψης για εισόδους από το 2 έως 10 εκατομμύρια]]

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

Mαθηματικά, η συνάρτηση ορίζεται ως εξής:
: <math> f(n) = \begin{cases} n/2, &\text{αν } n \bmod 2 = 0\\ 3n+1, & \text{αν } n \bmod 2 = 1 \end{cases}</math>

Ξεκινώντας από οποιονδήποτε θετικό ακέραιο ''n'', με επαναληπτική εφαρμογή αυτής της συνάρτησης, σχηματίζεται μια ακολουθία αριθμών χρησιμοποιώντας το αποτέλεσμα του κάθε βήματος ως είσοδο για το επόμενο βήμα:
: <math> a_i = \begin{cases}n & \text{για } i = 0 \\ f(a_{i-1}) & \text{για } i > 0 \end{cases}</math>

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

Το μικρότερο ''i'', τέτοιο ώστε ''α''<sub>''i''</sub> = 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.

:<big>'''27'''</big>, 82, <big>'''41'''</big>, 124, 62, <big>'''31'''</big>, 94, <big>'''47'''</big>, 142, <big>'''71'''</big>, 214, <big>'''107'''</big>, 322, <big>'''161'''</big>, 484, 242, <big>'''121'''</big>, 364, 182, <big>'''91'''</big>, 274, <big>'''137'''</big>, 412, 206, <big>'''103'''</big>, 310, <big>'''155'''</big>, 466, <big>'''233'''</big>, 700, 350, <big>'''175'''</big>, 526, <big>'''263'''</big>, 790, <big>'''395'''</big>, 1186, <big>'''593'''</big>, 1780, 890, <big>'''445'''</big>, 1336, 668, 334, <big>'''167'''</big>, 502, <big>'''251'''</big>, 754, <big>'''377'''</big>, 1132, 566, <big>'''283'''</big>, 850, <big>'''425'''</big>, 1276, 638, <big>'''319'''</big>, 958, <big>'''479'''</big>, 1438, <big>'''719'''</big>, 2158, <big>'''1079'''</big>, 3238, <big>'''1619'''</big>, 4858, <big>'''2429'''</big>, 7288, 3644, 1822, <big>'''911'''</big>, 2734, <big>'''1367'''</big>, 4102, <big>'''2051'''</big>, 6154, <big>'''3077'''</big>, <big><span style="color:#FF0000"> 9232</span></big>, 4616, 2308, 1154, <big>'''577'''</big>, 1732, 866, <big>'''433'''</big>, 1300, 650, <big>'''325'''</big>, 976, 488, 244, 122, <big>'''61'''</big>, 184, 92, 46, <big>'''23'''</big>, 70, <big>'''35'''</big>, 106, <big>'''53'''</big>, 160, 80, 40, 20, 10, <big>'''5'''</big>, 16, 8, 4, 2, <big>'''1'''</big> {{OEIS|id=A008884}}

[[Αρχείο:Collatz5.svg|500px|center|Απεικόνιση της ακολουθίας με ''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|A006877}}

Αριθμοί των οποίων το μέγιστο σημείο της τροχιάς τους είναι μεγαλύτερο από κάθε μικρότερη τιμή εκκίνησης πάνε ως εξής:
: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|id=A006884}}

Ο αριθμός των βημάτων που χρειάζεται το ''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|id=A006577}}

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

Οι δυνάμεις με βάση το δύο συγκλίνουν γρήγορα γιατί το 2<sup>''n''</sup> υποδιπλασιάζεται σε ''n'' φορές και φτάνει στο 1, χωρίς ποτέ να αυξάνεται. Οι [[Mersenne numbers|αριθμοί Μερσέν]] M<sub>''n''</sub> χρειάζεται να αυξηθούν ''n'' φορές και συνήθως χρειάζονται περισσότερα βήματα για να φτάσουν το 1.

==Απεικονίσεις==
<gallery widths="px" heights="px">
Collatz-graph-all-30-no27.svg|[[Κατευθυνόμενος γράφος]] που δείχνει τις τροχιές για μικρούς αριθμούς στον χάρτη της ακολουθίας. Η εικασία Κόλατζ ισοδυναμεί με την πρόταση ότι όλα τα μονοπάτια τελικά καταλήγουν στο 1.
Collatz Orbits of FIrst 1000 Integers.svg|Κατευθυνόμενος γράφος που δείχνει τις τροχιές των αριθμών μέχρι το 1000.
CollatzConjectureGraphMaxValues.jpg|Ο άξονας ''x'' των τετμημένων αντιστοιχεί στον αριθμό έναρξης και ο άξονας ''y'' των τεταγμένων δείχνει τον μεγαλύτερο αριθμό που φτάνει η ακολουθία.
</gallery>

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

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

Ένας ''k''-κύκλος είναι ένας κύκλος που μπορεί να χωριστεί σε 2''k'' συνεχόμενες υποακολουθίες: ''k'' αύξουσες ακολουθίες περιττών αριθμών εναλλασσόμενες με ''k'' φθίνουσες ακολουθίες άρτιων αριθμών. Για παράδειγμα, εάν ο κύκλος αποτελείται από μια μοναδική αύξουσα ακολουθία περιττών αριθμών ακολουθούμενη από μία φθίνουσα ακολουθία άρτιων αριθμών, ονομάζεται 1-κύκλος.<ref name="Simons & de Weger (2003)"/>

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

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

===Πειραματικές αποδείξεις===
Η εικασία έχει ελεγχθεί από τον υπολογιστή για όλες τις τιμές έως 2<sup>68</sup>.<ref name="Barina">{{cite web |last=Barina | first=David |title=Convergence verification of the Collatz problem |url=http://pcbarina.fit.vutbr.cz/ |accessdate=27 Jul 2020}}</ref> Όλες οι αρχικές τιμές που έχουν δοκιμαστεί μέχρι σήμερα καταλήγουν στην επανάληψη του κύκλου (4, 2, 1), που έχει μόνο τρεις όρους. Από αυτό το κάτω φράγμα για την τιμή εκκίνησης, έχει βρεθεί κατώτερο όριο για τον αριθμό των όρων επαναλαμβανόμενων κύκλων, εκτός του (4, 2, 1).<ref name="Garner">{{cite web | last=Garner | first = Lynn E. | title=On The Collatz 3n + 1 Algorithm | url = http://www.ams.org/journals/proc/1981-082-01/S0002-9939-1981-0603593-2/S0002-9939-1981-0603593-2.pdf| accessdate = 27 March 2015}}</ref> Όταν ανακαλύφθηκε αυτή η σχέση το 1981, ο τύπος έδωσε κάτω φράγμα με 35.400 όρους.<ref name="Garner"/>

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

===Ένα πιθανοτικό ευρεστικό επιχείρημα===
Αν κάποιος πάρει μόνο τους ''περιττούς'' αριθμούς με τη σειρά που παράγονται από την διαδικασία  του Κόλατζ, τότε κάθε περιττός αριθμός είναι, κατά μέσο όρο, μεγαλύτερος κατά τα 3/4 του προηγούμενου.{{Refn|Lagarias (1985) section "[http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node3.html A heuristic argument"].}} (Για την ακρίβεια, ο [[γεωμετρικός μέσος]] των λόγων των αποτελεσμάτων είναι 3/4.) Αυτό παράγει ένα ευρεστικό επιχείρημα ότι κάθε ακολουθία χαλαζιού θα πρέπει να φθίνει μακροπρόθεσμα, αν και αυτό δεν είναι απόδειξη για όλους τους κύκλους, παρά μόνον κατά της απόκλισης. Το επιχείρημα αυτό δεν είναι απόδειξη, επειδή υποθέτει ότι οι ακολουθίες χαλαζιού συναρμολογούνται από πιθανοτικά ασυσχέτιστα γεγονότα. (Ωστόσο, καθιερώνει αυστηρά ότι η [[p-adic numbers|2-αδική]] επέκταση της συνάρτησης Κόλατζ  έχει δύο βήματα διαίρεσης για κάθε βήμα πολλαπλασιασμού για σχεδόν όλες τις 2-αδικές τιμές εκκίνησης.)

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

===Αυστηρά όρια===
Αν και δεν γνωρίζουμε υπό την αυστηρή έννοια ότι όλοι οι θετικοί αριθμοί καταλήγουν στο 1 με την ακολουθία Κόλατζ, είναι γνωστό ότι πολλοί αριθμοί φτάνουν. Ειδικότερα, οι Krasikov και Lagarias έδειξαν ότι το πλήθος των ακεραίων στο διάστημα [1, ''x''] που τελικά φτάνουν στο ένα είναι τουλάχιστον ανάλογο με το ''x''<sup>0.84</sup>.<ref>{{Cite journal
 | last1 = Krasikov | first1 = Ilia
 | last2 = Lagarias | first2 = Jeffrey C. | authorlink2 = Jeffrey Lagarias
 | doi = 10.4064/aa109-3-4
 | issue = 3
 | journal = Acta Arithmetica
 | mr = 1980260
 | pages = 237–258
 | title = Bounds for the 3''x'' + 1 problem using difference inequalities
 | language = en
 | volume = 109
 | year = 2003
 | postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}.</ref>

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

===Αντίστροφη===
[[Αρχείο:Collatz-tree,_depth=20.svg|σύνδεσμος=https://el.wikipedia.org/wiki/%CE%91%CF%81%CF%87%CE%B5%CE%AF%CE%BF:Collatz-tree,_depth=20.svg|μικρογραφία|600x600εσ|Τα{{Dead link|date=Οκτώβριος 2019 }} πρώτα 21 επίπεδα του γράφου Κόλατζ όπως παράγεται από κάτω προς τα επάνω. Το γράφημα περιλαμβάνει όλους τους αριθμούς με μήκος τροχιάς 21 ή λιγότερο.]]
Υπάρχει και μια άλλη προσέγγιση για  να αποδειχθεί η εικασία, που χρησιμοποιεί την κάτω-προς-επάνω μέθοδο ανάπτυξης του λεγόμενου γράφου Κόλατζ. Ο ''γράφος Κόλατζ''  είναι ένας γράφος που ορίζεται από την αντίστροφη σχέση

<math> R(n) = \begin{cases} \{2n\} & \text{αν } n \bmod 6 = 0,1,2,3,5 \\ \{2n,(n-1)/3\} & \text{αν } n \bmod 6 = 4 \end{cases}</math>

Έτσι, αντί να αποδείξουμε ότι όλοι οι θετικοί ακέραιοι καταλήγουν τελικά στο 1, μπορούμε να προσπαθήσουμε να αποδείξουμε ότι το 1 οδηγεί σε όλους τους θετικούς ακεραίους. Για κάθε ακέραιο <math>n</math>, <math>n \bmod 2 = 1</math> αν και μόνον αν (ανν) <math>(3n + 1) \bmod 6 = 4</math>. Ισοδύναμα, <math>[(n-1)/3] \bmod 2 = 1</math> ανν <math>n \bmod 6 = 4</math>. Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα [[Δέντρο (Θεωρία Γράφων)|δέντρο]] αν εξαιρέσουμε τον βρόχο 1-2-4 (τον αντίστροφο του κύκλου (4, 2, 1) της αρχικής συνάρτησης ''f'' όπως ορίζεται στην ενότητα [[#Διατύπωση του προβλήματος|Διατύπωση του προβλήματος]] αυτού του άρθρου).

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

<math> R(n) = \begin{cases} \{2n\} & \text{αν } n \bmod 3 = 0, 1 \\ \{2n,(2n-1)/3\} & \text{αν } n \bmod 3 = 2 \end{cases} </math>

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

Εναλλακτικά, αντικαταστήστε το 3''n''+1 με το ''n' / H(n')'', όπου ''n''<nowiki/>' = 3''n''+1 και  ''H(n')''  είναι η μεγαλύτερη δύναμη του 2 που διαιρεί το ''n''' (χωρίς να αφήνει υπόλοιπο). Η προκύπτουσα συνάρτηση ''f'' είναι μια απεικόνιση από [[Άρτιοι και περιττοί αριθμοί|περιττούς αριθμούς]] σε περιττούς αριθμούς. Τώρα, ας υποθέσουμε ότι για κάποιον περιττό αριθμό ''n'', εφαρμογή αυτής της συνάρτησης ''k'' φορές καταλήγει στον αριθμό 1 (δηλαδή <math>f^k(n) = 1</math>). Τότε στο [[Δυαδικό σύστημα|δυαδικό]] σύστημα, ο αριθμός ''n'' μπορεί να γραφτεί ως συνένωση των συμβολοσειρών ''w<sub>k</sub> w<sub>k-1</sub> ... w<sub>1</sub>'', όπου κάθε ''w<sub>h</sub>'' είναι πεπερασμένo και συνεχόμενo τμήμα της αναπαράστασης του 1 / 3<sup>''h''</sup>.<ref name="Colussi2011">{{cite journal|last1=Colussi|first1=Livio|title=The convergence classes of Collatz function|language=en|journal=Theoretical Computer Science|date=2011-09-09|volume=412|issue=39|pages=5409–5419|doi=10.1016/j.tcs.2011.05.056}}</ref> Η αναπαράσταση του ''n'' ως εκ τούτου περιέχει το [[Περιοδικός αριθμός|επαναλαμβανόμενο τμήμα]] του 1 / 3<sup>''h''</sup>, όπου κάθε επαναλαμβανόμενο τμήμα μπορεί να περιστρέφεται και έπειτα να αναπαράγεται μέχρι έναν πεπερασμένο πλήθος δυαδικών ψηφίων. Αυτό συμβαίνει μόνο στη δυαδική αναπαράσταση.<ref name="Hew2016">{{Cite journal|title=Working in binary protects the repetends of 1/3h: Comment on Colussi's ‘The convergence classes of Collatz function’|language=en|date=2016-03-07|journal=Theoretical Computer Science|doi=10.1016/j.tcs.2015.12.033|volume=618|pages=135–141|last1=Hew|first1=Patrick Chisan}}</ref> Σύμφωνα με την εικασία, κάθε δυαδική συμβολοσειρά ''s'' που τελειώνει σε '1' μπορεί να επιτευχθεί με μια αναπαράσταση αυτής της μορφής (προθέτοντας μηδενικά '0' στο ''s'').

=== Αφηρημένη μηχανή που υπολογίζει με βάση το δύο ===
Επαναλαμβανόμενες εφαρμογές της συνάρτησης Κόλατζ μπορούν να αναπαρασταθούν ως μια αφηρημένη μηχανή που χειρίζεται [[Συμβολοσειρά|συμβολοσειρές]] από [[Bit|δυαδικά ψηφία]]. Η μηχανή θα εκτελεί τα ακόλουθα τρία βήματα σε κάθε περιττό αριθμό, μέχρι να απομείνει το '1':
# Προσάρτησε '1' στα δεξιά της δυαδικής αναπαράστασης του αριθμού (οδηγεί στον αριθμό 2''n+''1).
# Πρόσθεσε τον παραπάνω αριθμό στον αρχικό αριθμό με δυαδική πρόσθεση (οδηγεί στο (2''n''+1) + ''n'' = 3''n'' + 1).
# Αφαίρεσε όλα τα καταληκτικά '0' (δηλαδή επανειλημμένα διαιρεί δια δύο μέχρι το αποτέλεσμα να γίνει περιττό).

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

====Παράδειγμα====
Ξεκινάμε με το 7 που στο δυαδικό σύστημα γράφεται 111. Προκύπτει η εξής ακολουθία χαλαζιού:
<div style="font-family:'Courier New', 'Lucida Console', 'Courier', Monospace" class="">
          111
         <u>1111+</u>
        1011<s>0</s>
       <u>10111+</u>
      10001<s>0</s>
     <u>100011+</u>
     1101<s>00</s>
    <u>11011+</u>
   101<s>000</s>
  <u>1011+</u>
 1<s>0000</s>
</div>

===Ακολουθία ισοτιμίας===
Για αυτή την ενότητα, θεωρήστε τη συνάρτηση Κόλατζ στην ελαφρώς τροποποιημένη της μορφή
: <math> f(n) = \begin{cases} n/2 &\text{αν } n \bmod 2 = 0 \\ (3n+1)/2 & \text{αν } n \bmod 2 =  1 \end{cases}</math>
Αυτό μπορεί να γίνει, διότι όταν το ''n'' είναι περιττό, το 3''n''&#x20;+&#x20;1 είναι πάντα άρτιο.

Αν P(...) είναι η ισοτιμία του αριθμού, δηλαδή P(2''n'')&#x20;=&#x20;0 και P(2''n''&#x20;+&#x20;1) =&#x20;1, τότε μπορούμε να ορίσουμε την ακολουθία ισοτιμίας χαλαζιού (ή διάνυσμα ισοτιμίας) για έναν αριθμό ''n'' ως ''p<sub>i</sub>'' = P(''a<sub>i</sub>''), όπου ''a''<sub>0</sub> = ''n'', και ''ένα'' ''a''<sub>''i''+1</sub> = ''f''(''a''<sub>''i''</sub>).

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

Χρησιμοποιώντας αυτή τη μορφή για το ''f''(''n''), μπορεί να αποδειχθεί ότι οι ακολουθίες ισοτιμίας για δύο αριθμούς ''m'' και ''n'' θα συμφωνούν στους πρώτους ''k'' όρους, αν και μόνον αν ''m'' και ''n'' είναι ισοδύναμα κατά modulo 2<sup>''k''</sup>. Αυτό συνεπάγεται ότι κάθε αριθμός είναι προσδιορίζεται μονοσήμαντα από την  ακολουθία ισοτιμίας του και  επιπλέον, ότι αν υπάρχουν πολλαπλοί κύκλοι στην ακολουθία χαλαζιού, τότε οι αντίστοιχοι κύκλοι ισοτιμίας πρέπει να είναι διαφορετικοί.<ref name="Lagarias (1985)"/><ref>{{citation
 | last = Terras | first = Riho
 | issue = 3
 | journal = Polska Akademia Nauk
 | mr = 0568274
 | pages = 241–252
 | title = A stopping time problem on the positive integers
 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf
 | volume = 30
 | year = 1976}}</ref>

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

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

<math> f(n) = \begin{cases} n/2 &\text{αν } n \bmod 2 = 0 \\ (3n +1)/2 & \text{αν } n \bmod 2 = 1 \end{cases}</math>

οι ακολουθία χαλαζιού μπορεί να υπολογιστεί από το εξαιρετικά απλό [[Tag system#Example: Computation of Hailstone sequences|σύστημα 2-ετικετών]] με κανόνες παραγωγής ''a''→ ''bc'', ''b'' → ''a'', ''c'' → ''aaa''. Σε αυτό το σύστημα, ο θετικός ακέραιος ''n'' αντιπροσωπεύεται από μια σειρά από ''n a'' και η επανάληψη της λειτουργίας ετικέτας τερματίζεται σε οποιαδήποτε λέξη μήκους λιγότερου από 2 (προσαρμοσμένο από το De Mol.)

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

==Επεκτάσεις σε ευρύτερα πεδία==

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

Περιττές τιμές μαρκάρονται με έμφαση. Κάθε κύκλος παρουσιάζεται ξεκινώντας με το μέλος που έχει την μικρότερη απόλυτη τιμή (είναι πάντα περιττό).
{| class="wikitable" style="text-align: center; margin-bottom: 10px;"
! Cycle 
! Odd-value cycle length 
! Full cycle length
|-
| style="text-align: left;" | <big>'''1'''</big> → 4 → 2 → <big>'''1'''</big> '''…''' 
| 1 
| 3
|-
| style="text-align: left;" | <big>'''−1'''</big> → −2 → <big>'''−1'''</big> '''…''' 
| 1 
| 2
|-
| style="text-align: left;" | <big>'''−5'''</big> → −14 → <big>'''−7'''</big> → −20 → −10 → <big>'''−5'''</big> '''…''' 
| 2 
| 5
|-
| style="text-align: left;" | <big>'''−17'''</big> → −50 → <big>'''−25'''</big> → −74 → <big>'''−37'''</big> → −110 → <big>'''−55'''</big> → −164 → −82 → <big>'''−41'''</big> → −122 → <big>'''−61'''</big> → −182 → <big>'''−91'''</big> → −272 → −136 → −68 → −34 → <big>'''−17'''</big> '''…''' 
| 7 
| 18
|}

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

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

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

{{NumBlk|::|<math>\frac{3^{m-1} 2^{k_0} + \cdots + 3^0 2^{k_{m-1}}}{2^n - 3^m}.</math>|{{EquationRef|1}}}}

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

:<math>\frac{3^3 2^0 + 3^2 2^2 + 3^1 2^3 + 3^0 2^6}{2^7 - 3^4} = \frac{151}{47},</math>

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

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

:(0 1 1 0 0 1 1) → <math>\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{250}{47}</math>
:(1 1 0 0 1 1 0) → <math>\frac{3^3 2^0 + 3^2 2^1 + 3^1 2^4 + 3^0 2^5}{2^7 - 3^4} = \frac{{125}}{47}</math>
:(1 0 0 1 1 0 1) → <math>\frac{3^3 2^0 + 3^2 2^3 + 3^1 2^4 + 3^0 2^6}{2^7 - 3^4} = \frac{211}{47}</math>
:(0 0 1 1 0 1 1) → <math>\frac{3^3 2^2 + 3^2 2^3 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{340}{47}</math>
:(0 1 1 0 1 1 0) → <math>\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^4 + 3^0 2^5}{2^7 - 3^4} = \frac{170}{47}</math>
:(1 1 0 1 1 0 0) → <math>\frac{3^3 2^0 + 3^2 2^1 + 3^1 2^3 + 3^0 2^4}{2^7 - 3^4} = \frac{85}{47}</math>

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

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

====Κυκλικά όρια====
Η {{EquationNote|1|εξίσωση 1}} μας δίνει επίσης μια ιδέα για το πώς μπορεί κανείς να αποδείξει ότι δεν υπάρχουν κύκλοι με συγκεκριμένα μήκη. Για έναν υποθετικό κύκλο μήκους ''n'', ο αριθμητής φράσσεται άνω από το 3<sup>''n''</sup> - 2<sup>''n''</sup> (αυτό αντιστοιχεί σε ένα κύκλο με περιττούς αριθμούς μόνον). Ένα κάτω φράγμα για τον παρονομαστή μπορεί να ληφθεί θεωρώντας το ''n''/''m'' ως μια βέλτιστη κλασματική προσέγγιση του log(3)/log(2). Αυτά μαζί δίνουν ένα άνω φράγμα για το μοναδικό κλάσμα που παράγει ένα κύκλο μήκους ''n''. Αν αυτό το άνω φράγμα είναι μικρότερο από τον [[#Πειραματικές αποδείξεις|μεγαλύτερο αριθμό για τον οποίο η εικασία έχει επαληθευτεί ότι ισχύει]], τότε ένας κύκλος μήκους ''n'' είναι αδύνατος.

=== Επανάληψη σε πραγματικούς ή μιγαδικούς αριθμούς ===
[[Αρχείο:CobwebCollatz2.PNG|σύνδεσμος=https://el.wikipedia.org/wiki/%CE%91%CF%81%CF%87%CE%B5%CE%AF%CE%BF:CobwebCollatz2.PNG|μικρογραφία|300x300εσ|Γράφημα{{Dead link|date=Οκτώβριος 2019 }} ιστού αράχνης για την τροχιά 10-5-8-4-2-1-2-1-2-1-... στην πραγματική συνιστώσα της απεικόνισης Κόλατζ (βελτιστοποιημένη με την αντικατάσταση "3''n''+1" με "(3''n''+1)/2")]]

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

:: <math></math><math>f(z)=\frac 1 2 z \cos^2\left(\frac \pi 2 z\right)+(3z+1)\sin^2\left(\frac \pi 2 z\right)</math>

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

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

:: <math></math><math>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)</math>

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

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

Η επανάληψη κατά μήκος του άξονα των πραγματικών διερευνήθηκε από τον Chamberland<ref name="Chamberland (1996)"/> και στο επίπεδο των μιγαδικών από τους Letherman, Schleicher, and Wood.<ref name="Letherman, Schleicher, and Wood (1999)"/>
[[Αρχείο:CollatzFractal.png|σύνδεσμος=https://el.wikipedia.org/wiki/%CE%91%CF%81%CF%87%CE%B5%CE%AF%CE%BF:CollatzFractal.png|κέντρο|μικρογραφία|500x500εσ|Φράκταλ{{Dead link|date=Οκτώβριος 2019 }} της απεικόνισης Κόλατζ σε μια γειτονιά του πραγματικού άξονα]]

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

: ''f'' <sup>''k''</sup>(''a'' 2<sup>''k''</sup> + ''b'') = ''a'' 3<sup>''c''(b)</sup> + ''d''(b)

Οι πίνακες ''c'' και ''d'' είναι υπολογισμένοι εκ των προτέρων για όλους τους πιθανούς αριθμούς ''b'' μήκους ''k''-bit, όπου ''d''(b) είναι το αποτέλεσμα της εφαρμογής της συνάρτησης ''f'', ''k'' φορές στο ''b'' και ''c''(b) είναι ο αριθμός των περιττών αριθμών που συναντούν στη διαδρομή.<ref>{{citation|contribution=Looking for Class Records in the 3x+1 Problem by means of the COMETA Grid Infrastructure|url=http://www.dmi.unict.it/~scollo/seminars/gridpa2007/CR3x+1paper.pdf|first=Giuseppe|last=Scollo|year=2007|title=Grid Open Days at the University of Palermo}}</ref> Για παράδειγμα, αν ''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<sup>''k''</sup> προεπεξεργασίες και αποθηκεύσεις για να επιταχύνει τον υπολογισμό κατά ένα συντελεστή ''k'', αντισταθμίζοντας χρόνο με χώρο.

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

: ''f'' <sup>''k''</sup>(''a'' 2<sup>''k''</sup>+''b'') = ''a'' 3<sup>''c''(b)</sup> + ''d''(b) < ''a'' 2<sup>''k''</sup>+b

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

===Συνάρτηση Συρακουσών===
Αν ''k'' είναι ένας περιττός ακέραιος, τότε ο 3''k''+1 είναι άρτιος και έτσι 3''k''+1 = 2<sup>a</sup>''k' '' με ''k' '' περιττό και ''a''≥1. Η '''συνάρτηση Συρακουσών''' είναι η συνάρτηση ''f'' από το σύνολο ''I'' των περιττών ακεραίων προς τον εαυτό του, για την οποία ''f''(''k'')=''k' '' {{Oeis|id=A075677}}.

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

* <math>\forall k \in I, f(4k+1)=f(k)</math>. (Επειδή <math>3(4k+1)+1=12k+4=4(3k+1)</math> )
* Γενικότερα: Για όλα τα <math>p \geq 1</math> και περιττά <math>h</math>, <math>f^{p-1}(2^ph-1)=2 \cdot 3^{p-1}h-1</math> (Εδώ <math>f^{p-1}</math> συμβολίζει τη [[Σύνθεση συνάρτησης|επαναληπτική σύνθεση συνάρτησης]].)
* Για όλα τα περιττά <math>h</math>, <math>f(2h-1) \leq \frac{3h-1}{2}</math>

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

==Μη αποφασίσιμες γενικεύσεις==
Το 1972, ο [[Τζον Χόρτον Κόνγουεϊ]] (''John Horton Conway'') απέδειξε ότι μια φυσική γενίκευση του προβλήματος Κόλατζ είναι αλγοριθμικά [[undecidable problem|μη αποφασίσιμη]].<ref>{{Citation|last=Conway|first=John H.|title=Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder|year=1972|pages=49–52|contribution=Unpredictable Iterations}}</ref>

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

: <math>g(n) = a_i n + b_i,  n \bmod P = i</math>

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

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

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

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

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

Τροποποιώντας την προϋπόθεση με αυτό τον τρόπο μπορεί να κάνει το πρόβλημα πιο δύσκολο ή πιο εύκολο να λυθεί (διαισθητικά, είναι πιο δύσκολο να δικαιολογηθεί μια θετική απάντηση, αλλά μπορεί να είναι πιο εύκολο να δικαιολογηθεί η αρνητική). Οι Kurtz και Simon<ref name="KurtzSimon">{{Cite book|url=http://books.google.com/books?id=mhrOkx-xyJIC&pg=PA542|title=Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007|language=en|year=2007|isbn=3-540-72503-2|pages=542–553|author1=Kurtz, Stuart A.|author2=Simon, Janos|editor1=Cai, J.-Y.|editor2=Cooper, S.B.|editor3=Zhu, H.|contribution=The Undecidability of the Generalized Collatz Problem|doi=10.1007/978-3-540-72504-6_49}}</ref> απέδειξαν ότι το παραπάνω πρόβλημα είναι στην πραγματικότητα μη αποφασίσιμο και ακόμα υψηλότερα στην αριθμητική ιεραρχία, και πιο συγκεκριμένα είναι <math>\Pi^0_2</math>-πλήρες. Αυτό το επίπεδο δυσκολίας ισχύει ακόμη και αν κάποιος περιορίσει την κλάση των συναρτήσεων ''g'' σταθεροποιώντας το modulo συντελεστή ''P'' στο 6480.<ref>{{Citation|last=Ben-Amram|first=Amir M.|title=Mortality of iterated piecewise affine functions over the integers: Decidability and complexity|year=2015|journal=Computability|volume=1|issue=1|pages=19–56|doi=10.3233/COM-150032}}</ref>

==Η Απόλυτη Πρόκληση: Το  πρόβλημα 3''x''+1==
Αυτός ο τόμος,<ref name="Lagarias (2010)"/> επιμελημένος από τον [[Jeffrey Lagarias]] και δημοσιευμένος από την [[American Mathematical Society|Αμερικανική Μαθηματική Εταιρεία]], είναι μια συλλογή πληροφοριών σχετικά με την εικασία Κόλατζ, τις μεθόδους προσέγγισης και τις γενικεύσεις της. Περιλαμβάνει δύο επισκοπήσεις από τον επιμελητή και πέντε από άλλους συγγραφείς, σχετικά με την ιστορία του προβλήματος, τις γενικεύσεις, στατιστικές προσεγγίσεις και αποτελέσματα από την [[θεωρία υπολογισμού]]. Περιλαμβάνει, επίσης, ανατυπώσεις των πρώτων δημοσιεύσεων σχετικά με το θέμα (συμπεριλαμβανομένης μιας καταχώρισης από τον Λόθαρ Κόλατζ).

==Δείτε επίσης==
* [[Ημιομάδα 3''x''+1]]
* [[Αριθμητική υπολοίπων]]

==Παραπομπές==
{{Reflist|30em|refs=

===Δημοσιεύσεις===
<ref name="Lagarias (1985)">Jeffrey C. Lagarias (1985). The 3x + 1 problem and its generalizations. ''[[The American Mathematical Monthly]]'' 92(1): 3-23.</ref>
<!--<ref name="Lagarias (2001)">{{SpringerEOM | urlname=S/s110330 | title=Syracuse problem | author=Jeffrey C. Lagarias}}.</ref>-->
<ref name="Chamberland (1996)">Marc Chamberland. A continuous extension of the 3''x''+1 problem to the real line. Dynam. Contin. Discrete Impuls Systems 2: 4 (1996), 495–509.</ref>
<!--<ref name="Garner (1981)">{{cite journal |last=Garner |first=Lynn E. |year=1981 |title=On the Collatz 3''n''&nbsp;+&nbsp;1 Algorithm |journal=Proceedings of the American Mathematical Society |volume=82 |issue=1 |pages=19–22 |doi=10.2307/2044308 |jstor=2044308|accessdate= |quote= }}</ref>-->
<ref name="Letherman, Schleicher, and Wood (1999)">Simon Letherman, Dierk Schleicher, and Reg Wood: The (3''n''+1)-Problem and Holomorphic Dynamics. Experimental Mathematics 8: 3 (1999), 241–252.</ref>
<!--<ref name="Eliahou (1993)">Eliahou, Shalom, ''The 3x+1 problem: new lower bounds on nontrivial cycle lengths'', Discrete Mathematics 118 (1993) p.&nbsp;45-56; [http://images.math.cnrs.fr/Le-probleme-3n-1-y-a-t-il-des.html ''Le problème 3n+1 : y a-t-il des cycles non triviaux ?''], ''[[Images des mathématiques]]'' (2011) {{Link language|fr}}.</ref>
<ref name="Andrei (1998)">{{cite journal |author1=Andrei, Stefan |author2=Masalagiu, Cristian |doi=10.1007/s002360050117 |title=About the Collatz conjecture |url=https://archive.org/details/sim_acta-informatica_1998-02_35_2/page/167 |year=1998 |journal=Acta Informatica |volume=35 |issue=2 |page=167}}</ref>
<ref name="Van Bendegem (2005)">Van Bendegem, Jean Paul, [https://compmath.files.wordpress.com/2008/08/jpvb_collatz.pdf "The Collatz Conjecture: A Case Study in Mathematical Problem Solving"], ''Logic and Logical Philosophy'', volume 14 (2005), 7–23.</ref>
<ref name="Belaga (2006)">Belaga, Edward G., Mignotte, Maurice, [http://www-irma.u-strasbg.fr/~belaga/a8*BelagaMathInfo06Presentation060920.ppt "Walking Cautiously into the Collatz Wilderness: Algorithmically, Number Theoretically, Randomly"], Fourth Colloquium on Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, September 18–22, 2006, Institut Élie Cartan, Nancy, France.</ref>
<ref name="Belaga (1998a)">Belaga, Edward G., Mignotte, Maurice, [http://www.emis.de/journals/EM/expmath/volumes/7/7.html "Embedding the 3x+1 Conjecture in a 3x+d Context"], ''Experimental Mathematics'', volume 7, issue 2, 1998.</ref>-->
<ref name="Steiner (1977)">Steiner, R. P.; "A theorem on the syracuse problem", ''Proceedings of the 7th Manitoba Conference on Numerical Mathematics'', pages 553–559, 1977.</ref>
<ref name="Simons & de Weger (2003)">Simons, J.; de Weger, B.; [http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf "Theoretical and computational bounds for ''m''-cycles of the 3''n''+1 problem"] {{Webarchive|url=https://web.archive.org/web/20170517124216/http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n%201-ActaArith%5B2005%5D.pdf |date=2017-05-17 }}, ''Acta Arithmetica'' (on-line version 1.0, November 18, 2003), 2005.</ref>
<!--<ref name="Sinyor (2010)">Sinyor, J.; [http://downloads.hindawi.com/journals/ijmms/2010/458563.pdf "The 3x+1 Problem as a String Rewriting System"], ''International Journal of Mathematics and Mathematical Sciences'', volume 2010 (2010), Article ID 458563, 6 pages.</ref>-->

===Preprints===
<!--<ref name="Belaga (1998b)">{{cite paper | author1-link = Edward Belaga | author1-last = Belaga | author1-first = Edward G. | id = {{citeseerx|10.1.1.54.483}} | title = Reflecting on the 3x+1 Mystery | publisher = [[University of Strasbourg]] | date = 1998 }}</ref>
<ref name="Bruschi (2008)">{{cite arXiv |author=Bruschi, Mario |eprint=0810.5169 |title=A generalization of the Collatz problem and conjecture |class=math.NT |year=2008}}</ref>
<ref name="De Mol (2008)">{{cite journal | last = De Mol | first = Liesbeth | title = Tag systems and Collatz-like functions | journal = Theoretical Computer Science | volume = 390 | issue = 1 | pages =92–101 | date = January 2008 | url = http://logica.ugent.be/liesbeth/TagColOK.pdf | doi=10.1016/j.tcs.2007.10.020}}</ref>
<ref name="Lagarias (2006)">{{cite arXiv |author=Jeffrey C. Lagarias |eprint=math.NT/0608208 |title=The 3''x''+1 problem: An annotated bibliography, II (2000–) |class=math.NT |year=2006}}</ref>
<ref name="Ohira">{{cite paper | last1 = Ohira | first1 = Reiko | last2 = Yamashita | first2 = Michinori | url = http://risweb2.ris.ac.jp/faculty/earth_env/yamasita/open/p-col.pdf | title = A generalization of the Collatz problem | language = ja }}</ref>
<ref name="Sinisalo (2003)">{{cite paper | first = Matti K. | last = Sinisalo | archivedate = 2009-10-24 | archiveurl = http://web.archive.org/web/20091024183537/http://geocities.com/mattiksinisalo/collatz.doc | url = http://geocities.com/mattiksinisalo/collatz.doc | title = On the minimal cycle lengths of the Collatz sequences | date = June 2003 | publisher = University of Oulu }}</ref>
<ref name="Stadfeld">{{cite paper | first = Paul | last = Stadfeld | url = http://home.versatel.nl/galien8/blueprint/blueprint.html | title = Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture }}</ref>
<ref name="Urata">{{cite paper | last = Urata | first = Toshio | archivedate = 2008-04-06 | archiveurl = http://web.archive.org/web/20080406061036/http://auemath.aichi-edu.ac.jp/~turata/Fall.files/CTZVI.pdf | url = http://auemath.aichi-edu.ac.jp/~turata/Fall.files/CTZVI.pdf | title = Some Holomorphic Functions connected with the Collatz Problem }}</ref>-->

===Βιβλία===
<!--<ref name="Everest (2003)">{{cite book | last1=Everest | first1=Graham | last2=van der Poorten | first2=Alf | author2-link=Alfred van der Poorten | last3=Shparlinski | first3=Igor | last4=Ward | first4=Thomas | title=Recurrence sequences | series=Mathematical Surveys and Monographs | volume=104 | location=[[Providence, RI|Providence]], Rhode Island, USA | publisher=[[American Mathematical Society]] | year=2003 | isbn=0-8218-3387-1 | zbl=1033.11006 | at=Chapter 3.4 }}</ref>-->
<ref name="Guy (2004)">{{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory |url=https://archive.org/details/unsolvedproblems0003guyr|language=en|publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at="E17: Permutation Sequences" }} Cf [http://books.google.com/books?id=1AP2CEGxTkgC&pg=PA337&lpg=PA337&dq=%22Unpredictable+Iterations%22+conway&source=bl&ots=Tilvg0yIqF&sig=5Nz7invP8gpLKpkgd0Q7aX2njUU&hl=en&ei=WVITSp-fHdmLtgfJmKCTBA&sa=X&oi=book_result&ct=result&resnum=9#PPA336,M1 pp. 336–337].</ref>
<ref name="Lagarias (2010)">{{cite book | title=The Ultimate Challenge: the 3x+1 problem | url=https://archive.org/details/isbn_9780821849408 |language=en| editor1-first=Jeffrey C. | editor1-last=Lagarias | editor1-link=Jeffrey Lagarias | publisher=[[American Mathematical Society]] | year=2010 | isbn=978-0-8218-4940-8 | zbl=1253.11003 }}</ref>
<!--<ref name="Wirsching (1998)">{{cite book | first=Günther J. | last=Wirsching | title=The Dynamical System Generated by the 3''n''+1 Function | volume=1681 | series=Lecture Notes in Mathematics | publisher=[[Springer-Verlag]] | year=1998 | isbn=978-3-540-63970-1 | doi=10.1007/BFb0095985 | zbl=0892.11002 }}</ref>-->
}}

==Εξωτερικοί σύνδεσμοι==
* [http://www.numbertheory.org/3x+1/ Η σελίδα 3''x''+1 του Keith Matthews: Επισκόπηση προόδου μαζί με διάφορα προγράμματα].
* [http://boinc.thesonntags.com/collatz/ Ένα έργο] [[Παράλληλα και κατανεμημένα συστήματα|κατανεμημένου υπολογισμου]] [[BOINC]]) που επιβεβαιώνει την εικασία Κόλατζ για μεγάλες τιμές.
* Ένα σε εξελίξη [http://www.ericr.nl/wondrous/index.html έργο] [[Παράλληλα και κατανεμημένα συστήματα|κατανεμημένου υπολογισμου]] του Eric Roosendaal επιβεβαιώνει την εικασία Κόλατζ για όλο και μεγαλύτερες τιμές.
* Άλλο ένα σε εξέλιξη [http://sweet.ua.pt/tos/3x+1.html έργο] [[Παράλληλα και κατανεμημένα συστήματα|κατανεμημένου υπολογισμου]] του Tomás Oliveira e Silva που συνεχίζει να επιβεβιώνει την εικασία Κόλατζ (με λιγότερες στατιστικές από τη σελίδα του Eric Roosendaal's, αλλά με μεγαλύτερη πρόοδο).
* [http://gfredericks.com/sandbox/arith/collatz Μία διαδραστική εφαρμογή] που χρησιμοποιεί υψηλής ακρίβειας αριθμιτική.
* {{MathWorld | urlname=CollatzProblem | title=Collatz Problem}}
* {{Planetmath reference | urlname=CollatzProblem | title=Collatz Problem}}.
* {{YouTube|id=BhR-iIjhTNM|title=Collatz Iterations on the Ulam Spiral grid}}.
* [http://demonstrations.wolfram.com/CollatzPaths/ Μονοπάτια Κόλατζ] από τον Jesse Nochella, διαδραστική εφαρμογή στο [[Wolfram]].
* [http://go.helms-net.de/math/collatz/aboutloop/collloopintro_main.htm Collatz cycles?] Περί κύκλων, πολύ βασικό, περιέχει μερικούς ασυνήθιστους κύκλους (HTML).
* [http://go.helms-net.de/math/collatz/Collatz061102.pdf Collatz cycles?] Περί βρόχων, συμπυκνωμένο κείμενο, μάλλον βασικό (PDF).
* [https://web.archive.org/web/20160828224126/http://pageperso.univ-brest.fr/~huisman/etc/syracuse.html Μία διαδραστική εφαρμογή] της ακολουθίας Κόλατζ για τον αριθμό 2{{sup|2{{sup|6}}}} + 1 σε βάση 2.

{{Portal bar|Μαθηματικά}}

[[Κατηγορία:Εικασίες]]
[[Κατηγορία:Αριθμητική]]
[[Κατηγορία:Ακολουθίες ακεραίων]]
[[Κατηγορία:Θεωρία αριθμών]]