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

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

Πρώτοι και καλύτεροι

Όπως ξέρουμε από το σχολείο, κάθε θετικός ακέραιος μπορεί να γραφτεί κατά μοναδικό τρόπο σαν γινόμενο διακεκριμένων πρώτων αριθμών – όπου πρώτοι λέγονται οι αριθμοί που δεν έχουν μη τετριμμένους διαιρέτες. Μάλιστα, αν αγνοήσουμε τις όποιες αλλαγές στη σειρά με την οποία γράφουμε τους πρώτους στο γινόμενο, αυτό το γινόμενο είναι μοναδικό. Εμείς, για δική μας ευκολία, θα υποθέτουμε – εκτός αν το αναφέρουμε ρητά – ότι οι πρώτοι που εμφανίζονται στο ανάπτυγμα ενός ακεραίου είναι όλοι διαφορετικοί μεταξύ τους, γραμμένοι σε αύξουσα σειρά και οι όποιοι εκθέτες εμφανίζονται είναι θετικοί (σε αυτό το τελευταίο θα διατηρήσουμε μία ελαστικότητα, ωστόσο). Έτσι, για παράδειγμα, αν γράψουμε:

n=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}

θα ισχύουν τα εξής:

  • p_k πρώτοι,
  • a_k>0 και ακέραιοι,
  • p_1<p_2<\dots<p_n,

για κάθε k=1,2,\ldots,n.

Τώρα, πώς μπορεί το παραπάνω ανάπτυγμα να μας βοηθήσει στη μελέτη της εικασίας Collatz;

Λοιπόν, ας ασχοληθούμε αρχικά με τη συνήθη διατύπωση της εικασίας Collatz. Με βάση αυτή, ξεκινάμε με έναν θετικό ακέραιο αριθμό και αν αυτός είναι άρτιος τον υποδιπλασιάζουμε, ενώ αν είναι περιττός τον πολλαπλασιάζουμε επί 3 και προσθέτουμε 1. Στόχος μας είναι να φτάσουμε στη μονάδα – και η εικασία είναι ότι για κάθε αριθμό τελικά αυτό συμβαίνει. Επομένως, ας πάρουμε έναν θετικό ακέραιο αριθμό n ο οποίος γράφεται σαν γινόμενο πρώτων ως εξής:

n=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}.

Το να εφαρμόσουμε τα βήματα του αλγορίθμου που μας παρουσιάζει ο Collatz συνίσταται στο να κάνουμε το εξής:

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

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

[Σκέψεις, σκέψεις, σκέψεις]

Ουσιαστικά, το παραπάνω ερώτημα συνίσταται στο να απαντήσουμε το εξής:

Τι σχέση έχουν τα αναπτύγματα σε γινόμενο πρώτων δύο διαδοχικών ακεραίων αριθμών;

Ας πάρουμε, για αρχή, κάποια παραδείγματα:

  • 4=2^2, 5 πρώτος.
  • 12=2^33, 13 πρώτος.
  • 26=2\cdot13, 27=3^3.

Δε φαίνεται κάποιο ιδιαίτερο μοτίβο παραπάνω – και, πράγματι, δεν αναμέναμε να υπάρχει. Αν το καλοσκεφτούμε, το μόνο που ξέρουμε σίγουρα για τα αναπτύγματα δύο διαδοχικών ακεραίων, έστω n,n+1 είναι ότι δεν έχουν κανέναν κοινό παράγοντα. Πράγματι, αν ένας πρώτος p διαιρεί τόσο τον n όσο και τον n+1 τότε θα πρέπει να διαιρεί και τη διαφορά τους, άρα θα πρέπει ο p να διαιρεί το 1, άτοπο, καθώς είναι πρώτος. Επομένως, σίγουρα, προσθέτοντας μία μονάδα εξαφανίζουμε όλους τους πρώτους που βρίσκονται στο ανάπτυγμά μας.

Επιπρόσθετα, για τη δική μας περίπτωση, όπου έχουμε τελικά στα χέρια μας έναν περιττό αριθμό, έστω x, γνωρίζουμε και ότι ο 3x+1 είναι άρτιος – καθώς είναι κατά ένα μεγαλύτερος από τον 3x που είναι περιττός ως γινόμενο περιττών. Επομένως, έχουμε τουλάχιστον ένα δυάρι στο ανάπτυγμά μας και άρα θα κάνουμε τουλάχιστον έναν υποδιπλασιασμό ακόμα. Κι εδώ έρχεται ένα ακόμα ερώτημα να προστεθεί στη λίστα των αναπάντητων ερωτημάτων της σειράς:

Πόσους υποδιπλασιασμούς μπορούμε να κάνουμε μετά από κάθε «τριπλασιασμό» (+1);

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

Γι’ αυτόν τον σκοπό γράψαμε το ακόλουθο script σε python:

import json

from matplotlib import pyplot as plt

def count_powers_of_2(n):
    powers = []
    for i in range(1, 2 * n + 1, 2):
        j = 3 * i + 1
        counter = 0
        while j % 2 == 0:
            j /= 2
            counter += 1
        powers.append(counter)
    return powers

def plot_frequencies(powers):
    x = [2 * i + 1 for i in range(len(powers))]
    plt.plot(x, powers, 'r-')
    plt.xlabel('n')
    plt.ylabel('# of 2s in 3n + 1')
    plt.savefig('powers_' + str(len(powers)) + '.png')

if __name__ == '__main__':
    n = 20
    powers = count_powers_of_2(n)
    with open('powers_' + str(n) + '.txt', 'w') as file:
        json.dump(powers, file)
    plot_frequencies(powers)

Στο παραπάνω δεν κάνουμε τίποτα το τρομερό πέρα από το το να παίρνουμε του n πρώτους περιττούς αριθμούς, να τους πολλαπλασιάζουμε επί 3 και να προσθέτουμε 1 και στη συνέχεια να εξετάζουμε πόσες φορές το αποτέλεσμα διαιρείται με το 2 – τουλάχιστον 1, όπως είδαμε και παραπάνω. Έτσι, κατασκευάζουμε μία λίστα την οποία μετά την απεικονίζουμε σε ένα διάγραμμα, όπως το παρακάτω – n=20:

Πόσες φορές διαιρείται ο 3n+1 με το 2;

Ή παρατηρούμε κάτι ενδιαφέρον. Φαίνεται ότι εναλλάξ πάμε από κάποιον μεγάλο αριθμό – όπου μεγάλος σημαίνει μεγαλύτερος του 1 εδώ – πίσω στο 1. Δηλαδή, ο αριθμός 3n+1 για n=3, 7, 11,\ldots φαίνεται να περιέχει ακριβώς μία δύναμη του 2. Αυτό που μόλις διατυπώσαμε δεν είναι παρά μία μικρή εικασία που ίσως μας φανεί χρήσιμο να εξετάσουμε αν μπορούμε να την αποδείξουμε. Λίγο πιο αυστηρά, αυτό που λέμε είναι ότι οι αριθμοί της μορφής 3(4k-1)+1, για k=1,2,\ldots διαιρούνται ακριβώς μία φορά με το 2. Λίγο αναλυτικότερα, αν κάνουμε αρχικά πράξεις, έχουμε:

3(4k-1)+1=12k-3+1=12k-2=2(6k-1),\ k=1,2,\ldots,

είναι πολλαπλάσια του 2 (προφανές) αλλά όχι και του 4. Ισοδύναμα, ότι οι αριθμοί:

6k-1,\ k=1,2,\ldots,

δεν είναι πολλαπλάσια του 2, πράγμα επίσης προφανές, αφού ο 6k είναι πάντοτε άρτιος. Επομένως, πράγματι, αναμένουμε συνεχώς να έχουμε αυτά τα σκαμπανεβάσματα σε κάθε γράφημα που θα σχεδιάσουμε. Τώρα, πριν προχωρήσουμε παρακάτω, ας δούμε τι μας λέει αυτή η μικρή μας διαπίστωση για τους αριθμούς 4k-1. Πρακτικά, κάθε φορά που φτάνουμε σε έναν τέτοιο περιττό αριθμό, αφού κάνουμε τον «τριπλασιασμό», θα μπορούμε αμέσως μετά να κάνουμε μόνο έναν υποδιπλασιασμό και, ως εκ τούτου, θα καταλήξουμε να έχουμε έναν αριθμό που είναι μεγαλύτερος από τον 4k-1. Αυτό τώρα είναι ιδιαίτερα σημαντικό, καθώς ένας τρόπος για να αντιμετωπίσουμε την εικασία Collatz είναι ο εξής:

  • Υποθέτουμε ότι έχουμε αποδείξει ότι η εικασία αληθεύει για κάποιους αριθμούς, 1,2,\ldots,n,
  • Αν θέλουμε να εξετάσουμε την ισχύ της εικασίας για τον n+1 τότε αρκεί να εξετάσουμε αν στην ακολουθία Collatz που παράγει ο n+1 εμφανίζεται σε κάποια φάση κάποιος αριθμός m<n. Αν ναι, τότε σταματάμε, καθώς από εκεί και μετά γνωρίζουμε ότι θα καταλήξουμε στη μονάδα.

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

Γενικά, για να αναιρέσουμε έναν «τριπλασιασμό» θα χρειαστούμε δύο διπλασιασμούς, καθώς, αν n είναι ένας θετικός ακέραιος τότε:

\displaystyle\frac{3n+1}{4}\leq n,

με την ισότητα να ισχύει μάλιστα μόνο για n=1. Επομένως, οι αριθμοί σε μία ακολουθία Collatz που κάνουν«ζημιά» είναι ακριβώς εκείνοι οι οποίοι δεν επιτρέπουν να έχουμε παραπάνω από έναν – το ελάχιστο δυνατό – υποδιπλασιασμό μετά από τον «τριπλασιασμό» τους. Έτσι, θα θέλαμε να γνωρίζαμε περισσότερα γι’ αυτούς τους αριθμούς – ξέρουμε ήδη ποιοι είναι, καθώς είναι εύκολο να δούμε ότι δεν υπάρχουν άλλοι πέρα από τους 4k-1. Για παράδειγμα, εντάξει, το να συναντήσουμε έναν «κακό» αριθμό δεν είναι ίσως τόσο κακό αν μετά ακολουθεί ένας αριθμός ο οποίος δεν είναι δα και τόσο κακός. Επομένως, έχει νόημα να εξετάσουμε τις ακολουθίες τέτοιων αριθμών μέσα σε ακολουθίες Collatz. Υπάρχει το ενδεχόμενο να συναντήσουμε μία άπειρη τέτοια «κακή» ακολουθία; Αν όχι, πόσο μεγάλες μπορεί να είναι τέτοιες ακολουθίες «κακών» αριθμών;

Αυτά και άλλα πολλά την επόμενη φορά! Μέχρι τότε, καλή συνέχεια!

Η κεντρική εικόνα είναι ο πίνακας Τσάι της Mary Cassatt.

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

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

One comment

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Google

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

Σύνδεση με %s