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

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

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

 Ο [Paul Erdős Paul Erdos] δήλωσε σχετικά με την υπόθεση Collatz:" Τα Μαθηματικά μπορεί να μην είναι έτοιμα για τέτοια προβλήματα . "Επίσης ,πρόσφερε $ 500 για την λύση του.

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

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

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

Διάστημα επανάληψης για ις εισροές από 2 έως 10.000.000

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

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

Στην modular arithmetic σημειογραφία, ορίζετε η συνάρτηση f ως εξής:

$f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}}\\3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}$

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

Στο συμβολισμό:

$a_{i}={\begin{cases}n&{\text{for }}i=0\\f(a_{i-1})&{\text{for }}i>0\end{cases}}$

(Δηλαδή: $a_{i}$ είναι η τιμή $f$εφαρμόζεται $n$ αναδρομικά $i$ φορές; $a_{i}=f^{i}(n)$).

Η εικασία Collatz είναι: Αυτή η διαδικασία θα φτάσει τελικά το νούμερο 1,ανεξάρτητα από το ποίος θετικός ακέραιος έχει επιλεγεί αρχικά.

Αυτό το μικρότερο  i τέτοιο ώστε a_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, 991, 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)

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

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, 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 , με 1132 βήματα.

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

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

• 
• 
• 

Κύκλοι

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

Ο τύπος ενός κύκλου μπορεί να καθοριστεί με αναφορά στην "συντόμευση" ορισμός του χάρτη του Collatz, $f(n)=(3n+1)/2$ για περιττά n και$f(n)=n/2$ για άρτια n. Ένας κύκλος είναι μια ακολουθία sequence $(a_{0};a_{1};\ldots a_{q})$ όπου$f(a_{0})=a_{1}$, $f(a_{1})=a_{2}$,και ούτε καθεξής, μέχρι$f(a_{q})=a_{0}$ σε κλειστό βρόχο. Για τον ορισμό της συντόμευσης αυτής ,ο μόνος γνωστής κύκλος είναι (1; 2). Αν και τα 4 είναι μέρος του ενιαίου γνωστού κύκλου για τον αρχικό κύκλο Collatz, δεν είναι μέρος του κύκλου για τον χάρτη 

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

 Ο Steiner (1977) απέδειξε ότι δεν υπάρχει 1-κύκλος εκτός από το ασήμαντο (1?2). Ο Simons το (2004) χρησιμοποίησε την μέθοδο του Stainer για να αποδείξει ότι δεν υπάρχει 2-κύκλος. Ο Simon & de Weger το (2003) επέκτεινε μέχρι 68 κύκλους: δεν υπάρχει k-κύκλος με k=68. Πέραν 68, η μέθοδος αυτή δίνει άνω φράγματα για τα στοιχεία σε ένα τέτοιο κύκλο: για παράδειγμα αν υπάρχει ένας 75-κύκλος, τότε τουλάχιστον ένα στοιχείο του κύκλου είναι μικρότερο από 2.385 *2 ^50. Ως εκ τούτου , σε μια συνεχή εξαντλητική έρευνα από τον υπολογιστή μπορούν οι μεγαλύτεροι κύκλοι να αποκλειστούν.Να δηλώσω το επιχείρημα περισσότερο διαισθητικά: δεν χρειάζεται να κοιτάξουμε για τους κύκλους που έχουν περισσότερες από 68 τροχιές, όπου κάθε τροχία αποτελείται από συνεχόμενα ups πουν ακολουθούνται από διαδοχικές υποτιμήσεις . Δείτε παρακάτω για μια ιδέα για το πως θα μπορούσε κανείς να βρει ένα άνω φράγμα για τα στοιχεία του κύκλου.

.