| 1 | # Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020 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 <http://www.gnu.org/licenses/>. | ||||||||||||||
| 17 | |||||||||||||||
| 18 | package Math::NumSeq::HofstadterFigure; | ||||||||||||||
| 19 | 2 | ▶ | use 5.004; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 20 | 2 | ▶ | use strict; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 21 | |||||||||||||||
| 22 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 23 | 2 | $VERSION = 75; | |||||||||||||
| 24 | |||||||||||||||
| 25 | 2 | ▶ | use Math::NumSeq; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 26 | 2 | @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 | ▶ | use constant description => Math::NumSeq::__('Hofstadter figure sequence.'); | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 34 | 2 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 35 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 36 | 2 | ▶ | use constant i_start => 1; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 37 | |||||||||||||||
| 38 | 2 | ▶ | use constant parameter_info_array => | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 39 | [ | ||||||||||||||
| 40 | { name => 'start', | ||||||||||||||
| 41 | type => 'integer', | ||||||||||||||
| 42 | default => '1', | ||||||||||||||
| 43 | width => 2, | ||||||||||||||
| 44 | minimum => 1, | ||||||||||||||
| 45 | # description => Math::NumSeq::__(''), | ||||||||||||||
| 46 | }, | ||||||||||||||
| 47 | 2 | ]; | |||||||||||||
| 48 | |||||||||||||||
| 49 | 2 | ▶ | sub values_min { | ||||||||||||
|
Subroutine
values_min: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||
| 50 | 2 | my ($self) = @_; | |||||||||||||
| 51 | 2 | 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 | 2 | 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 | 2 | ▶ | sub oeis_anum { | ||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||
| 85 | 2 | my ($self) = @_; | |||||||||||||
| 86 | 2 | 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 | 2 | = (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 | 2 | 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 | 2 | 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 | 97 | ▶ | sub rewind { | ||||||||||||
|
Subroutine
rewind: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||
| 231 | 97 | my ($self) = @_; | |||||||||||||
| 232 | 97 | $self->{'i'} = $self->i_start; | |||||||||||||
| 233 | |||||||||||||||
| 234 | 97 | my $start = $self->{'start'}; | |||||||||||||
| 235 | 97 | $self->{'small_inc'} = $small_inc[$start]; | |||||||||||||
| 236 | |||||||||||||||
| 237 | 97 | ▶ | if ($self->{'small_inc'}) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 238 | 16 | $self->{'grow_upto'} = $small_upto[$start]; | |||||||||||||
| 239 | 16 | $self->{'grow_inc'} = $small_upto_inc[$start]; | |||||||||||||
| 240 | } else { | ||||||||||||||
| 241 | 81 | $self->{'small_inc'} = [ (1 .. $start-1), $start+2 ]; | |||||||||||||
| 242 | 81 | $self->{'grow_upto'} = $start+3; | |||||||||||||
| 243 | 81 | $self->{'grow_inc'} = 3; | |||||||||||||
| 244 | } | ||||||||||||||
| 245 | $self->{'upto'} = [ $start, | ||||||||||||||
| 246 | 97 | $self->{'grow_upto'} ]; | |||||||||||||
| 247 | $self->{'inc'} = [ 0, | ||||||||||||||
| 248 | 97 | $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 | 30040 | ▶ | sub next { | ||||||||||||
|
Subroutine
next: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||||||
| 256 | 30040 | my ($self) = @_; | |||||||||||||
| 257 | ### HofstadterFigure next(): "$self->{'i'}" | ||||||||||||||
| 258 | ### upto: join (', ',@{$self->{'upto'}}) | ||||||||||||||
| 259 | ### inc : join (', ',@{$self->{'inc'}}) | ||||||||||||||
| 260 | |||||||||||||||
| 261 | 30040 | my $i = $self->{'i'}++; | |||||||||||||
| 262 | 30040 | my $upto = $self->{'upto'}; | |||||||||||||
| 263 | 30040 | my $inc = $self->{'inc'}; | |||||||||||||
| 264 | |||||||||||||||
| 265 | 30040 | my $add = $inc->[0]++; | |||||||||||||
| 266 | ### prospective add: $add | ||||||||||||||
| 267 | |||||||||||||||
| 268 | 30040 | ▶ | if (defined (my $next_inc = $self->{'small_inc'}->[$add])) { | ||||||||||||
|
Branch: 2 branches
| |||||||||||||||
| 269 | ### small next_inc: $next_inc | ||||||||||||||
| 270 | 968 | $inc->[0] = $next_inc; | |||||||||||||
| 271 | |||||||||||||||
| 272 | } elsif ($add >= $upto->[1]) { | ||||||||||||||
| 273 | ### must skip this increment ... | ||||||||||||||
| 274 | ### add now: $inc->[0] | ||||||||||||||
| 275 | 1664 | $add = $inc->[0]++; | |||||||||||||
| 276 | |||||||||||||||
| 277 | # diff=26 already seen (6), at i=22 value=311 prev_value=285 | ||||||||||||||
| 278 | |||||||||||||||
| 279 | 1664 | my $pos = 1; | |||||||||||||
| 280 | 1664 | for (;;) { | |||||||||||||
| 281 | ### $pos | ||||||||||||||
| 282 | 1908 | ▶ | if ($pos >= $#$upto) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 283 | ### grow ... | ||||||||||||||
| 284 | 134 | push @$upto, $self->{'grow_upto'}; | |||||||||||||
| 285 | 134 | push @$inc, $self->{'grow_inc'}; | |||||||||||||
| 286 | } | ||||||||||||||
| 287 | |||||||||||||||
| 288 | 1908 | my $posadd = $inc->[$pos]++; | |||||||||||||
| 289 | ### $posadd | ||||||||||||||
| 290 | 1908 | $upto->[$pos] += $posadd; | |||||||||||||
| 291 | |||||||||||||||
| 292 | 1908 | ▶ | if (defined (my $next_inc = $self->{'small_inc'}->[$posadd])) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 293 | ### small pos next_inc: $next_inc | ||||||||||||||
| 294 | 980 | $inc->[$pos] = $next_inc; | |||||||||||||
| 295 | 980 | last; | |||||||||||||
| 296 | } | ||||||||||||||
| 297 | 928 | ▶ | if ($posadd < $upto->[$pos+1]) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 298 | ### less than next upto: $upto->[$pos+1] | ||||||||||||||
| 299 | 684 | last; | |||||||||||||
| 300 | } | ||||||||||||||
| 301 | 244 | $upto->[$pos]++; # skip and to next level | |||||||||||||
| 302 | 244 | $inc->[$pos]++; | |||||||||||||
| 303 | 244 | $pos++; | |||||||||||||
| 304 | } | ||||||||||||||
| 305 | } | ||||||||||||||
| 306 | ### $add | ||||||||||||||
| 307 | ### for return value: $upto->[0] + $add | ||||||||||||||
| 308 | 30040 | return ($i, | |||||||||||||
| 309 | ($upto->[0] += $add)); | ||||||||||||||
| 310 | } | ||||||||||||||
| 311 | |||||||||||||||
| 312 | 2 | 1; | |||||||||||||
| 313 | __END__ | ||||||||||||||