(r1) KolakoskiFrequencies < CoWiki

CoWiki Web>ImportantOpenProblems>KolakoskiFrequencies (revision 1) (raw view)~~EditAttach~~

The Kolakoski word can be defined in a number of different ways, but probably the simplest is as the unique infinite word <b>k</b> over the alphabet {1, 2}, starting with 1, such that the sequence of lengths of blocks of consecutive identical symbols is equal to <b>k</b> itself.

The first few terms are 12211212212211211221211212211211212212211212212112.  As you can see, the lengths of successive blocks are 1,2,2,1,1, etc., the sequence itself.

W. Kolakoski asked [Elementary Problem 5304, Amer. Math. Monthly <b>72</b> (1965), 674] if the symbols "1" and "2" occur with limiting frequency 1/2.  This problem is still open.  The best result is that if the frequency exists, then the frequence is between .499 and .501, and is due to Chv&aacute;tal in a technical report.

The image shows a discussion of the problem at an Oberwolfach meeting, December 16 1988.

-- Main.JeffreyShallit - 13 Jul 2011
   * kolakoski-oberwolfach.JPG: <br />
    <img src="%ATTACHURLPATH%/kolakoski-oberwolfach.JPG" alt="kolakoski-oberwolfach.JPG"  width="1000"  />

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	kolakoski-oberwolfach.JPG	r1	manage	3045.0 K	2011-07-13 - 11:38	JeffreyShallit

Topic revision: r1 - 2011-07-13 - JeffreyShallit

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit