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