NumSeq/PrimeFactorCount.pm

filter: Statementstmt 79.4% 93 / 117 Branchbran 67.6% 46 / 68 Conditioncond 58.8% 10 / 17 MC/DCmcdc 54.5% 6 / 11 Subroutinesub 95.8% 23 / 24 Podpod 100% 5 / 5 totaltotal 75.6% 183 / 242 CC 41 SCAR 31.2
CC
41
Cov
74%
_prime_factors
83.4
ith
18.0
description
9.6
CRAP 22.7
« NumSeq/ReverseAddSteps.pm ↑ Summary NumSeq/TotientPerfect.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  
19 # values_type => 'mod2'
20  
21  
22 package Math::NumSeq::PrimeFactorCount;
23 8 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
24 8 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 8 ▶use List::Util 'min', 'max';
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 8 ▶use vars '$VERSION','@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
28 8 $VERSION = 75;
29  
30 8 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
31 8 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
32 8 @ISA = ('Math::NumSeq::Base::IterateIth',
33 'Math::NumSeq');
34 8 *_is_infinite = \&Math::NumSeq::_is_infinite;
35  
36 8 ▶use Math::Prime::XS 'is_prime';
Subroutine BEGIN: called CC=1 SCAR=0.0
37 8 ▶use Math::Factor::XS 'prime_factors';
Subroutine BEGIN: called CC=1 SCAR=0.0
38  
39 8 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 8 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
41  
42 # uncomment this to run the ### lines
43 #use Smart::Comments;
44  
45  
46 # cf. Untouchables, not sum of proper divisors of any other integer
47 # p*q sum S=1+p+q
48 # so sums up to hi need factorize to (hi^2)/4
49 #
50  
51 8 ▶use constant values_min => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
52 8 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
53  
54 0 ▶sub values_max {
Subroutine values_max: not called CC=2 SCAR=17.9
Pod documented
55 0 my ($self) = @_;
56 0 ▶ if ($self->{'values_type'} eq 'mod2') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'values_type'} eq 'mod2') { } 0 0 0
57 0 return 1;
58 } else {
59 0 return undef;
60 }
61 }
62 8 ▶use constant characteristic_count => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
63 8 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
64 8 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
65  
66 8 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
67 [
68 { name => 'prime_type',
69 display => Math::NumSeq::__('Prime Type'),
70 type => 'enum',
71 default => 'all',
72 choices => ['all','odd','4k+1','4k+3',
73 'twin','SG','safe'],
74 choices_display => [Math::NumSeq::__('All'),
75 Math::NumSeq::__('Odd'),
76 # TRANSLATORS: "4k+1" meaning numbers 1,5,9,13 etc, probably no need to translate except into another script if Latin letter "k" won't be recognised
77 Math::NumSeq::__('4k+1'),
78 Math::NumSeq::__('4k+3'),
79 Math::NumSeq::__('Twin'),
80 Math::NumSeq::__('SG'),
81 Math::NumSeq::__('Safe'),
82 ],
83 description => Math::NumSeq::__('The type of primes to count.
84 twin=P where P+2 or P-2 also prime.
85 SG=Sophie Germain P where 2P+1 also prime.
86 safe=P where (P-1)/2 also prime (the "other" of the SGs).'),
87 },
88 { name => 'multiplicity',
89 display => Math::NumSeq::__('Multiplicity'),
90 type => 'enum',
91 default => 'repeated',
92 choices => ['repeated','distinct'],
93 choices_display => [Math::NumSeq::__('Repeated'),
94 Math::NumSeq::__('Distinct'),
95 ],
96 description => Math::NumSeq::__('Whether to include repeated prime factors, or only distinct prime factors.'),
97 },
98  
99 # not documented yet
100 { name => 'values_type',
101 share_key => 'values_type_cm2',
102 display => Math::NumSeq::__('Values Type'),
103 type => 'enum',
104 default => 'count',
105 choices => ['count','mod2'],
106 choices_display => [Math::NumSeq::__('Count'),
107 Math::NumSeq::__('Mod2'),
108 ],
109 # description => Math::NumSeq::__('...'),
110 },
111 8 ];
112  
113 12 ▶sub description {
Subroutine description: called CC=9 SCAR=22.7
Pod documented
114 12 my ($self) = @_;
115 12 ▶ if (ref $self) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $self) { } 6 6 12
116 return ($self->{'multiplicity'} eq 'repeated'
117 ? Math::NumSeq::__('Count of prime factors, including repetitions.')
118 : Math::NumSeq::__('Count of distinct prime factors.'))
119 . ($self->{'prime_type'} eq 'odd' ? "\nOdd primes only."
120 : $self->{'prime_type'} eq '4k+1' ? "\nPrimes of form 4k+1 only."
121 : $self->{'prime_type'} eq '4k+3' ? "\nPrimes of form 4k+3 only."
122 : $self->{'prime_type'} eq 'twin' ? "\nTwin primes only."
123 : $self->{'prime_type'} eq 'SG' ? "\nSophie Germain primes only (2P+1 also prime)."
124 6 ▶ : $self->{'prime_type'} eq 'SG' ? "\nSafe primes only ((P-1)/2 also prime)."
Branch: 7 branches
BranchTrueFalseTotal
$self->{'multiplicity'} eq 'repeated' ? : 4 2 6
$self->{'prime_type'} eq 'odd' ? : 0 6 6
$self->{'prime_type'} eq '4k+1' ? : 0 6 6
$self->{'prime_type'} eq '4k+3' ? : 0 6 6
$self->{'prime_type'} eq 'twin' ? : 2 4 6
$self->{'prime_type'} eq 'SG' ? : 1 3 4
$self->{'prime_type'} eq 'SG' ? : 0 3 3
125 : "");
126 } else {
127 # class method
128 6 return Math::NumSeq::__('Count of prime factors.');
129 }
130 }
131  
132 #------------------------------------------------------------------------------
133 #
134 # count 1-bits in exponents of primes
135 # A000028,A000379 seqs
136 # A133008 characteristic
137 # A131181,A026416 same, but 1 in "B" class
138 # A064547 count 1 bits in prime exponents
139 # A066724 so a(i)*a(j) not in seq
140 # A026477 so a(i)*a(j)*a(k) not in seq
141 # A050376 prime^(2^k)
142 # A084400 smallest not dividing product a(1)..a(n-1), is prime^(2^k)
143  
144 8 my %oeis_anum = (repeated => { all => 'A001222',
145 odd => 'A087436',
146 '4k+1' => 'A083025',
147 '4k+3' => 'A065339',
148 },
149 distinct => { all => 'A001221',
150 odd => 'A005087',
151 '4k+1' => 'A005089',
152 '4k+3' => 'A005091',
153 twin => 'A284203',
154 SG => 'A156542',
155 },
156 );
157 # OEIS-Catalogue: A001222
158 # OEIS-Catalogue: A087436 prime_type=odd
159 # OEIS-Catalogue: A083025 prime_type=4k+1
160 # OEIS-Catalogue: A065339 prime_type=4k+3
161  
162 # OEIS-Catalogue: A001221 multiplicity=distinct
163 # OEIS-Catalogue: A005087 multiplicity=distinct prime_type=odd
164 # OEIS-Catalogue: A005089 multiplicity=distinct prime_type=4k+1
165 # OEIS-Catalogue: A005091 multiplicity=distinct prime_type=4k+3
166 # OEIS-Catalogue: A284203 multiplicity=distinct prime_type=twin
167 # OEIS-Catalogue: A156542 multiplicity=distinct prime_type=SG
168  
169 6 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
170 6 my ($self) = @_;
171 6 return $oeis_anum{$self->{'multiplicity'}}->{$self->{'prime_type'}};
172 }
173  
174 #------------------------------------------------------------------------------
175  
176 # prime_factors() is about 5x faster
177 #
178 2014 ▶sub ith {
Subroutine ith: called CC=18 SCAR=28.9
Pod documented
179 2014 my ($self, $i) = @_;
180 2014 $i = abs($i);
181  
182 2014 my ($good, @primes) = _prime_factors($i);
183 2014 ▶ return undef unless $good;
Branch: 1 branch
BranchTrueFalseTotal
unless $good 0 2014 2014
184  
185 2014 my $multiplicity = ($self->{'multiplicity'} ne 'distinct');
186 2014 my $prime_type = $self->{'prime_type'};
187 2014 my $count = 0;
188  
189 2014 ▶ while (@primes) {
Branch: 1 branch
BranchTrueFalseTotal
if (@primes) 2858 2014 4872
190 2858 my $p = shift @primes;
191 2858 my $c = 1;
192 2858 ▶ while (@primes && $primes[0] == $p) {
Branch: 1 branch
BranchTrueFalseTotal
if (@primes and $primes[0] == $p) 1003 2858 3861
Condition100%3/3
@primes and $primes[0] == $p
!ll&&!rl&&r
19589001003
MC/DC100%2/2
@primes and $primes[0] == $p
@primes $primes[0] == $p
Truth table100%3/3
A and B
A= @primesB= $primes[0] == $p
ABresult
0X0
100
111
193 1003 shift @primes;
194 1003 $c += $multiplicity;
195 }
196  
197 2858 ▶ if ($prime_type eq 'odd') {
Branch: 6 branches
BranchTrueFalseTotal
if ($prime_type eq 'odd') { } 86 2772 2858
elsif ($prime_type eq '4k+1') { } 86 2686 2772
elsif ($prime_type eq '4k+3') { } 86 2600 2686
elsif ($prime_type eq 'twin') { } 1212 1388 2600
elsif ($prime_type eq 'SG') { } 567 821 1388
elsif ($prime_type eq 'safe') { } 567 254 821
198 86 ▶ next unless $p & 1;
Branch: 1 branch
BranchTrueFalseTotal
unless $p & 1 30 56 86
199 } elsif ($prime_type eq '4k+1') {
200 86 ▶ next unless ($p&3)==1;
Branch: 1 branch
BranchTrueFalseTotal
unless ($p & 3) == 1 66 20 86
201 } elsif ($prime_type eq '4k+3') {
202 86 ▶ next unless ($p&3)==3;
Branch: 1 branch
BranchTrueFalseTotal
unless ($p & 3) == 3 50 36 86
203 } elsif ($prime_type eq 'twin') {
204 1212 ▶ next unless _is_twin_prime($p);
Branch: 1 branch
BranchTrueFalseTotal
unless _is_twin_prime($p) 453 759 1212
205 } elsif ($prime_type eq 'SG') {
206 567 ▶ next unless _is_SG_prime($p);
Branch: 1 branch
BranchTrueFalseTotal
unless _is_SG_prime($p) 121 446 567
207 } elsif ($prime_type eq 'safe') {
208 567 ▶ next unless _is_safe_prime($p);
Branch: 1 branch
BranchTrueFalseTotal
unless _is_safe_prime($p) 371 196 567
209  
210 # } elsif ($prime_type eq 'twin_first') {
211 # next unless is_prime($p+2);
212 # } elsif ($prime_type eq 'twin_second') {
213 # next unless is_prime($p-2);
214 }
215 1767 $count += $c;
216 }
217  
218 2014 ▶ if ($self->{'values_type'} eq 'mod2') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"values_type"} eq "mod2") 0 2014 2014
219 0 $count %= 2;
220 }
221 2014 return $count;
222 }
223  
224 # Return ($good, $prime,$prime,$prime,...).
225 # $good is true if a full factorization is found.
226 # $good is false if cannot factorize because $n is too big or infinite.
227 #
228 # If $n==0 or $n==1 then there are no prime factors and the return is
229 # $good=1 and an empty list of primes.
230 #
231 6191 ▶sub _prime_factors {
Subroutine _prime_factors: called CC=12 SCAR=44.2
232 6191 my ($n) = @_;
233 ### _prime_factors(): $n
234  
235 6191 ▶ unless ($n >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($n >= 0) 9 6182 6191
236 9 return 0;
237 }
238 6182 ▶ if (_is_infinite($n)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($n)) 0 6182 6182
239 0 return 0;
240 }
241  
242 6182 ▶ if ($n <= 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n <= 4294967295) 6182 0 6182
243 6182 return (1, prime_factors($n));
244 }
245  
246 0 my @ret;
247 0 ▶ until ($n % 2) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($n % 2) 0 0 0
248 ### div2: $n
249 0 $n /= 2;
250 0 push @ret, 2;
251 }
252  
253 # Stop at when prime $p reaches $limit and when no prime factor has been
254 # found for the last 20 attempted $p. Stopping only after a run of no
255 # factors found allows big primorials 2*3*5*7*13*... to be divided out.
256 # If the divisions are making progress reducing $i then continue.
257 #
258 # Would like $p and $gap to count primes, not just odd numbers. Perhaps
259 # a table of small primes. The first gap of 36 odds between primes
260 # occurs at prime=31469. cf A000230 smallest prime p for gap 2n.
261  
262 0 ▶ my $limit = 10_000 / (_blog2_estimate($n) || 1);
Condition0%0/2
_blog2_estimate($n) || 1
l!l
00
MC/DC0%0/1
_blog2_estimate($n) || 1
_blog2_estimate($n)
Truth table0%0/2
A
A= _blog2_estimate($n)
Aresult
11
00
263 0 my $gap = 0;
264 0 ▶ for (my $p = 3; $gap < 36 || $p <= $limit ; $p += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($gap < 36 or $p <= $limit) 0 0 0
Condition0%0/3
$gap < 36 or $p <= $limit
l!l&&r!l&&!r
000
MC/DC0%0/2
$gap < 36 or $p <= $limit
$gap < 36 $p <= $limit
Truth table0%0/3
A or B
A= $gap < 36B= $p <= $limit
ABresult
1X1
011
000
265 0 ▶ if ($n % $p) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n % $p) { } 0 0 0
266 0 $gap++;
267 } else {
268 0 ▶ do {
Branch: 1 branch
BranchTrueFalseTotal
$n % $p or do { do { $n /= $p; push @ret, $p } } 0 0 0
269 ### prime: $p
270 0 $n /= $p;
271 0 push @ret, $p;
272 } until ($n % $p);
273  
274 0 ▶ if ($n <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n <= 1) 0 0 0
275 ### all factors found ...
276 0 return (1, @ret);
277 }
278 0 ▶ if ($n < 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n < 4294967295) 0 0 0
279 ### remaining factors by XS ...
280 0 return (1, @ret, prime_factors($n));
281 }
282 0 $gap = 0;
283 }
284 }
285 0 return 0; # factors too big
286 }
287  
288 1212 ▶sub _is_twin_prime {
Subroutine _is_twin_prime: called CC=2 SCAR=6.9
289 1212 my ($n) = @_;
290 ### assert: $n >= 2
291 ### assert: is_prime($n)
292 1212 ▶ return (is_prime($n+2) || is_prime($n-2));
Condition100%3/3
is_prime($n + 2) || is_prime($n - 2)
l!l&&r!l&&!r
561198453
MC/DC100%2/2
is_prime($n + 2) || is_prime($n - 2)
is_prime($n + 2) is_prime($n - 2)
Truth table100%3/3
A || B
A= is_prime($n + 2)B= is_prime($n - 2)
ABresult
1X1
011
000
293 }
294 567 ▶sub _is_SG_prime {
Subroutine _is_SG_prime: called CC=1 SCAR=0.0
295 567 my ($n) = @_;
296 ### assert: is_prime($n)
297 567 return is_prime(2*$n+1);
298 }
299 567 ▶sub _is_safe_prime {
Subroutine _is_safe_prime: called CC=2 SCAR=6.9
300 567 my ($n) = @_;
301 ### assert: is_prime($n)
302 567 ▶ return (($n&1) && is_prime(($n-1)/2));
Condition100%3/3
$n & 1 && is_prime(($n - 1) / 2)
!ll&&!rl&&r
188183196
MC/DC100%2/2
$n & 1 && is_prime(($n - 1) / 2)
$n & 1 is_prime(($n - 1) / 2)
Truth table100%3/3
A && B
A= $n & 1B= is_prime(($n - 1) / 2)
ABresult
0X0
100
111
303 }
304  
305 110 ▶sub pred {
Subroutine pred: called CC=2 SCAR=8.1
Pod documented
306 110 my ($self, $value) = @_;
307 110 ▶ return ($value >= 0 && $value == int($value));
Condition33%1/3
$value >= 0 && $value == int $value
!ll&&!rl&&r
00110
MC/DC0%0/2
$value >= 0 && $value == int $value
$value >= 0 $value == int $value
Truth table33%1/3
A && B
A= $value >= 0B= $value == int $value
ABresult
0X0
100
111
308 }
309  
310 8 1;
311 __END__
« NumSeq/ReverseAddSteps.pm ↑ Summary NumSeq/TotientPerfect.pm »