Perl-Sensitive Sunglasses PerlMonks

### Kolakoski sequence generator

by ariels (Curate)
 on Jun 20, 2002 at 14:08 UTC Need Help??

```   1: #!/usr/local/bin/perl -w
2:
3: # The "Kolakoski sequence"
4: # (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000002)
5: # is the sequence beginning 2,2,1,1,2,1,2,2,1,2,2,1,1,2,...
6: # of alternating blocks of 1's and 2's, where the length
7: # of the k'th block is the value of the k'th element.  So
8: # the sequence has TWO 2's, then TWO 1's, then ONE 2, then
9: # ONE 1, then TWO 2's, then ONE 1, ...
10: #
11: # It's not a periodic sequence, but it is conjectured
12: # (i.e. it is thought to be true, but nobody has any idea
13: # how to prove it) that approximately half the elements
14: # are 1's.
15:
16: # Generate the Kolakoski sequence
17:
18: use strict;
19:
20: package Kolakoski;
21:
22: # Object format: [ WHAT, HOW_MANY, KOLAKOSKI ]
23: #
24: # WHAT: What we're generating now (1's or 2's)
25: # HOW_MANY: How many to generate (2 -> 1 -> 0)
26: # KOLAKOSKI: Sequence generator, to use when HOW_MANY == 0
27: sub new {
28:   my \$class = shift;
29:   \$class = ref(\$class) || \$class;
30:   bless [2, 2, undef], \$class
31: }
32:
33: sub next {
34:   my \$self = shift;
35:   if (\$self->[1] == 0) {
36:     if (! defined \$self->[2]) {
37:       # Generate a new object
38:       \$self->[2] = \$self->new;
40:     }
41:     # Use sequence object to generate next count
42:     \$self->[0] = 3 - \$self->[0]; # flip 1 <-> 2
43:     \$self->[1] = \$self->[2]->next;
44:   }
45:   -- \$self->[1];
46:   return \$self->[0];
47: }
48:
49:
50: package main;
51:
52: my \$n = shift || 100_000;
53: my \$n2;
54:
55: my \$k = new Kolakoski;
56:
57: for (1..\$n) {
58:   my \$v = \$k->next;
59:   print \$v;
60:   \$n2++ if \$v==2;
61: }
62: print "\n";
63: print "\$n2 / \$n 2's (@{[\$n2/\$n*100]}%)\n";
64:
65: # Notes
66: #
67: # 1. Some people prefer to start the sequence with a "1".
68: # If you're one of them, just print a "1" before starting
69: # the loop.
70: # 2. The number of objects required to print the first N
71: # elements is O(log N), IF the conjecture about the
72: # distribution of 2's in the sequence is true.
73: # 3. Simulations (not much more sophisticated than this
74: # one, although probably better written in C) suggest that
75: # the conjecture is true.  The number of 2's in the first
76: # N elements of the sequence appears to be  N/2+O(log(N)),
77: # but of course this too is unproven.
```

Replies are listed 'Best First'.
(MeowChow) Re: Kolakoski sequence generator
by MeowChow (Vicar) on Jun 20, 2002 at 17:11 UTC
You may enjoy these other solutions.
```   MeowChow
s aamecha.s a..a\u\$&owag.print```

Create A New User
Node Status?
node history
Node Type: perlcraft [id://176016]
Approved by SparkeyG
help
Chatterbox?

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (15)
As of 2017-11-21 17:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (308 votes). Check out past polls.

Notices?