NumSeq/JugglerSteps.pm untested

filter: Statementstmt 0.0% 0 / 145 Branchbran 0.0% 0 / 40 Conditioncond 0.0% 0 / 20 MC/DCmcdc 0.0% 0 / 13 Subroutinesub 0.0% 0 / 20 Podpod 0.0% 0 / 5 totaltotal 0.0% 0 / 243 CC 21 SCAR 53.5
CC
21
Cov
0%
ith
420.0
next
6.0
oeis_anum
2.0
CRAP 211.2
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::JugglerSteps;
19 use 5.004;
20 use strict;
21  
22 use vars '$VERSION', '@ISA';
23 $VERSION = 75;
24  
25 use Math::NumSeq;
26 use Math::NumSeq::Base::IterateIth;
27 @ISA = ('Math::NumSeq::Base::IterateIth',
28 'Math::NumSeq');
29  
30 use Math::NumSeq::Base::Cache
31 'cache_hash',
32 'make_key';
33  
34 # uncomment this to run the ### lines
35 #use Devel::Comments;
36  
37 # use constant name => Math::NumSeq::__('Juggler Steps');
38 use constant description => Math::NumSeq::__('Number of steps to reach 1 in the Juggler sqrt sequence.');
39 use constant characteristic_count => 1;
40 use constant characteristic_smaller => 1;
41 use constant characteristic_increasing => 0;
42 use constant values_min => 0;
43 use constant i_start => 1;
44  
45 use constant parameter_info_array =>
46 [
47 { name => 'step_type',
48 display => Math::NumSeq::__('Step Type'),
49 type => 'enum',
50 default => 'both',
51 choices => ['up','down','both'],
52 choices_display => [Math::NumSeq::__('Up'),
53 Math::NumSeq::__('Down'),
54 Math::NumSeq::__('Both'),
55 ],
56 description => Math::NumSeq::__('Which steps to count, the n^(3/2) ups, the n^(1/2) downs, or both.'),
57 },
58 { name => 'juggler_type',
59 display => Math::NumSeq::__('Juggler Algorithm Type'),
60 type => 'string',
61 default => '1/2-3/2',
62 width => 9,
63 choices => ['1/2-3/2','2/3-3/2','3/4-4/3'],
64 description => Math::NumSeq::__('Juggler algorithm type, as the even power and odd power.'),
65 },
66 # { name => 'round_type',
67 # display => Math::NumSeq::__('Rounding Type'),
68 # type => 'enum',
69 # default => 'floor',
70 # choices => ['floor','round'],
71 # choices_display => [Math::NumSeq::__('Floor'),
72 # Math::NumSeq::__('Round'),
73 # ],
74 # description => Math::NumSeq::__('Rounding type.'),
75 # },
76 ];
77  
78 #------------------------------------------------------------------------------
79 # eg. 78901 peaks at about 370,000 digits ...
80 #
81 # cf
82 # A094683 - iteration, ie. n^(1/2) or n^(3/2)
83 # A094670 - smallest requiring n iterations
84 # A094679 - start requiring n iterations
85 # A094684 - records in plain seq
86 # A094698 - num steps where new record
87 # A143745 - next largest
88 # A094716 - largest value in trajectory starting from n
89 # A094778 - dropping time from odd
90 # A094804 - num primes in trajectory
91 # A094819 - steps starting 10^n
92 # A143742 - producing larger value
93 # A143743 - num digits
94 # A143744 - steps next largest
95 #
96 # A007321 - rounded steps
97 # A094685 - rounded iteration, ie. single powering
98 # A094693 - rounded records
99 # A094725 - rounded largest value in trajectory starting from n
100 # A095910 - rounded records
101 # A095911 - rounded num steps to records
102 #
103 # A095396 - 2/3-3/2 iteration
104 # A095397 - 2/3-3/2 largest in trajectory starting from n
105 # A095398 - 2/3-3/2 steps
106 #
107 # A095399 - 3/4-4/3 iteration
108 # A095400 - 3/4-4/3 largest value in trajectory starting from n
109 # A095401 - 3/4-4/3 steps
110 #
111 # up => '',
112 # # OEIS-Catalogue: step_type=up
113 #
114 # down => '',
115 # # OEIS-Catalogue: step_type=down
116 #
117 my %oeis_anum = (
118 # both up and down
119 both => { '1/2-3/2' => 'A007320',
120 # OEIS-Catalogue: A007320
121  
122 '2/3-3/2' => 'A095398',
123 # OEIS-Catalogue: A095398 juggler_type=2/3-3/2
124  
125 '3/4-4/3' => 'A095401',
126 # OEIS-Catalogue: A095401 juggler_type=3/4-4/3
127 },
128 );
129 sub oeis_anum {
130 my ($self) = @_;
131 return $oeis_anum{$self->{'step_type'}}->{$self->{'juggler_type'}};
132 }
133  
134 #------------------------------------------------------------------------------
135  
136 sub rewind {
137 my ($self) = @_;
138 ($self->{'epow'},$self->{'eroot'}, $self->{'opow'},$self->{'oroot'})
139 = ($self->{'juggler_type'} =~ m{(\d+)/(\d+)-(\d+)/(\d+)});
140 $self->{'i'} = i_start();
141 }
142  
143 use constant 1.02; # for leading underscore
144 use constant _UV_3_2_LIMIT => do {
145 my $limit = ~0;
146 my $bits = 0;
147 while ($limit) {
148 $bits++;
149 $limit >>= 1;
150 }
151 $bits = int($bits / 3);
152 (1 << $bits) - 1
153 };
154  
155 my %cache_upto;
156 sub next {
157 my ($self) = @_;
158 ### JugglerSteps next(): $self->{'i'}
159  
160 my $i = $self->{'i'}++;
161 my $pkey = ($self->{'pkey'} ||= do {
162 ### make pkey ...
163 my $k = make_key('JugglerSteps',
164 $self->{'juggler_type'},
165 $self->{'step_type'});
166 $cache_upto{$k} ||= 0;
167 $k
168 });
169 my $key_i = $pkey . $i;
170  
171 ### $pkey
172 ### $key_i
173 ### cache upto: "$cache_upto{$pkey} cf i=$i"
174  
175 if ($i < $cache_upto{$pkey}) {
176 ### fetch from cache ...
177 return ($i, cache_hash()->{$key_i});
178 } else {
179 ### store to cache ...
180 my $ret = $self->ith($i);
181 cache_hash()->{$key_i} = $ret;
182 $cache_upto{$pkey} = $i;
183 ### cache upto now: $cache_upto{$pkey}
184 return ($i, $ret);
185 }
186 }
187  
188 sub ith {
189 my ($self, $i) = @_;
190 ### JugglerSteps ith(): $i
191 my $count = 0;
192 if ($i <= 1) {
193 return $count;
194 }
195  
196 my $pkey = $self->{'pkey'};
197 my $step_type = $self->{'step_type'};
198 my $count_up = ($step_type ne 'down');
199 my $count_down = ($step_type ne 'up');
200 my %seen;
201  
202 if ($self->{'juggler_type'} eq '1/2-3/2') {
203 ### 1/2 and 3/2 ...
204 for (;;) {
205 if ($pkey && $i < $cache_upto{$pkey}) {
206 my $c = cache_hash()->{$pkey.$i};
207 ### from cache: "$c at i=$i"
208 if ($c < 0) {
209 return $c;
210 } else {
211 return $c + $count;
212 }
213 }
214  
215 if ($i & 1) {
216 ### 1/2 odd: $i
217  
218 if ($i > _UV_3_2_LIMIT) {
219 $i = Math::NumSeq::_to_bigint($i);
220 ### using bigint: "$i"
221 for (;;) {
222 if ($pkey && $i < $cache_upto{$pkey}) {
223 my $c = cache_hash()->{$pkey.$i};
224 ### from cache: "$c at i=$i"
225 if ($c < 0) {
226 return $c;
227 } else {
228 return $c + $count;
229 }
230 }
231  
232 if ($i & 1) {
233 ### 1/2 odd: "$i"
234 $i->bmul($i*$i);
235 $count += $count_up;
236 } else {
237 ### 1/2 even: "$i"
238 $count += $count_down;
239 }
240 $i->bsqrt();
241 if ($i <= 1) {
242 return $count;
243 }
244 ### now: "$i count=$count"
245 if ($seen{$i}++) {
246 ### repeat of bigint: $i
247 return -1;
248 }
249 }
250 }
251  
252 $i *= $i*$i;
253 $count += $count_up;
254 } else {
255 ### even: $i
256 $count += $count_down;
257 }
258 $i = int(sqrt($i));
259 if ($i <= 1) {
260 return $count;
261 }
262 ### now: "$i count=$count"
263 if ($seen{$i}++) {
264 return -1;
265 }
266 }
267  
268 } else {
269 ### general case: "$self->{'epow'}/$self->{'eroot'}-$self->{'opow'}/$self->{'oroot'}"
270 $i = Math::NumSeq::_to_bigint($i);
271  
272 unless (($self->{'opow'} % $self->{'oroot'})
273 && ($self->{'epow'} % $self->{'eroot'})) {
274 return -1;
275 }
276  
277 for (;;) {
278 if ($pkey && $i < $cache_upto{$pkey}) {
279 my $c = cache_hash()->{$pkey.$i};
280 ### from cache: "$c at i=$i"
281 if ($c < 0) {
282 return $c;
283 } else {
284 return $c + $count;
285 }
286 }
287  
288 if ($i->is_odd) {
289 ### odd: "$i"
290 $i->bpow($self->{'opow'});
291 $i->broot($self->{'oroot'});
292 $count += $count_up;
293 } else {
294 ### even: "$i"
295 $i->bpow($self->{'epow'});
296 $i->broot($self->{'eroot'});
297 $count += $count_down;
298 }
299 if ($i <= 1) {
300 return $count;
301 }
302 ### now: "$i count=$count"
303 if ($seen{$i}++) {
304 ### repeat of: $i
305 return -1;
306 }
307 }
308 }
309 }
310  
311 sub pred {
312 my ($self, $value) = @_;
313 return ($value == int($value)
314 && $value >= 0);
315 }
316  
317 1;
318 __END__