Η εικασία Collatz (2)

Στο πρώτο μέρος της σειράς είδαμε τη διατύπωση μίας αρκετά ενδιαφέρουσας εικασίας:

Ξεκινάμε με έναν θετικό ακέραιο αριθμό και, αν είναι άρτιος, τον διαιρούμε με το 2 ενώ αν είναι περιττός τον πολλαπλασιάζουμε με το 3 και προσθέτουμε 1 Αν επαναλαμβάνουμε τα παραπάνω με κάθε αριθμό που βρίσκουμε, μετά από πεπερασμένα στο πλήθος βήματα θα πάρουμε αποτέλεσμα 1.

Η παραπάνω εικασία είναι γνωστή και ως εικασία του Collatz. Είδαμε ότι ξεκινώντας από οποιονδήποτε από τους αριθμούς 1,2,…,10 πράγματι καταλήγουμε στον αριθμό 1 – δείτε εδώ για περισσότερα. Ωστόσο, το ότι το δείξαμε για δέκα θετικούς ακεραίους δε σημαίνει επ’ουδενί ότι ισχύει η παραπάνω εικασία για κάθε θετικό ακέραιο αριθμό. Είναι όμως χρήσιμο να αποκτήσουμε μία διαίσθηση για το πώς μοιάζουν οι ακολουθίες που προκύπτουν από την παραπάνω διαδικασία, καθώς μπορούμε να αποκομίσουμε δύο οφέλη (δυνητικά):

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

Τώρα, το να φτιάξουμε έναν πίνακα όπως αυτό που είδαμε εδώ αλλά όχι μόνο με 10 αλλά, ας πούμε, με 1000 γραμμές, σίγουρα δεν είναι κάτι που θα ήταν διασκεδαστικό να το κάνουμε με το χέρι. Γι’ αυτό, όμως, έχουμε τον υπολογιστή μας. Η παρακάτω συνάρτηση – σε python – δέχεται έναν θετικό ακέραιο n και παράγει την αντίστοιχη ακολουθία Collatz με αρχικό όρο n:

def collatz(n):
    sequence = [n]
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3*n + 1
        sequence.append(n)
    return sequence

Απλή αποτύπωση του ορισμού της ακολουθίας Collatz σε python είναι το παραπάνω, δε χρειάζεται και ιδιαίτερη εξήγηση είναι η αλήθεια. Με τη βοήθεια της παραπάνω συνάρτησης μπορούμε να εξετάσουμε τώρα ποιες είναι οι 1000 πρώτες ακολουθίες Collatz, χρησιμοποιώντας το εξής script:

def collatz(n):
    sequence = [n]
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3*n + 1
        sequence.append(n)
    return sequence
    
if __name__ == '__main__':
    n = 1000
    sequences = ''
    for i in range(1,n+1):
        sequence = collatz(i)
        for entry in sequence:
            sequences += str(entry) + ' '
        sequences += '\n'
    with open('sequenes.txt','w') as file:
        file.write(sequences)

Το παραπάνω δεν κάνει τίποτα άλλο από το να υπολογίζει τις πρώτες 1000 ακολουθίες Collatz και να τις αποθηκεύει σε ένα αρχείο sequence.txt που θα δημιουργηθεί στον ίδιο φάκελο με το αρχείο που έχουμε τον παραπάνω κώδικα. Το αρχείο που θα παραχθεί θα έχει αυτή τη μορφή – μπορείτε να το βρείτε κι εδώ:

Οι πρώτες 53ακολουθίες Collatz μέσα στο αρχείο.

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

Χρήσιμη παρατήρηση είναι αυτή, καθώς φαίνεται να εισάγει κάποιου είδους κανονικότητα στο παραπάνω πρόβλημα. Αν το καλοσκεφτούμε, δε, είναι απολύτως λογικό, καθώς επιθυμούμε ο τελευταίος όρος της ακολουθίας μας να είναι 1, οπότε ο προτελευταίος όρος της θα είναι μεγαλύτερος του 1. Αφού σε κάθε βήμα είτε διαιρούμε με το 2 είτε πολλαπλασιάζουμε με το 3 και προσθέτουμε 1, ο μόνος τρόπος για να είναι ο επόμενος όρος μας μικρότερος από τον τρέχοντα είναι να διαιρέσουμε με το 2. Συνεπώς, ο προτελευταίος όρος θα είναι πάντοτε 2. Με ανάλογο σκεπτικό, και ο προ-προτελευταίος μας όρος θα πρέπει αναγκαστικά να είναι 4.

Ωστόσο, για να φτάσουμε στο 4 έχουμε δύο (φαινομενικά) επιλογές. Η μία είναι να φτάσουμε έχοντας διαιρέσει το 8 με το 2 και η άλλη να φτάσουμε έχοντας πολλαπλασιάσει το 1 με 3 και προσθέτοντας 1. Όμως, σαφώς δεν μπορούμε να περάσουμε από το 1 πάνω από μία φορά, άρα ο προ-προ-προτελευταίος όρος είναι το 8. Συνεπώς, κάθε ακολουθία Collatz πρέπει να καταλήγει με τους όρους 8, 4, 2, 1, γεγονός που μπορείς να επαληθεύσει ότι ισχύει με όλες τις ακολουθίες στο παραπάνω αρχείο που έχουν τουλάχιστον τέσσερις όρους.

Το παραπάνω σκεπτικό μπορεί να μας πάει και λίγο παρακάτω. Στο 8 είτε καταλήγουμε από το 16, διαιρώντας με το 2, είτε από το 7/3. πολλαπλασιάζοντας επί 3 και προσθέτοντας 1. Επειδή, όμως, το 7/3 δεν είναι ακέραιος, αυτό το σενάριο απορρίπτεται, επομένως όσες ακολουθίες Collatz έχουν τουλάχιστον 5 στοιχεία, θα πρέπει να καταλήγουν σε 16, 8, 4, 2, 1 – όπως μπορείτε να παρατηρήσετε, αυτό ισχύει και παραπάνω. Από το 16 και πιο πριν, όμως, είναι πιο δύσκολο να κάνουμε καλές μαντεψιές. Αφενός, υπάρχει το «ευχάριστο» σενάριο, όπου καταλήγουμε στο 16 από έναν υποδιπλασιασμό του 32. Αφετέρου, αν πολλαπλασιάσουμε το 5 με το 3 και προσθέσουμε 1 παίρνουμε 16 κι εδώ είναι που το πράγμα γίνεται πιο περίπλοκο. Ωστόσο, το παραπάνω μας δίνει μία καλή ιδέα για να μελετήσουμε το πρόβλημά μας. Αντί να ξεκινάμε από κάθε αριθμό και να εξετάζουμε αν μπορούμε να φτάσουμε στο 1 – πράγμα που είναι μία λογική προσέγγιση, αν και χρονοβόρα – μπορούμε να ξεκινήσουμε από το 1 και εφαρμόζοντας τις «αντίστροφες» πράξεις να εξετάσουμε αν μπορούμε να φτάσουμε σε κάθε αριθμό. Έτσι, έχουμε την εξής ισοδύναμη διατύπωση της εικασίας του Collatz:

Θεωρώντας τις συναρτήσεις d(x)=2x  και t(x)=\dfrac{x-1}{3}  με την πρώτη ορισμένη για κάθε x\in\mathbb{N}  και τη δεύτερη για x=4,7,10,\ldots  είναι αλήθεια ότι κάθε θετικός ακέραιος αριθμός n  γράφεται στη μορφή f(1)  όπου f  είναι μία συνάρτηση που προκύπτει από πεπερασμένες στο πλήθος συνθέσεις των d,t;

Για παράδειγμα, παρατηρούμε τα εξής:

  • 1=d^{(0)}(1) – θεωρούμε ότι σύνθεση μίας συνάρτησης μηδέν φορές δίνει την ταυτοτική απεικόνιση.
  • 2=d(1).
  • 3=tdtdddd(1) – παραλείπουμε τις παρενθέσεις, για σαφήνεια, οπότε dd(1)=d(d(1)) κ.ο.κ.
  • 4=dd(1)
  • 5=tdddd(1)
  • 6=dtdtdddd(1)
  • 7=tdtdtddtdddtdddd(1)

Παρατηρήστε ότι στα παραπάνω δε μας πολυαπασχολεί η σειρά με την οποία εφαρμόζουμε τις d και t, αρκεί να μπορούμε να εφαρμόσουμε την t που δεν ορίζεται σε όλους τους θετικούς ακεραίους.

Με την παραπάνω διαδικασία έχουμε και μία νέα προσέγγιση που μπορούμε να ακολουθήσουμε για να μελετήσουμε την εικασία του Collatz. Αντί να ξεκινάμε από κάθε θετικό ακέραιο και, εφαρμόζοντας πιστά τις οδηγίες του Collatz, να προχωράμε μέχρι να συναντήσουμε τη μονάδα, μπορούμε ξεκινώντας από το 1 και εφαρμόζοντας με όποια σειρά θέλουμε και επιτρέπεται τις d και t να αναρωτηθούμε: Θα καταλήξουμε σε όποιον αριθμό θέλουμε;

Περισσότερα για τα παραπάνω στο επόμενο μέρος.

Καλημέρα!

Η κεντρική εικόνα είναι το πορτραίτο του Ambroise Vollard του Pierre-Auguste Renoir.

Σαφώς, αν μετά από 84 χρόνια η μαθηματική κοινότητα δεν έχει αποφανθεί για το τι συμβαίνει, δεν προσδοκά το aftermaths να δώσει τη λύση. Ωστόσο, οι τομείς των μαθηματικών που δείχνουν με μία πρώτη ματιά σχετικοί με την παραπάνω εικασία είναι ιδιαίτερα ενδιαφέροντες και η παραπάνω εικασία είναι μία καλή και απλή αφορμή για να ασχοληθούμε μαζί τους. Σε αυτή τη σειρά, λοιπόν, με αφορμή την εικασία του Collatz, θα εξερευνάμε σε σχεδόν καθημερινό επίπεδο μικρά ψήγματα μαθηματικών και απλές – ή και όχι τόσο απλές – σκέψεις και ιδέες πάνω σε ένα ανοικτό πρόβλημα.

Διαβάστε επίσης: Μία γνωστή σχέση…

Ακολουθήστε το aftermathsgr στα social media:

One comment

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Google

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s