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

Επιχειρήματα υποστήριξης

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

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

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

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

Μια πιθανολογική ευρετική

Αν κάποιος πάρει μόνο τους περιττούς αριθμούς με τη σειρά που διμηουργούνται από την διαδικασία  του Collatz,τότε  κάθε περιττός αριθμός είναι κατά μέσο όρο μεγαλύτερος κατα 3/4 του προηγούμενου. (για την ακρίβεια, η γεωμετρική ερμηνεία  των λόγων  των αποτελεσμάτων είναι 3/4.) Αυτό παράγει ένα ευρετικό επιχείρημα ότι κάθε ακολουθία Hailstone θα πρέπει να μειωθεί μακροπρόθεσμα, αν και αυτό δεν είναι απόδειξη ενάντια σε άλλους κύκλους, μόνο κατά απόκλισης. Το επιχείρημα αυτό δεν είναι μια απόδειξη, επειδή υποθέτει ότι η  ακολουθία του Hailstone συναρμολογείταιι από ασυσχέτιστα πιθανολογικά γεγονότα. (Είναι αυστηρά καθιερωμένο  ότι η δυαδική διαδικασία επέκτασης του Collatz  έχει δύο τμηματικά  βήματα για κάθε βήμα πολλαπλασιασμού  για σχεδόν όλες τις τιμες που είναι δυνάμεις του 2.)

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

Αυστηρά όρια

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

Αλλα σκευάσματα για την εικασία 

Σε αντίστροφη

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

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

$R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\\{2n,(n-1)/3\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.$

Έτσι, αντί να αποδεικνύουν ότι όλοι οι θετικοί ακέραιοι οδηγούνται τελικά σε 1, μπορούμε να προσπαθήσουμε να αποδείξουμε ότι 1 οδηγείται σε όλους τους θετικούς ακεραίους. Για κάθε ακέραιο n, n ≡ 1 (mod 2) αν 3n + 1 ≡ 4 (mod 6). Aντίστοιχα, (n − 1)/3 ≡ 1 (mod 2) αν n ≡ 4 (mod 6). Εικάζοντας, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο εκτός από τον βρόγχο 1-2-4  (το αντίστροφο του 4-2-1 βρόγχο του αναλλοίωτη συνάρτηση f ορίζεται στην Δήλωση του προβλήματος αυτού του άρθρου).

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

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

Για κάθε ακέραιο n, n ≡ 1 (mod 2) iff (3n + 1)/2 ≡ 2 (mod 3). Aντίστοιχα, (2n − 1)/3 ≡ 1 (mod 2) αν n ≡ 2 (mod 3). Εικάζοντας, αυτή η αντίστροφη σχέση αποτελεί ένα δέντρο, εκτός από 1-2 βρόγχους (το αντίστροφο της 1-2 βρόγχους της συνάρτησης f(n) αναθεωρημένη όπως αναφέρεται παραπάνω).

Εναλλακτικά, αντικαταστήστε το 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 ως εκ τούτου κατέχει το repetends του 1 / 3^h, όπου κάθε repetend είναι προαιρετικά, να περιστρέφεται και, στη συνέχεια, να αντικατασταθεί πάνω σε ένα πεπερασμένο αριθμό από bits. Μόνο σε δυαδική ότι αυτό συμβαίνει. Conjecturally, κάθε δυαδική συμβολοσειρά s που τελειώνει με το " 1 "μπορεί να επιτευχθεί με μια αναπαράσταση της μορφής (που μπορεί να προσθέσετε ή να διαγράψετε κορυφαίος" 0 σε s).

Ως μια αφηρημένη μηχανή που υπολογίζει με βάση δύο

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

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

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

Παράδειγμα

Το νούμερο 7 είναι γραμμένο στη βάση δύο ως 111. Η προκύπτουσα ακολουθία Hailstone είναι:

111
 1111
 10110
 10111
 100010
 100011
 110100
 11011
 101000
 1011
10000

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

Για αυτό το τμήμα, σκεφτείται ότι η συνάρτηση του Collatz λειτουργία σε ελαφρώς τροποποιημένη μορφή

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

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

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

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

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

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

Ως σύστημα ετικεττών

Για την συνάρτηση του Collatz στον τύπο

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

 ΟΙ ακολουθίες Hailstone  μπορούν να υπολογιστούν από την εξαιρετικά απλή διαδυκή επέκταση με κανόνες παραγωγής a → bc, b → a, γ → aaa. Σε αυτό το σύστημα, ο θετικός ακέραιος n αντιπροσωπεύεται από μια σειρά από n a, και την επανάληψη της  λειτουργία σταματά σε οποιαδήποτε λέξη με μήκος λιγότερο από 2. (Προσαρμοσμένο από το De Mol.)

Η εικασία του Collatz εχει ισοδύναμα μέλη ώστε  αυτό το  σύστημα, με μια αυθαίρετη πεπερασμένη σειρά as, όπως η αρχική λέξη, τελικά σταματά (βλέπε Ετικέττα του συστήματος#Παράδειγμα: Υπολογισμός του Collatz ακολουθίες για παράδειγμα).

Επεκτάσεις μεγαλύτερο τομείς

Επανάληψη σε όλους  τους ακέραιους

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

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

Κύκλος	Περίεργη τιμή το μήκος του κύκλου	Πλήρες μήκος του κύκλου
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

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

Επανάληψη με περίεργο παρονομαστές ή 2-adic αριθμούς

Για παράδειγμα, η ισοτιμία του κύκλου (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-ψήφια ισοτιμία της ακολουθίας.

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