NumSeq/CollatzSteps.pm

filter: Statementstmt 88.7% 110 / 124 Branchbran 75.0% 42 / 56 Conditioncond 28.5% 2 / 7 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 100% 17 / 17 Podpod 85.7% 6 / 7 totaltotal 82.3% 177 / 215 CC 32 SCAR 29.7
CC
32
Cov
82%
ith
35.6
description
4.0
pred
2.3
CRAP 19.4
« NumSeq/TotientPerfect.pm ↑ Summary NumSeq/PisanoPeriod.pm »
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  
19 # step_type up,down, up_reduced, down_reduced
20 # diff=down-up frac=up/down
21 # completeness
22 # to_peak, after_peak, to_drop, to_last_drop,
23 # to_pow2 after_pow2
24 # first_drop first_down
25 # last_drop last_down
26 # peak
27 #
28  
29 # Maybe "before_drop", "after_drop"
30 # Maybe "before_peak", "after_peak"
31 # Maybe +1 count steps from 1.
32 #
33  
34 # on_values=>'even' is 2*i gives +1 for "both" and "down", no change to "up"
35 # on_values=>'odd' is 2*i+1
36 # starts 3*(2i+1)+1 = 6i+4 -> 3i+2
37 #
38 # i=0 for odd same as Odd->ith() ?
39  
40 # 2^E(N) = 3^O(N) * N * Res(N)
41 # log(2^E(N)) = log(3^O(N) * N * Res(N))
42 # log(2^E(N)) = log(3^O(N)) + log(N) + log(Res(N))
43 # E(N)*log(2) = O(N)*log(3) + log(N) + log(Res(N))
44 # log(Res(N)) = O(N)*log(3) - E(N)*log(2) + log(N)
45  
46 # "Glide" how many steps to get a value < N.
47 #
48  
49 package Math::NumSeq::CollatzSteps;
50 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
52  
53 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
54 2 $VERSION = 75;
55  
56 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
57 2 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
58 2 @ISA = ('Math::NumSeq::Base::IterateIth',
59 'Math::NumSeq');
60 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
61  
62 # uncomment this to run the ### lines
63 # use Smart::Comments;
64  
65 # use constant name => Math::NumSeq::__('Collatz Steps');
66 6 ▶sub description {
Subroutine description: called CC=4 SCAR=13.9
Pod documented
67 6 my ($self) = @_;
68 6 ▶ if (ref $self) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $self) 3 3 6
69 3 ▶ if ($self->{'step_type'} eq 'up') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"step_type"} eq "up") 1 2 3
70 1 return Math::NumSeq::__('Number of up steps to reach 1 in the Collatz "3n+1" problem.');
71 }
72 2 ▶ if ($self->{'step_type'} eq 'down') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"step_type"} eq "down") 1 1 2
73 1 return Math::NumSeq::__('Number of down steps to reach 1 in the Collatz "3n+1" problem.');
74 }
75 }
76 4 return Math::NumSeq::__('Number of steps to reach 1 in the Collatz "3n+1" problem.');
77 }
78  
79 61 ▶sub default_i_start {
Subroutine default_i_start: called CC=2 SCAR=7.2
Pod undocumented
80 61 my ($self) = @_;
81 61 ▶ return ($self->{'on_values'} eq 'odd' ? 0 : 1);
Branch: 1 branch
BranchTrueFalseTotal
$self->{'on_values'} eq 'odd' ? : 0 61 61
82 }
83 21 ▶sub values_min {
Subroutine values_min: called CC=1 SCAR=0.0
Pod documented
84 21 my ($self) = @_;
85 21 return ($self->ith($self->i_start));
86 }
87 2 ▶use constant characteristic_count => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
88 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
89 2 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
90  
91 2 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
92 [
93 # { name => 'end_type',
94 # share_key => 'end_type_1drop',
95 # display => Math::NumSeq::__('End Type'),
96 # type => 'enum',
97 # default => 'one',
98 # choices => ['one','drop','to_peak','from_peak','pow2'],
99 # choices_display => [Math::NumSeq::__('One'),
100 # Math::NumSeq::__('Drop'),
101 # Math::NumSeq::__('To Peak'),
102 # Math::NumSeq::__('From Peak'),
103 # Math::NumSeq::__('Pow2'),
104 # ],
105 # # description => Math::NumSeq::__(''),
106 # },
107  
108 { name => 'step_type',
109 share_key => 'step_type_bothupdown',
110 display => Math::NumSeq::__('Step Type'),
111 type => 'enum',
112 default => 'both',
113 choices => ['both','up','down',
114 # 'diff', 'both+1',
115 ],
116 choices_display => [Math::NumSeq::__('Both'),
117 Math::NumSeq::__('Up'),
118 Math::NumSeq::__('Down'),
119 ],
120 description => Math::NumSeq::__('Which steps to count, the 3*n+1 ups, the n/2 downs, or both.'),
121 },
122  
123 # secret extra 'odd1' for 2*i-1 starting i=1 to help offset of A075680
124 { name => 'on_values',
125 share_key => 'on_values_aoe',
126 display => Math::NumSeq::__('On Values'),
127 type => 'enum',
128 default => 'all',
129 choices => ['all','odd','even'],
130 choices_display => [Math::NumSeq::__('All'),
131 Math::NumSeq::__('Odd'),
132 Math::NumSeq::__('Even')],
133 description => Math::NumSeq::__('The values to act on, either all integers or just odd or even.'),
134 },
135 2 ];
136  
137 #------------------------------------------------------------------------------
138 # cf
139 # A139399 steps to reach cycle 4-2-1, so is steps-2 except at 4,2,1
140 # A112695 similar
141 # A064433 steps to reach 2, which is -1 except at n=1
142 #
143 # A066861 steps x/2 and (3x+1)/2
144 # A058633 steps of n cumulative
145 # A070975 steps for n prime
146 # A075677 one reduction 3x+1/2^r on the odd numbers, r as big as possible
147 # A014682 one step 3x+1 or x/2 on the integers
148 # A006884 new record for highest point reached in iteration
149 # A006885 that record high position
150 #
151 # A102419 "dropping time" steps to go below initial
152 # A217934 new highs of dropping time steps to go below initial
153 # A060412 n where those highs occur
154 #
155 # A074473 "dropping time" + 1, counting initial as step 1
156 # A075476 "dropping time" of numbers 64n+7
157 # A075477 "dropping time" of numbers 64n+15
158 # A075478 "dropping time" of numbers 64n+27
159 # A075480 "dropping time" of numbers 64n+39
160 # A075481 "dropping time" of numbers 64n+47
161 # A075482 "dropping time" of numbers 64n+59
162 # A075483 "dropping time" of numbers 64n+63
163 # A060445 "dropping time" of odd numbers 2n+1
164 # A060412 n start for new record "dropping time"
165 # A217934 new record "dropping time"
166 #
167 # A005184 multiple k*n occurs in Collatz trajectory
168 # A055509 number of odd primes in trajectory
169 # A055510 largest odd prime in trajectory
170 # A060322 how many integers have steps=n
171 # A070917 steps is a divisor of n
172 #
173 # A088975 collatz tree breadth-first
174 # A088976 collatz tree breadth-first
175 # A127824 breadth first sorted within rows
176 #
177 2 my %oeis_anum =
178 ('one,all,both' => 'A006577',
179 'one,all,up' => 'A006667', # triplings
180 'one,even,up' => 'A006667', # triplings unchanged by even 2*i
181 'one,all,down' => 'A006666', # halvings
182 # OEIS-Catalogue: A006577
183 # OEIS-Catalogue: A006667 step_type=up
184 # OEIS-Other: A006667 step_type=up on_values=even
185 # OEIS-Catalogue: A006666 step_type=down
186  
187 'one,even,both' => 'A008908', # +1 from "all"
188 'one,all,both+1' => 'A008908', # +1 from "all"
189 # OEIS-Catalogue: A008908 on_values=even
190 # OEIS-Other: A008908 step_type=both+1
191  
192 'one,odd,both+1' => 'A064685',
193 'one,odd1,down' => 'A166549',
194 # OEIS-Catalogue: A064685 on_values=odd step_type=both+1
195 # OEIS-Catalogue: A166549 on_values=odd1 step_type=down
196  
197 # A075680 up steps for odd 2n-1 0,2,1,5,6,4,etc starting n=1 2n-1=1
198 # it being defined as steps of (3x+1)/2^r for maximum r
199 'one,odd1,up' => 'A075680',
200 # OEIS-Catalogue: A075680 on_values=odd1 step_type=up
201  
202 #--------------
203 # drop
204  
205 'drop,all,both' => 'A102419', # "dropping time"
206 'drop,all,both+1' => 'A074473', # "dropping time"
207 'drop,all,down' => 'A126241',
208 # OEIS-Catalogue: A102419 end_type=drop
209 # OEIS-Catalogue: A074473 end_type=drop step_type=both+1
210 # OEIS-Catalogue: A126241 end_type=drop step_type=down
211  
212 'drop,odd,both' => 'A060445', # odd numbers 2n+1 so n=0 for odd=1
213 'drop,odd,up' => 'A122458',
214 # OEIS-Catalogue: A060445 end_type=drop on_values=odd
215 # OEIS-Catalogue: A122458 end_type=drop on_values=odd step_type=up
216  
217 # Not quite A087225 is "position" of peak reckoning start as position=1
218 # as opposed to value=0 many "steps" here.
219 'to_peak,all,both+1' => 'A087225',
220 # OEIS-Catalogue: A087225 end_type=to_peak step_type=both+1
221  
222 #--------------
223 # pow2
224  
225 'pow2,all,both' => 'A208981',
226 # OEIS-Catalogue: A208981 end_type=pow2
227 );
228 3 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
229 3 my ($self) = @_;
230 3 return $oeis_anum{"$self->{'end_type'},$self->{'on_values'},$self->{'step_type'}"};
231 }
232  
233 #------------------------------------------------------------------------------
234  
235 5 ▶sub new {
Subroutine new: called CC=2 SCAR=7.1
Pod documented
236 5 my $self = shift->SUPER::new(@_);
237 5 ▶ $self->{'end_type'} ||= 'one';
Condition50%1/2
$self->{"end_type"} ||= "one"
l!l
05
MC/DC0%0/1
$self->{"end_type"} ||= "one"
$self->{"end_type"}
Truth table50%1/2
A
A= $self->{"end_type"}
Aresult
11
00
238 5 return $self;
239 }
240  
241 2 ▶use constant 1.02 _UV_LIMIT => do { # version 1.02 for leading underscore
Subroutine BEGIN: called CC=2 SCAR=6.9
242 2 my $limit = ~0;
243 2 my $bits = 0;
244 2 ▶ while ($limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($limit) 128 2 130
245 128 $bits++;
246 128 $limit >>= 1;
247 }
248 2 $bits -= 2;
249 2 (1 << $bits) - 1
250 2 };
251  
252 185 ▶sub ith {
Subroutine ith: called CC=25 SCAR=35.7
Pod documented
253 185 my ($self, $i) = @_;
254 ### CollatzSteps ith(): $i
255 ### end_type: $self->{'end_type'}
256  
257 185 ▶ if ($self->{'on_values'} eq 'odd') {
Branch: 3 branches
BranchTrueFalseTotal
if ($self->{'on_values'} eq 'odd') { } 0 185 185
elsif ($self->{'on_values'} eq 'odd1') { } 0 185 185
elsif ($self->{'on_values'} eq 'even') { } 0 185 185
258 0 $i = 2*$i+1; # i=0 is odd number 1
259 } elsif ($self->{'on_values'} eq 'odd1') {
260 0 $i = 2*$i-1; # i=1 is odd number 1
261 } elsif ($self->{'on_values'} eq 'even') {
262 0 $i *= 2;
263 }
264 185 my $orig_i = $i;
265  
266 185 my $ups = 0;
267 185 my $downs_sans_trailing = 0;
268 185 my $downs = 0;
269 185 my $peak_ups = 0;
270 185 my $peak_downs = 0;
271 185 ▶ if ($i >= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= 2) 137 48 185
272 137 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 137 137
273 0 return $i;
274 }
275  
276 137 my $peak_i = $i;
277 137 ▶ my $end = ($self->{'end_type'} eq 'drop' ? $i : 1);
Branch: 1 branch
BranchTrueFalseTotal
$self->{'end_type'} eq 'drop' ? : 0 137 137
278  
279 137 OUTER: for (;;) {
280 458 $downs_sans_trailing = $downs;
281 458 ▶ until ($i & 1) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($i & 1) 838 322 1160
282 838 $i >>= 1;
283 838 $downs++;
284 838 ▶ last OUTER if $i <= $end;
Branch: 1 branch
BranchTrueFalseTotal
if $i <= $end 136 702 838
285 }
286 ### odd: $i
287  
288 322 ▶ if ($i > _UV_LIMIT) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > '4611686018427387903') 1 321 322
289 1 $i = Math::NumSeq::_to_bigint($i);
290  
291 ### using bigint: "$i"
292 1 for (;;) {
293 ### odd: "$i"
294 309 $i->bmul(3);
295 309 $i->binc();
296 309 $ups++;
297  
298 309 ▶ if ($i > $peak_i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > $peak_i) 1 308 309
299 1 $peak_ups = $ups;
300 1 $peak_downs = $downs;
301 1 $peak_i = $i;
302 }
303  
304 309 $downs_sans_trailing = $downs;
305 309 ▶ until ($i->is_odd) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($i->is_odd) 554 308 862
306 554 $i->brsft(1);
307 554 $downs++;
308 554 ▶ last OUTER if $i <= $end;
Branch: 1 branch
BranchTrueFalseTotal
if $i <= $end 1 553 554
309 }
310 }
311 }
312  
313 321 $i = 3*$i + 1;
314 321 $ups++;
315  
316 321 ▶ if ($i > $peak_i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > $peak_i) 170 151 321
317 170 $peak_ups = $ups;
318 170 $peak_downs = $downs;
319 170 $peak_i = $i;
320 }
321 }
322 }
323  
324 ### $ups
325 ### $downs
326 ### $downs_sans_trailing
327  
328 185 ▶ if ($self->{'end_type'} eq 'to_peak') {
Branch: 3 branches
BranchTrueFalseTotal
if ($self->{'end_type'} eq 'to_peak') { } 0 185 185
elsif ($self->{'end_type'} eq 'from_peak') { } 0 185 185
elsif ($self->{'end_type'} eq 'pow2') { } 0 185 185
329 0 $ups = $peak_ups;
330 0 $downs = $peak_downs;
331 } elsif ($self->{'end_type'} eq 'from_peak') {
332 0 $ups -= $peak_ups;
333 0 $downs -= $peak_downs;
334 } elsif ($self->{'end_type'} eq 'pow2') {
335 0 $downs = $downs_sans_trailing;
336 }
337  
338 185 my $step_type = $self->{'step_type'};
339 185 ▶ if ($step_type eq 'up') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "up") 61 124 185
340 61 return $ups;
341 }
342 124 ▶ if ($step_type eq 'down') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "down") 61 63 124
343 61 return $downs;
344 }
345 63 ▶ if ($step_type eq 'diff') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "diff") 0 63 63
346 0 return $downs - $ups;
347 }
348 63 ▶ if ($step_type eq 'completeness') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "completeness") 0 63 63
349 # maximum C(N) < ln(2)/ln(3) = 0.63
350 0 return $ups / $downs;
351 }
352 63 ▶ if ($step_type eq 'gamma') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "gamma") 0 63 63
353 0 ▶ return $downs / (log($orig_i) || 1);
Condition0%0/2
log $orig_i || 1
l!l
00
MC/DC0%0/1
log $orig_i || 1
log $orig_i
Truth table0%0/2
A
A= log $orig_i
Aresult
11
00
354 }
355 63 ▶ if ($step_type eq 'residue') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "residue") 0 63 63
356 # log(Res(N)) = Odd(N)*log(3) - Even(N)*log(2) + log(N)
357 0 return $ups*log(3) - $downs*log(2) + log($orig_i);
358 }
359 63 ▶ if ($step_type eq 'both+1') {
Branch: 1 branch
BranchTrueFalseTotal
if ($step_type eq "both+1") 0 63 63
360 0 return $ups + $downs + 1;
361 }
362 # $step_type eq 'both'
363 63 return $ups + $downs;
364 }
365  
366 18 ▶sub pred {
Subroutine pred: called CC=2 SCAR=8.1
Pod documented
367 18 my ($self, $value) = @_;
368 18 ▶ return ($value == int($value)
Condition33%1/3
$value == int $value && $value >= $self->values_min
!ll&&!rl&&r
0018
MC/DC0%0/2
$value == int $value && $value >= $self->values_min
$value == int $value $value >= $self->values_min
Truth table33%1/3
A && B
A= $value == int $valueB= $value >= $self->values_min
ABresult
0X0
100
111
369 && $value >= $self->values_min);
370 }
371  
372 2 1;
373 __END__
« NumSeq/TotientPerfect.pm ↑ Summary NumSeq/PisanoPeriod.pm »