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;
39: $self->[2]->next; # advance past first one (already generated)
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.
