File Coverage

blib/lib/Math/NumSeq/HofstadterFigure.pm
Criterion Covered Total %
statement 66 66 100.0
branch 12 12 100.0
condition n/a
subroutine 13 13 100.0
pod 4 4 100.0
total 95 95 100.0


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             package Math::NumSeq::HofstadterFigure;
19 2     2   6964 use 5.004;
  2         6  
20 2     2   6 use strict;
  2         3  
  2         46  
21              
22 2     2   6 use vars '$VERSION', '@ISA';
  2         2  
  2         104  
23             $VERSION = 72;
24              
25 2     2   342 use Math::NumSeq;
  2         2  
  2         81  
26             @ISA = ('Math::NumSeq');
27              
28             # uncomment this to run the ### lines
29             #use Smart::Comments;
30              
31              
32             # use constant name => Math::NumSeq::__('Hofstadter Figure');
33 2     2   8 use constant description => Math::NumSeq::__('Hofstadter figure sequence.');
  2         2  
  2         6  
34 2     2   7 use constant characteristic_increasing => 1;
  2         4  
  2         100  
35 2     2   7 use constant characteristic_integer => 1;
  2         3  
  2         68  
36 2     2   5 use constant i_start => 1;
  2         3  
  2         86  
37              
38 2         818 use constant parameter_info_array =>
39             [
40             { name => 'start',
41             type => 'integer',
42             default => '1',
43             width => 2,
44             minimum => 1,
45             # description => Math::NumSeq::__(''),
46             },
47 2     2   7 ];
  2         2  
48              
49             sub values_min {
50 2     2 1 8 my ($self) = @_;
51 2         4 return $self->{'start'};
52             }
53              
54             #------------------------------------------------------------------------------
55              
56             # A005228 - seq and first diffs make all integers, increasing
57             # A030124 - the first diffs
58             #
59             # cf A061577 - starting from 2
60             # A061578 - starting from 2 first diffs
61             # 2, 3, 7, 12, 18, 26, 35, 45,
62             # 1, 4, 5, 6, 8, 9, 10, 11, 13,
63             #
64             # A140778 - seq and first diffs make all positive integers,
65             # each int applied to one of the two in turn
66             # A140779 - its first diffs
67             #
68             # A037257 - seq + first diffs + second diffs make all integers
69             # A037258 - the first diffs
70             # A037259 - the second diffs
71             # A081145
72             #
73             my @oeis_anum = (
74             # OEIS-Catalogue array begin
75             undef, # start=0
76             'A005228', #
77             'A061577', # start=2
78             'A022935', # start=3
79             'A022936', # start=4
80             'A022937', # start=5
81             'A022938', # start=6
82             # OEIS-Catalogue array end
83             );
84             sub oeis_anum {
85 2     2 1 6 my ($self) = @_;
86 2         4 return $oeis_anum[$self->{'start'}];
87             }
88              
89             #------------------------------------------------------------------------------
90              
91             # start S
92             # S, S+1, S+2, ..., S+(S-1), S+(S+1), S+(S+2)
93              
94             # $upto[0] is the previous value returned
95             # $inc[0] is the amount to increment it by next time
96             #
97             # $upto[1] is the sequence at a previous position
98             # if $inc[0] == $upto[1] then that increment must be skipped,
99             # and advance $upto[1] for the next to skip#
100             #
101             # initial
102             # upto[0] = 1
103             # inc[0] = 0
104             #
105             # return 1+0=1, small inc[0] -> 2
106             # upto[0] = 1
107             # inc[0] = 2
108             #
109             # return 1+2=3, small inc[0] -> 4
110             # upto[0] = 3
111             # inc[0] = 4
112             #
113             # return 3+4=7, small inc[0] 4 -> 5
114             # upto[0] = 7
115             # inc[0] = 5
116             #
117             # return 7+5=12, small inc[0] 5 -> 6
118             # upto[0] = 12
119             # inc[0] = 6
120             #
121             # return 12+6=18, small inc[0] 6 -> outside
122             # upto[0] = 12
123             # inc[0] = 8
124             # upto[1] = 12
125             # inc[1] = 6
126             #
127             # inc[0]==upto[1] so skip to inc[0]=4
128             # add 4 to return upto[0]=3+4=7
129             # $inc[0]++
130             # next upto[1] is 7
131             # upto[0] = 7
132             # upto[1] = 7
133             # inc[0] = 5
134             # inc[1] = 4
135             #
136             # add 7+5 to 12, inc[0]++
137             # upto[0] = 12
138             # upto[1] = 7
139             # inc[0] = 6
140             # inc[1] = 4
141             #
142             # add 12+6=18, inc[0]++
143             # upto[0] = 18
144             # upto[1] = 7
145             # inc[0] = 7
146             # inc[1] = 4
147             #
148             # inc[0]==upto[1] so skip to inc[0]=8
149             # add 8 to return upto[0]=18+8=26
150             # step upto[1] add inc[1]++ to 7+5=12
151             # upto[0] = 26
152             # upto[1] = 12
153             # inc[0] = 7
154             # inc[1] = 6
155             #
156              
157             # start=1
158             # seq 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191,
159             # diffs 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22,
160             #
161             # start=2
162             # seq 2, 3, 7, 12, 18, 26,
163             # diffs 1 4 5 6 8
164             #
165             # start=4
166             # seq 4, 5, 7, 10, 16, 24,
167             # diffs 1 2 3 6 8 9
168             #
169             # start=5
170             # seq 5, 6, 8, 11, 15, 22, 31,
171             # diffs 1 2 3 4, 7 9 10
172             #
173             # start=6
174             # seq 6, 7, 9, 12, 16, 21, 29,
175             # diffs 1 2 3 4, 5, 8 10
176             #
177             # start=7
178             # seq 7, 8, 10, 13, 17, 22, 28, 37
179             # diffs 1 2 3 4, 5, 6 9 11
180              
181             my @small_inc
182             = (undef, # start=0 impossible
183              
184             # 0 1 2 3 4 5 6 7
185             #
186             [ 2, undef, 4, undef, 5, 6, 7 ], # start=1
187             [ 1, 4, undef, undef, 5, 6, 7 ], # start=2
188              
189             # start=3
190             # seq 3, 4, 6, 11, 18, 26,
191             # diffs 1 2 5 7 8 9
192             #
193             # 0 1 2 3 4 5 6 7
194             [ 1, 2, 5, undef, undef, 7, undef, 8 ],
195              
196             # # start=4
197             # [ 1, 2, 3, 6, ],
198              
199             # # start=5
200             # [ 1, 2, 3, 4, 7, undef, undef, 9 ],
201              
202             # # start=6
203             # # 0 1 2 3 4 5
204             # [ 1, 2, 3, 4, 5, 8 ],
205              
206             # # start=7
207             # # 0 1 2 3 4 5 6
208             # [ 1, 2, 3, 4, 5, 6, 9 ],
209             );
210             my @small_upto = (undef, # 0
211             7, # 1
212             7, # 2
213             11, # 3
214              
215             # 7, # 4
216             # 11, # 5
217             # 9, # 6
218             # 10, # 7
219             );
220             my @small_upto_inc = (undef, # 0
221             5, # 1
222             5, # 2
223             7, # 3
224              
225             # 3, # 4
226             # 4, # 5
227             # 3, # 6
228             # 3, # 7
229             );
230             sub rewind {
231 97     97 1 24270 my ($self) = @_;
232 97         170 $self->{'i'} = $self->i_start;
233              
234 97         86 my $start = $self->{'start'};
235 97         88 $self->{'small_inc'} = $small_inc[$start];
236              
237 97 100       184 if ($self->{'small_inc'}) {
238 16         15 $self->{'grow_upto'} = $small_upto[$start];
239 16         16 $self->{'grow_inc'} = $small_upto_inc[$start];
240             } else {
241 81         194 $self->{'small_inc'} = [ (1 .. $start-1), $start+2 ];
242 81         90 $self->{'grow_upto'} = $start+3;
243 81         76 $self->{'grow_inc'} = 3;
244             }
245             $self->{'upto'} = [ $start,
246 97         122 $self->{'grow_upto'} ];
247             $self->{'inc'} = [ 0,
248 97         200 $self->{'grow_inc'} ];
249             }
250              
251             # # 1->2->4->5->6->7
252             # # 0 1 2 3 4 5 6
253             # my @small_inc = (undef, 2, 4, undef, 5, 6);
254              
255             sub next {
256 30040     30040 1 179669 my ($self) = @_;
257             ### HofstadterFigure next(): "$self->{'i'}"
258             ### upto: join (', ',@{$self->{'upto'}})
259             ### inc : join (', ',@{$self->{'inc'}})
260              
261 30040         21514 my $i = $self->{'i'}++;
262 30040         17994 my $upto = $self->{'upto'};
263 30040         17443 my $inc = $self->{'inc'};
264              
265 30040         18409 my $add = $inc->[0]++;
266             ### prospective add: $add
267              
268 30040 100       45303 if (defined (my $next_inc = $self->{'small_inc'}->[$add])) {
    100          
269             ### small next_inc: $next_inc
270 968         687 $inc->[0] = $next_inc;
271              
272             } elsif ($add >= $upto->[1]) {
273             ### must skip this increment ...
274             ### add now: $inc->[0]
275 1664         1180 $add = $inc->[0]++;
276              
277             # diff=26 already seen (6), at i=22 value=311 prev_value=285
278              
279 1664         1012 my $pos = 1;
280 1664         981 for (;;) {
281             ### $pos
282 1908 100       2176 if ($pos >= $#$upto) {
283             ### grow ...
284 134         197 push @$upto, $self->{'grow_upto'};
285 134         125 push @$inc, $self->{'grow_inc'};
286             }
287              
288 1908         1284 my $posadd = $inc->[$pos]++;
289             ### $posadd
290 1908         1167 $upto->[$pos] += $posadd;
291              
292 1908 100       2314 if (defined (my $next_inc = $self->{'small_inc'}->[$posadd])) {
293             ### small pos next_inc: $next_inc
294 980         657 $inc->[$pos] = $next_inc;
295 980         799 last;
296             }
297 928 100       1197 if ($posadd < $upto->[$pos+1]) {
298             ### less than next upto: $upto->[$pos+1]
299 684         584 last;
300             }
301 244         155 $upto->[$pos]++; # skip and to next level
302 244         156 $inc->[$pos]++;
303 244         158 $pos++;
304             }
305             }
306             ### $add
307             ### for return value: $upto->[0] + $add
308 30040         35226 return ($i,
309             ($upto->[0] += $add));
310             }
311              
312             1;
313             __END__