File Coverage

blib/lib/Math/NumSeq/Kolakoski.pm
Criterion Covered Total %
statement 37 57 64.9
branch 0 6 0.0
condition 0 3 0.0
subroutine 12 13 92.3
pod 2 2 100.0
total 51 81 62.9


line stmt bran cond sub pod time code
1             # Copyright 2011, 2012, 2013, 2014 Kevin Ryde
2              
3             # This file is part of Math-NumSeq.
4             #
5             # Math-NumSeq is free software; you can redistribute it and/or modify
6             # it under the terms of the GNU General Public License as published by the
7             # Free Software Foundation; either version 3, or (at your option) any later
8             # version.
9             #
10             # Math-NumSeq is distributed in the hope that it will be useful, but
11             # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12             # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13             # for more details.
14             #
15             # You should have received a copy of the GNU General Public License along
16             # with Math-NumSeq. If not, see .
17              
18             # http://dimacs.rutgers.edu/TechnicalReports/abstracts/1993/93-84.html
19              
20              
21             package Math::NumSeq::Kolakoski;
22 1     1   1137723 use 5.004;
  1         4  
  1         52  
23 1     1   8 use strict;
  1         1  
  1         47  
24              
25 1     1   6 use vars '$VERSION', '@ISA';
  1         2  
  1         84  
26             $VERSION = 71;
27              
28 1     1   6 use Math::NumSeq;
  1         3  
  1         67  
29             @ISA = ('Math::NumSeq');
30              
31             # uncomment this to run the ### lines
32             #use Devel::Comments;
33              
34             # use constant name => Math::NumSeq::__('Kolakoski Sequence');
35 1     1   7 use constant description => Math::NumSeq::__('Kolakoski sequence 1,2,2,1,1,2,1,etc its own run lengths.');
  1         2  
  1         12  
36 1     1   5 use constant characteristic_increasing => 0;
  1         2  
  1         51  
37 1     1   4 use constant characteristic_integer => 1;
  1         2  
  1         49  
38 1     1   6 use constant values_min => 1;
  1         2  
  1         45  
39 1     1   6 use constant values_max => 2;
  1         1  
  1         52  
40 1     1   6 use constant i_start => 1;
  1         2  
  1         54  
41              
42             # cf A000002 - starting 1,2,2,1,1,
43             # A006928 - starting 1,2,1,1,...
44             # A064353 - 1,3 sequence
45             # A054353 - partial sums
46             # A078880 - starting from 2
47             # A054353 - partial sums, step 1 or 2, is kol(n)!=kol(n+1) the 2 gaps ...
48             # A074286 - partial sums minus n (variously repeating values)
49             # A054349 - successive generations as big decimals
50             # A042942 - something substitutional
51             # A013949 substitute
52             # A156077 digits ...
53             # A078929 A(n+k) = A(n)
54             # A081592 - runs of n many 1 or 2
55             #
56             # A156253 kol supp
57             # A064353 kol 1/3
58             # A001083 A00002 lengths after iterating 1,2,3,5,7,10,15
59             # A006928 lengths ...
60             # A042942 1,2,1,1 lengths after iterating 1,2,4,6,9,14,22
61             # A079729 1,2,3 starting 1,2,2
62             # A079730 1,2,3,4 starting 1,2,2
63             #
64             # A074290 - diff from n mod 2
65             # A074291 - positions of n odd having 1 or n even having 2
66             #
67             # A025142,A025143 - invert 1,2 so opposite run length
68             #
69             # A171899 van eck transform of A000002
70             #
71 1     1   5 use constant oeis_anum => 'A000002';
  1         2  
  1         336  
72              
73             sub rewind {
74 1     1 1 1 my ($self) = @_;
75 1         17 $self->{'i'} = $self->i_start;
76 1         4 $self->{'digits'} = [1];
77 1         4 $self->{'counts'} = [2];
78             }
79              
80             sub next {
81 0     0 1   my ($self) = @_;
82             ### Kolakoski next(): "$self->{'i'}"
83              
84 0           my $counts = $self->{'counts'};
85 0           my $digits = $self->{'digits'};
86 0           my $pos = -1;
87 0           my $digit;
88 0           for (;;) {
89 0 0         if (++$pos > $#$counts) {
90             ### all zeros to pos: $pos
91 0 0 0       if ($pos == 1 && $digits->[0] == 1) {
92             ### special case i=2,i=3 digit 2 ...
93 0           $counts->[0] = 2;
94 0           return ($self->{'i'}++, ($digits->[0] = 2));
95             }
96             ### extend for get i=3 leave i=4 state ...
97 0           push @$counts, 1;
98 0           push @$digits, ($digit = 2);
99 0           last;
100             }
101 0 0         if (--$counts->[$pos]) {
102             ### non-zero count at: "pos=$pos digit=$digits->[$pos], remaining count=$counts->[$pos]"
103 0           $digit = $digits->[$pos];
104 0           last;
105             }
106             }
107              
108 0           while (--$pos >= 0) {
109 0           $counts->[$pos] = $digit;
110 0           $digit = ($digits->[$pos] ^= 3);
111             }
112 0           return ($self->{'i'}++, $digit);
113              
114             }
115              
116             1;
117             __END__