NumSeq/AlmostPrimes.pm

filter: Statementstmt 97.6% 122 / 125 Branchbran 80.0% 40 / 50 Conditioncond 61.1% 11 / 18 MC/DCmcdc 33.3% 4 / 12 Subroutinesub 100% 16 / 16 Podpod 100% 5 / 5 totaltotal 87.6% 198 / 226 CC 33 SCAR 24.9
CC
33
Cov
90%
next
17.8
pred
16.3
values_min
2.1
CRAP 12.1
« NumSeq/TotientSteps.pm ↑ Summary NumSeq/KlarnerRado.pm »
1 # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2018, 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::AlmostPrimes;
19 1 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 1 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 1 $VERSION = 75;
24 1 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 1 @ISA = ('Math::NumSeq');
26  
27 1 ▶use Math::NumSeq::Primes;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 1 ▶use Math::NumSeq::Primorials;
Subroutine BEGIN: called CC=1 SCAR=0.0
29  
30 # uncomment this to run the ### lines
31 #use Smart::Comments;
32  
33 # use constant name => Math::NumSeq::__('Almost Primes');
34 1 ▶use constant description => Math::NumSeq::__('Products of a fixed number of primes, default the semi-primes, 4, 6, 9, 10, 14 15, etc with just two prime factors P*Q.');
Subroutine BEGIN: called CC=1 SCAR=0.0
35 1 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
36 1 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 1 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
38  
39 1 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
40 [
41 { name => 'factor_count',
42 display => Math::NumSeq::__('Factor Count'),
43 type => 'integer',
44 default => 2,
45 minimum => 2,
46 width => 2,
47 description => Math::NumSeq::__('How many prime factors to include.'),
48 },
49 { name => 'multiplicity',
50 display => Math::NumSeq::__('Multiplicity'),
51 type => 'enum',
52 choices => ['repeated','distinct'],
53 choices_display => [Math::NumSeq::__('Repeated'),
54 Math::NumSeq::__('Distinct'),
55 ],
56 default => 'repeated',
57 # description => Math::NumSeq::__(''),
58 },
59 1 ];
60  
61 # cf A068318 - sum of the prime factors of the nth semiprime
62 #
63 1 my %oeis_anum
64 = (repeated =>
65 [ undef,
66 'A000040', # 1, just the primes
67 'A001358', # 2 with repeats
68 'A014612', # 3 with repeats
69 'A014613', # 4 with repeats
70 'A014614', # 5 with repeats
71 'A046306', # 6 with repeats
72 'A046308', # 7 with repeats
73 'A046310', # 8 with repeats
74 'A046312', # 9 with repeats
75 'A046314', # 10 with repeats
76 'A069272', # 11 with repeats
77 'A069273', # 12 with repeats
78 'A069274', # 13 with repeats
79 'A069275', # 14 with repeats
80 'A069276', # 15 with repeats
81 'A069277', # 16 with repeats
82 'A069278', # 17 with repeats
83 'A069279', # 18 with repeats
84 'A069280', # 19 with repeats
85 'A069281', # 20 with repeats
86 # OEIS-Other: A000040 factor_count=1
87 # OEIS-Catalogue: A001358
88 # OEIS-Catalogue: A014612 factor_count=3
89 # OEIS-Catalogue: A014613 factor_count=4
90 # OEIS-Catalogue: A014614 factor_count=5
91 # OEIS-Catalogue: A046306 factor_count=6
92 # OEIS-Catalogue: A046308 factor_count=7
93 # OEIS-Catalogue: A046310 factor_count=8
94 # OEIS-Catalogue: A046312 factor_count=9
95 # OEIS-Catalogue: A046314 factor_count=10
96 # OEIS-Catalogue: A069272 factor_count=11
97 # OEIS-Catalogue: A069273 factor_count=12
98 # OEIS-Catalogue: A069274 factor_count=13
99 # OEIS-Catalogue: A069275 factor_count=14
100 # OEIS-Catalogue: A069276 factor_count=15
101 # OEIS-Catalogue: A069277 factor_count=16
102 # OEIS-Catalogue: A069278 factor_count=17
103 # OEIS-Catalogue: A069279 factor_count=18
104 # OEIS-Catalogue: A069280 factor_count=19
105 # OEIS-Catalogue: A069281 factor_count=20
106 ],
107 distinct =>
108 [ undef,
109 'A000040', # 1, just the primes
110 'A006881', # 2 distinct primes
111 'A007304', # 3 distinct primes
112 'A046386', # 4 distinct primes
113 'A046387', # 5 distinct primes
114 'A067885', # 6 distinct primes
115 'A123321', # 7 distinct primes
116 'A123322', # 8 distinct primes
117 'A115343', # 9 distinct primes
118 # OEIS-Other: A000040 multiplicity=distinct factor_count=1
119 # OEIS-Catalogue: A006881 multiplicity=distinct
120 # OEIS-Catalogue: A007304 multiplicity=distinct factor_count=3
121 # OEIS-Catalogue: A046386 multiplicity=distinct factor_count=4
122 # OEIS-Catalogue: A046387 multiplicity=distinct factor_count=5
123 # OEIS-Catalogue: A067885 multiplicity=distinct factor_count=6
124 # OEIS-Catalogue: A123321 multiplicity=distinct factor_count=7
125 # OEIS-Catalogue: A123322 multiplicity=distinct factor_count=8
126 # OEIS-Catalogue: A115343 multiplicity=distinct factor_count=9
127 ],
128 );
129 1 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
130 1 my ($self) = @_;
131 1 return $oeis_anum{$self->{'multiplicity'}}->[$self->{'factor_count'}];
132 }
133  
134 3 ▶sub values_min {
Subroutine values_min: called CC=2 SCAR=7.4
Pod documented
135 3 my ($self) = @_;
136 3 my $factor_count = $self->{'factor_count'};
137 3 ▶ if ($self->{'multiplicity'} eq 'distinct') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'multiplicity'} eq 'distinct') { } 0 3 3
138 0 return Math::NumSeq::Primorials->ith($factor_count);
139 } else {
140 3 return 2 ** $factor_count;
141 }
142 }
143  
144 3 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
145 3 my ($self) = @_;
146 3 $self->{'i'} = $self->i_start;
147 3 $self->{'done'} = 1;
148 3 $self->{'hi'} = 0;
149 3 $self->{'pending'} = [];
150 }
151  
152 122 ▶sub next {
Subroutine next: called CC=17 SCAR=28.8
Pod documented
153 122 my ($self) = @_;
154  
155 122 my $done = $self->{'done'};
156 122 my $pending = $self->{'pending'};
157  
158 122 for (;;) {
159 ### $done
160 124 ▶ if (@$pending) {
Branch: 1 branch
BranchTrueFalseTotal
if (@$pending) 122 2 124
161 ### ret: $self->{'i'}, $pending->[0]
162 return ($self->{'i'}++,
163 122 ($self->{'done'} = shift @$pending));
164 }
165  
166 ### refill pending array ...
167  
168 2 my $factor_count = $self->{'factor_count'};
169 2 my $distinct = ($self->{'multiplicity'} eq 'distinct');
170 ### $factor_count
171 ### $distinct
172  
173 my $hi = $self->{'hi'} = ($self->{'hi'} == 0
174 ? 500 + $self->values_min
175 2 ▶ : $self->{'hi'} * 2);
Branch: 1 branch
BranchTrueFalseTotal
$self->{'hi'} == 0 ? : 2 0 2
176 2 ▶ my $primes_hi
Branch: 1 branch
BranchTrueFalseTotal
$distinct ? : 0 2 2
177 = int ($hi / ($distinct
178 ? Math::NumSeq::Primorials->ith($factor_count-1)
179 : 2 ** ($factor_count-1)));
180 ### $hi
181 ### $primes_hi
182  
183 2 require Math::NumSeq::Primes;
184 2 my @primes = Math::NumSeq::Primes::_primes_list (0, $primes_hi);
185 2 ▶ if (@primes < ($distinct ? $factor_count : 1)) {
Branch: 2 branches
BranchTrueFalseTotal
if (@primes < ($distinct ? $factor_count : 1)) 0 2 2
$distinct ? : 0 2 2
186 ### not enough primes, go bigger ...
187 0 next;
188 }
189 ### primes count: scalar(@primes)
190  
191  
192 # This is an iterative array based descent so as not to hit the "deep
193 # recursion" warnings if factor_count is 100 or more. Though quite how
194 # well such a large count works in practice is another matter. Ought to
195 # break out bignums for 2^100 etc to keep accuracy.
196 #
197 # The @any flags track whether any products were added by the descent.
198 # It allows big chunks of the descent to be pruned back at a low depth
199 # when the products get close to $hi.
200  
201 2 my @prod = (1);
202 2 my @upto = (-1);
203 2 my @any;
204  
205 2 my $depth = 0;
206 2 OUTER: for (;;) {
207 218 my $prod = $prod[$depth];
208 218 ▶ if ($depth >= $factor_count-1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth >= $factor_count - 1) { } 108 110 218
209 ### lowest level: "prod=$prod and ".($upto[$depth]+1)." to $#primes"
210 108 my $prev_len = @$pending;
211 108 foreach my $i ($upto[$depth]+1 .. $#primes) {
212 416 my $new_prod = $prod * $primes[$i];
213 ### $new_prod
214 416 ▶ if ($new_prod > $hi) {
Branch: 1 branch
BranchTrueFalseTotal
if ($new_prod > $hi) 106 310 416
215 106 last;
216 }
217 310 ▶ if ($new_prod > $done) {
Branch: 1 branch
BranchTrueFalseTotal
if ($new_prod > $done) 310 0 310
218 310 push @$pending, $new_prod;
219 }
220 }
221 ### pushed: "was $prev_len count ".(@$pending-$prev_len)." ".((@$pending>$prev_len) && $pending->[$prev_len])." to ".((@$pending>$prev_len) && $pending->[-1])
222 ### pending: @$pending
223  
224 108 ▶ if ($depth > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth > 0) 108 0 108
225 108 ▶ $any[$depth] ||= (@$pending != $prev_len);
Condition66%2/3
$any[$depth] ||= @$pending != $prev_len
l!l&&r!l&&!r
01692
MC/DC50%1/2
$any[$depth] ||= @$pending != $prev_len
$any[$depth] @$pending != $prev_len
Truth table66%2/3
A ||= B
A= $any[$depth]B= @$pending != $prev_len
ABresult
1X1
011
000
226 }
227  
228 } else {
229 ### increment at: "depth=$depth"
230 110 my $upto = ++$upto[$depth];
231 110 ▶ if ($upto <= $#primes) {
Branch: 1 branch
BranchTrueFalseTotal
if ($upto <= $#primes) 108 2 110
232 108 $prod *= $primes[$upto];
233 108 ▶ if ($prod < $hi) {
Branch: 1 branch
BranchTrueFalseTotal
if ($prod < $hi) 108 0 108
234 ### descend to: "upto=".($upto+$distinct)." prod=$prod"
235 108 $depth++;
236 108 $prod[$depth] = $prod;
237 108 $upto[$depth] = $upto + $distinct - 1;
238 108 $any[$depth] = 0;
239 108 next;
240 }
241 }
242 }
243  
244 ### backtrack ...
245 110 for (;;) {
246 110 ▶ if (--$depth < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--$depth < 0) 2 108 110
247 2 last OUTER;
248 }
249 108 ▶ $any[$depth] ||= $any[$depth+1];
Condition66%2/3
$any[$depth] ||= $any[$depth + 1]
l!l&&r!l&&!r
10620
MC/DC0%0/2
$any[$depth] ||= $any[$depth + 1]
$any[$depth] $any[$depth + 1]
Truth table66%2/3
A ||= B
A= $any[$depth]B= $any[$depth + 1]
ABresult
1X1
011
000
250 108 ▶ if ($any[$depth]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($any[$depth]) { } 108 0 108
251 ### continue at this depth ...
252 108 last;
253 } else {
254 ### not any, backtrack further ...
255 }
256 }
257 }
258  
259  
260 # my $descend;
261 # $descend = sub {
262 # my ($prod, $start, $depth) = @_;
263 # ### descend: "$prod $start $depth"
264 # my $any = 0;
265 # if ($depth > 0) {
266 # foreach my $i ($start .. $#primes) {
267 # my $new_prod = $prod * $primes[$i];
268 # if ($new_prod > $hi) {
269 # last;
270 # }
271 # if (! &$descend ($new_prod,
272 # $distinct ? $i+1 : $i,
273 # $depth-1)) {
274 # ### nothing added, break out ...
275 # last;
276 # }
277 # $any = 1;
278 # }
279 # } else {
280 # foreach my $i ($start .. $#primes) {
281 # my $new_prod = $prod * $primes[$i];
282 # if ($new_prod > $hi) {
283 # last;
284 # }
285 # $any = 1;
286 # if ($new_prod > $done) {
287 # push @$pending, $new_prod;
288 # }
289 # }
290 # }
291 # ### $any
292 # return $any;
293 # };
294 # &$descend (1, 0, $factor_count-1);
295  
296  
297 2 @$pending = sort {$a<=>$b} @$pending;
298 }
299 }
300  
301 428 ▶sub pred {
Subroutine pred: called CC=16 SCAR=27.9
Pod documented
302 428 my ($self, $value) = @_;
303 ### AlmostPrimes pred(): $value
304  
305 428 ▶ unless ($value >= 0 && $value <= 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value >= 0 and $value <= 4294967295) 0 428 428
Condition33%1/3
$value >= 0 and $value <= 4294967295
!ll&&!rl&&r
00428
MC/DC0%0/2
$value >= 0 and $value <= 4294967295
$value >= 0 $value <= 4294967295
Truth table33%1/3
A and B
A= $value >= 0B= $value <= 4294967295
ABresult
0X0
100
111
306 0 return undef;
307 }
308 428 ▶ if ($value < 1 || $value != int($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 1 or $value != int $value) 183 245 428
Condition66%2/3
$value < 1 or $value != int $value
l!l&&r!l&&!r
0183245
MC/DC50%1/2
$value < 1 or $value != int $value
$value < 1 $value != int $value
Truth table66%2/3
A or B
A= $value < 1B= $value != int $value
ABresult
1X1
011
000
309 183 return 0;
310 }
311 245 $value = "$value"; # numize Math::BigInt for speed
312  
313 245 my $factor_count = $self->{'factor_count'};
314 245 my $distinct = ($self->{'multiplicity'} eq 'distinct');
315  
316 245 my $seen_count = 0;
317  
318 245 ▶ unless ($value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value % 2) 116 129 245
319 ### even ...
320 116 $value /= 2;
321 116 $seen_count = 1;
322 116 ▶ until ($value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value % 2) 81 105 186
323 81 $value /= 2;
324 81 ▶ if ($seen_count++ > $factor_count || $distinct) {
Branch: 1 branch
BranchTrueFalseTotal
if ($seen_count++ > $factor_count or $distinct) 11 70 81
Condition66%2/3
$seen_count++ > $factor_count or $distinct
l!l&&r!l&&!r
11070
MC/DC50%1/2
$seen_count++ > $factor_count or $distinct
$seen_count++ > $factor_count $distinct
Truth table66%2/3
A or B
A= $seen_count++ > $factor_countB= $distinct
ABresult
1X1
011
000
325 11 return 0;
326 }
327 ### $seen_count
328 }
329 }
330  
331 234 my $limit = int(sqrt($value));
332 234 ▶ for (my $p = 3; $p <= $limit; $p += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p <= $limit) 494 223 717
333 494 ▶ unless ($value % $p) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value % $p) 129 365 494
334 129 $value /= $p;
335 129 ▶ if ($seen_count++ > $factor_count) {
Branch: 1 branch
BranchTrueFalseTotal
if ($seen_count++ > $factor_count) 3 126 129
336 3 return 0;
337 }
338 126 ▶ until ($value % $p) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value % $p) 42 118 160
339 42 $value /= $p;
340 42 ▶ if ($seen_count++ > $factor_count || $distinct) {
Branch: 1 branch
BranchTrueFalseTotal
if ($seen_count++ > $factor_count or $distinct) 8 34 42
Condition66%2/3
$seen_count++ > $factor_count or $distinct
l!l&&r!l&&!r
8034
MC/DC50%1/2
$seen_count++ > $factor_count or $distinct
$seen_count++ > $factor_count $distinct
Truth table66%2/3
A or B
A= $seen_count++ > $factor_countB= $distinct
ABresult
1X1
011
000
341 8 return 0;
342 }
343 }
344  
345 118 $limit = int(sqrt($value)); # new smaller limit
346 }
347 }
348 223 ▶ if ($value != 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != 1) 203 20 223
349 203 $seen_count++;
350 }
351 ### final seen_count: $seen_count
352 223 return ($seen_count == $factor_count);
353 }
354  
355 1 1;
356 __END__
« NumSeq/TotientSteps.pm ↑ Summary NumSeq/KlarnerRado.pm »