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

1. Ξεκινάμε από έναν κόμβο με ετικέτα 1 τον οποίο και προσθέτουμε σε μία λίστα που θα ονομάζουμε λίστα των τρεχόντων κόμβων. Επίσης, δημιουργούμε και μία λίστα ακμών καθώς και μία ακόμα λίστα ετικετών – αρχικά κενές αμφότερες.
2. Επαναλαμβάνουμε τα ακόλουθα επ’ άπειρον για κάθε κόμβο n που βρίσκεται στη λίστα των τρεχόντων κόμβων και έχει ετικέτα που δεν βρίσκεται στη λίστα ετικετών:
   1. Προσθέτουμε έναν κόμβο n_a με ετικέτα διπλάσια από αυτήν που έχει ο τρέχων κόμβος και τον προσθέτουμε στους τρέχοντες κόμβους. Προσθέτουμε στη λίστα ακμών την ακμή (n,n_a).
   2. Αν η ετικέτα του κόμβου που βρισκόμαστε είναι ένας αριθμός του συνόλου τότε δημιουργούμε έναν ακόμα κόμβο n_b με ετικέτα ίση με το ένα τρίτο της ετικέτας του τρέχοντος κόμβου μειωμένη κατά 1 και τον προσθέτουμε στη λίστα των τρεχόντων κόμβων. Προσθέτουμε επίσης στη λίστα ακμών την ακμή (n,n_b).
   3. Αφαιρούμε από τη λίστα των τρεχόντων κόμβων τον κόμβο n και προσθέτουμε το n στη λίστα ετικετών.

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

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

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

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

Λοιπόν, αλγόριθμο έχουμε, όρεξη έχουμε, μένει μόνο να βρούμε μία γλώσσα για να τον υλοποιήσουμε. Η αλήθεια είναι ότι αυτό ίσως μας παιδέψει λίγο. Από τη μία, όσα έχει χρειαστεί να υλοποιήσουμε ως τώρα στη σειρά αλλά και γενικά στο aftermaths έχουν γραφτεί σε python – κυρίως γιατί είναι απλή. Από την άλλη, η python δεν είναι και η πρώτη σκέψη κάθε – υγιώς σκεπτόμενου – ατόμου όταν πρόκειται για ζωγραφική. Από τη μία, μπορούμε να γράψουμε έναν σχετικό κώδικα στο tikz στον οποίο θα πειράζουμε μία παράμετρο και θα σχεδιάζει αυτοματοποιημένα όλο το γράφημα που θέλουμε, αλλά, όπως έχουμε πει, το tikz δεν είναι και η καλύτερη επιλογή όταν έχουμε να κάνουμε πολλές πράξεις – κυρίως λόγω ακρίβειας, αλλά και υπολογιστικού κόστους. Μία άλλη επιλογή είναι το να υλοποιήσουμε όλα τα παραπάνω σε ένα web περιβάλλον – html, css, javascript. Βασικά, αυτή ίσως είναι και η πιο απλή γιατί είναι και η πιο αναμενόμενη – όλα τα παραπάνω υπάρχουν για να εξυπηρετούν ακριβώς αυτόν τον σκοπό.

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

• το σύνολο των κορυφών του – τα κυκλάκια – και,
• το σύνολο των ακμών του – τα βελάκια.

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

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

τότε η ακμή από τον κόμβο 16 στον 5 – θα τη λέμε απλώς ακμή 16-5 – έχει το μήκος που βλέπετε. Ωστόσο, αν επιλέξουμε να σχεδιάσουμε ένα γράφημα με περισσότερους κόμβους, όπως το παρακάτω:

τότε θα χρειαστεί να σχεδιάσουμε μία μακρύτερη ακμή 16-5 καθώς μετά τον κόμβο 16 εμφανίζονται κι άλλες διακλαδώσεις οι οποίες κάνουν το γράφημά μας πιο ψηλό από εκείνο το σημείο και μετά. Σε αυτό το σημείο, λοιπόν, θα κάνουμε μία σύμβαση που θα μας διευκολύνει κάπως: θα διακρίνουμε δύο είδη ακμών:

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

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

Λέγοντας «στρώσεις» εννοούμε στην ουσία τις στήλες κόμβων που σχηματίζονται στα παραπάνω δύο γραφήματα και θα τις «φωνάζουμε» με τις αντίστοιχες δυνάμεις του 2. Έτσι, έχουμε την στρώση του 1 και του 2 που περιέχουν μόνο αυτούς τους δύο κόμβους, αντίστοιχα, αλλά, στο τελευταίο γράφημα, έχουμε και τη στρώση του 128 που περιέχει το 21 και το 3 επίσης. Με τη βοήθεια των παραπάνω στρώσεων είναι σχετικά εύκολο να μετράμε τακτικά το μήκος των «λοξών» ακμών καθώς κάθε δύο στρώσεις – δηλαδή κάθε δύο δυνάμεις του 2 – δεν έχουμε παρά να υποδιπλασιάζουμε το αρχικό μήκος που έχουμε καθορίσει – το πώς έχει περισσότερο να κάνει με τον προγραμματισμό και τα svg παρά με αυτά που λέμε τώρα. Τώρα, αντί να σκεφτόμαστε ότι κάθε δύο βήματα υποδιπλασιάζουμε το μήκος του βέλους, μπορούμε να σκεφτόμαστε ότι σε κάθε στρώση διαιρούμε το μήκος που είχε το βέλος στην προηγούμενη στρώση με Έτσι, κάθε δύο στρώσεις πετυχαίνουμε τον πολυπόθητο υποδιπλασιασμό.

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

Το λύσαμε το πρόβλημα! Μπράβο μας, ας πάμε τώρα σπίτια μας. Ή και όχι. Ας βάλουμε έναν ακόμα κόμβο στο παραπάνω γράφημα:

Εδώ, αν και το 64 και το 10 βρίσκονται στην ίδια στρώση, τα βελάκια που ξεκινούν από αυτά δεν έχουν καθόλου ίδιο μήκος – είναι σαφές ότι το 64-21 είναι κατά πολύ μεγαλύτερο. Γιατί όμως χρειάζεται αυτό;

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

Εδώ η ακμή 64-21 είναι κατά πολύ μεγαλύτερη της 10-3 ακριβώς γιατί έχουμε αυτήν την εκνευριστική ακολουθία διαδοχικών διακλαδώσεων: 85-28-9. Βλέπετε, υποθέτοντας ότι κάθε δύο στρώσεις έχουμε και υποδιπλασιασμό του μήκους των ακμών, θέσαμε ένα άνω φράγμα για το μήκος των ακμών διακλάδωσης που, σε περιπτώσεις διαδοχικών διακλαδώσεων παραβιάζεται. Έτσι, θα πρέπει κάθε φορά που καλούμαστε να σχεδιάσουμε μία ακμή διακλάδωσης να κοιτάμε στο «μέλλον» και να βλέπουμε πόσο χαμηλά φτάνει το υπολειπόμενο κομμάτι του γραφήματος και να κάνουμε τους ανάλογους υπολογισμούς. Εναλλακτικά, θα μπορούσαμε να ξεκινάμε τη σχεδίαση του γραφήματος από τα δεξιά, κάτι που θα έλυνε εύκολα αυτό το πρόβλημα, αλλά θα δημιουργούσε άλλα – τα οποία, με τη σειρά του, θα λύνονταν με καταλληλότερη επιλογή δομής δεδομένων για το γράφημά μας, αλλά δεν είναι της παρούσης αυτά.

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

Καλό ξημέρωμα και καλή διασκέδαση!

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

Η κεντρική εικόνα είναι ο πίνακας Η Λεωφόρος Μονμάρτης στο Παρίσι του Camille Pissarro.