Μετάβαση στο περιεχόμενο

Ακολουθία Κολακόσκι

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Απεικόνιση του 3ου έως 50ου όρου της ακολουθίας Κολακόσκι ως σπείρα. Οι όροι ξεκινούν από την κουκκίδα στη μέση της σπείρας. Στην επόμενη περιστροφή, κάθε τόξο επαναλαμβάνεται αν ο όρος είναι 1, ή χωρίζεται σε δύο ίσα μισά αν είναι 2. Οι δύο πρώτοι όροι δεν μπορούν να απεικονιστούν καθώς είναι αυτοαναφορικοί. Στο the SVG image, περάστε με το ποντίκι πάνω από ένα τόξο ή μια ετικέτα για να το επισημάνετε και να εμφανίσετε τα στατιστικά του στοιχεία.

Στα μαθηματικά, η ακολουθία Κολακόσκι, η οποία μερικές φορές αναφέρεται και ως ακολουθία Όλντενμπουργκερ-Κολακόσκι,[1] είναι μια άπειρη ακολουθία συμβόλων {1,2} που είναι η σειρά των διαδρόμων στην κωδικοποίηση του δικού της διαδρόμου[2]. Πήρε το όνομά της από τον ψυχαγωγικό μαθηματικό Ουίλιαμ Κολακόσκι (1944-97), ο οποίος την περιέγραψε το 1965[3], αλλά είχε ήδη συζητηθεί από τον Ρούφους Όλντενμπουργκερ το 1939[1][4].

Ορισμός

[Επεξεργασία | επεξεργασία κώδικα]
Η ακολουθία Κολακόσκι περιγράφει το δικό της μήκος διαδρομής

Οι αρχικοί όροι της ακολουθίας Κολακόσκι είναι οι εξής:

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,... (ακολουθία A000002 στην OEIS)

Κάθε σύμβολο εμφανίζεται σε μια "διαδρομή" (μια ακολουθία ίσων στοιχείων) είτε ενός είτε δύο διαδοχικών όρων και η καταγραφή των μηκών αυτών των διαδρομών δίνει ακριβώς την ίδια ακολουθία:

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...
1, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1, 2 ,...

Η περιγραφή της ακολουθίας Κολακόσκι είναι επομένως αναστρέψιμη. Αν Κ συμβολίζει την "ακολουθία Κολακόσκι", η περιγραφή #1 προϋποθέτει λογικά την περιγραφή #2 (και αντίστροφα):

1. Οι όροι του K παράγονται από τις διαδρομές (δηλαδή τα μήκη διαδρομής) του K
2. Οι διαδρομές του K παράγονται από τους όρους του K.

Κατά συνέπεια, μπορούμε να πούμε ότι κάθε όρος της ακολουθίας Κολακόσκι δημιουργεί μια σειρά ενός ή δύο μελλοντικών όρων. Το πρώτο 1 της ακολουθίας παράγει μια σειρά του "1", δηλαδή τον εαυτό του- το πρώτο 2 παράγει μια σειρά του "22", η οποία περιλαμβάνει τον εαυτό του- το δεύτερο 2 παράγει μια σειρά του "11"- και ούτω καθεξής. Κάθε αριθμός στην ακολουθία είναι το μήκος της επόμενης σειράς που θα παραχθεί, και το στοιχείο που θα παραχθεί εναλλάσσεται μεταξύ 1 και 2:

1,2 (μήκος της ακολουθίας l = 2; άθροισμα των όρων s = 3)
1,2,2 (l = 3, s = 5)
1,2,2,1,1 (l = 5, s = 7)
1,2,2,1,1,2,1 (l = 7, s = 10)
1,2,2,1,1,2,1,2,2,1 (l = 10, s = 15)
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 (l = 15, s = 23)

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

Ένα κινουμένο gif που απεικονίζει πώς οι μεταγενέστεροι όροι της ακολουθίας Κολακόσκι παράγονται από τους προηγούμενους όρους.
Ένα κινουμένο gif που απεικονίζει πώς οι μεταγενέστεροι όροι της ακολουθίας Κολακόσκι παράγονται από τους προηγούμενους όρους.

Αυτές οι αυτοδημιουργούμενες ιδιότητες, οι οποίες παραμένουν αν η ακολουθία γραφτεί χωρίς το αρχικό 1, σημαίνουν ότι η ακολουθία Κολακόσκι μπορεί να περιγραφεί ως φράκταλ, ή μαθηματικό αντικείμενο που κωδικοποιεί τη δική του αναπαράσταση σε άλλες κλίμακες[1].Ο Μπερτράν Στάινσκι δημιούργησε έναν αναδρομικό τύπο για τον i-th όρο της ακολουθίας[5], αλλά η ακολουθία εικάζεται ότι είναι απεριοδική,[6] πράγμα που σημαίνει ότι οι όροι της δεν έχουν ένα γενικό επαναλαμβανόμενο μοτίβο (βλ. άρρητοι αριθμοί όπως π και √2).

Έρευνα

[Επεξεργασία | επεξεργασία κώδικα]

Πυκνότητα

[Επεξεργασία | επεξεργασία κώδικα]

Φαίνεται εύλογο ότι η πυκνότητα των 1s στην {1,2}-ακολουθία του Κολακόσκι είναι 1/2, αλλά αυτή η εικασία παραμένει αναπόδεικτη [6]. Ο Βακλάβ Τσβάταλ απέδειξε ότι η ανώτερη πυκνότητα των 1s είναι μικρότερη από 0,50084[7]. Ο Νίλσον χρησιμοποίησε την ίδια μέθοδο με πολύ μεγαλύτερη υπολογιστική ισχύ για να επιτύχει το όριο 0,500080.[8]

Αν και οι υπολογισμοί των πρώτων 3×108 τιμών της ακολουθίας φάνηκε να δείχνουν ότι η πυκνότητά της συγκλίνει σε μια τιμή ελαφρώς διαφορετική από το 1/2,[5] μεταγενέστεροι υπολογισμοί που επέκτειναν την ακολουθία στις πρώτες 1013 τιμές της δείχνουν ότι η απόκλιση από την πυκνότητα του 1/2 γίνεται όλο και μικρότερη, όπως θα περίμενε κανείς αν η οριακή πυκνότητα είναι πράγματι 1/2[9].

Σύνδεση με συστήματα επισήμανσης

[Επεξεργασία | επεξεργασία κώδικα]

Η ακολουθία Κολακόσκι μπορεί επίσης να περιγραφεί ως το αποτέλεσμα ενός απλού κυκλικού συστήματος ετικετών. Ωστόσο, καθώς αυτό το σύστημα είναι ένα σύστημα 2 ετικετών και όχι ένα σύστημα 1 ετικέτας (δηλαδή αντικαθιστά ζεύγη συμβόλων με άλλες ακολουθίες συμβόλων, αντί να λειτουργεί σε ένα μόνο σύμβολο κάθε φορά), βρίσκεται στην περιοχή των παραμέτρων για τις οποίες τα συστήματα ετικετών είναι πλήρη κατά Τούρινγκ, γεγονός που καθιστά δύσκολη τη χρήση αυτής της αναπαράστασης για τη συλλογιστική της ακολουθίας[10].

Αλγόριθμοι

[Επεξεργασία | επεξεργασία κώδικα]

Η ακολουθία Κολακόσκι μπορεί να παραχθεί από έναν αλγόριθμο που, στην i-th επανάληψη, διαβάζει την τιμή xi που έχει ήδη εκδοθεί ως την i-th τιμή της ακολουθίας (ή, αν δεν έχει εκδοθεί ακόμη τέτοια τιμή, θέτει xi = i). Στη συνέχεια, αν το i είναι περιττό, εξάγει xi αντίγραφα του αριθμού 1, ενώ αν το i είναι άρτιο, εξάγει xi αντίγραφα του αριθμού 2. Έτσι, τα πρώτα βήματα του αλγορίθμου είναι τα εξής:

  1. Η πρώτη τιμή δεν έχει ακόμη εκδοθεί, οπότε ορίστε x1 = 1 και δώστε 1 αντίγραφο του αριθμού 1.
  2. Η δεύτερη τιμή δεν έχει ακόμη εξαχθεί, οπότε θέστε x2 = 2 και εξάγετε 2 αντίγραφα του αριθμού 2.
  3. Η τρίτη τιμή x3 εξήχθη ως 2 στο δεύτερο βήμα, οπότε εξάγετε 2 αντίγραφα του αριθμού 1.
  4. Η τέταρτη τιμή x4 εξήχθη ως 1 στο τρίτο βήμα, οπότε εξάγετε 1 αντίγραφο του αριθμού 2. κ.λπ.

Ο αλγόριθμος αυτός απαιτεί γραμμικό χρόνο, αλλά επειδή πρέπει να ανατρέξει σε προηγούμενες θέσεις της ακολουθίας, πρέπει να αποθηκεύσει ολόκληρη την ακολουθία, καταλαμβάνοντας γραμμικό χώρο. Ένας εναλλακτικός αλγόριθμος που δημιουργεί πολλαπλά αντίγραφα της ακολουθίας με διαφορετικές ταχύτητες, με κάθε αντίγραφο της ακολουθίας να χρησιμοποιεί την έξοδο του προηγούμενου αντιγράφου για να καθορίσει τι θα κάνει σε κάθε βήμα, μπορεί να χρησιμοποιηθεί για να δημιουργήσει την ακολουθία σε γραμμικό χρόνο και μόνο λογαριθμικό χώρο[9].

Δημοσιεύσεις

[Επεξεργασία | επεξεργασία κώδικα]
  • Allouche, Jean-Paul· Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, GeneralizationsΔωρεάν πρόσβαση υπoκείμενη σε περιορισμένη δοκιμή, συνήθως απαιτείται συνδρομή. Cambridge University Press. σελ. 337. ISBN 978-0-521-82332-6. Zbl 1086.11015. 
  • Dekking, F. M. (1997). «What Is the Long Range Order in the Kolakoski Sequence?». Στο: Moody, R. V., επιμ. Dordrecht, Netherlands: Kluwer, pp. 115–125. 
  • Fedou, J. M.; Fici, G. (2010). «Some remarks on differentiable sequences and recursivity». Journal of Integer Sequences 13 (3): Article 10.3.2. http://hal.archives-ouvertes.fr/docs/00/46/35/72/PDF/Some_remarks_on_differentiable_sequences_and_recursivity.pdf. 
  • Keane, M. S. (1991). «Ergodic Theory and Subshifts of Finite Type». Στο: Bedford, T.; Keane, M., επιμ. Oxford, England: Oxford University Press, pp. 35–70. 
  • Lagarias, J. C. (1992). «Number Theory and Dynamical Systems». Στο: Burr, S. A., επιμ. Providence, RI: American Mathematical Society, pp. 35–72. ISBN 9780821855010. https://books.google.com/books?id=j-pLi01XbFUC&pg=PA35. 
  • Păun, Gheorghe; Salomaa, Arto (1996). «Self-Reading Sequences». American Mathematical Monthly 103 (2): 166–168. doi:10.2307/2975113.
    Zbl 0854.68082
    .     
  • Shallit, Jeffrey (1999). «Number theory and formal languages». Στο: Hejhal, Dennis A.· Friedman, Joel· Gutzwiller, Martin C.· Odlyzko, Andrew M., επιμ. Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15--26, 1996. The IMA volumes in mathematics and its applications. 109. Springer-Verlag. σελίδες 547–570. ISBN 0-387-98824-6. Zbl 0919.00047. 

Δείτε επίσης

[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές

[Επεξεργασία | επεξεργασία κώδικα]
  1. ↑ 1,0 1,1 1,2 2= Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's
  2. ↑ Pytheas Fogg, N. (2002). Berthé, Valérie· Ferenczi, Sébastien· Mauduit, Christian· Siegel, A., επιμ. Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. σελ. 93. ISBN 3-540-44141-7. Zbl 1014.11015. 
  3. ↑ Kolakoski, William (1965). «Problem 5304». American Mathematical Monthly 72: 674. doi:10.2307/2313883.  For a partial solution, see Üçoluk, Necdet (1966). «Self Generating Runs». American Mathematical Monthly 73: 681–682. doi:10.2307/2314839. 
  4. ↑ Oldenburger, Rufus (1939). «Exponent trajectories in symbolic dynamics». Transactions of the American Mathematical Society 46 (3): 453–466. doi:10.2307/1989933.
    MR 0000352
    .     
  5. ↑ 5,0 5,1 Steinsky, Bertran (2006). «A recursive formula for the Kolakoski sequence A000002». Journal of Integer Sequences 9 (3): Article 06.3.7. Bibcode: 2006JIntS...9...37S.
    MR 2240857
    .
    Zbl 1104.11012
    . http://www.emis.de/journals/JIS/VOL9/Steinsky/steinsky5.pdf.     
  6. ↑ 6,0 6,1 Kimberling, Clark. «Integer Sequences and Arrays». University of Evansville. Ανακτήθηκε στις 13 Οκτωβρίου 2016. 
  7. ↑ Chvátal, Vašek (Δεκεμβρίου 1993). Notes on the Kolakoski Sequence. Technical Report 93-84. DIMACS. 
  8. ↑ Nilsson, J. «Letter Frequencies in the Kolakoski Sequence» (PDF). Acta Physics Polonica A. Ανακτήθηκε στις 24 Απριλίου 2014. 
  9. ↑ 9,0 9,1 Nilsson, Johan (2012). «A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence». Journal of Integer Sequences 15 (6): Article 12.6.7, 13.
    MR 2954662
    . http://www.emis.de/journals/JIS/VOL15/Nilsson/nilsson5.pdf.     
  10. ↑ van der Poorten, A. J. (1981). «Substitution automata, functional equations and "functions algebraic over a finite field"». Papers in algebra, analysis and statistics (Hobart, 1981). Contemporary Mathematics. 9. Providence, Rhode Island: American Mathematical Society. σελίδες 307–312. MR 0655988.  See in particular p. 308.


Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Ακολουθία_Κολακόσκι&oldid=10230875"