NumSeq/MobiusFunction.pm

filter: Statementstmt 98.6% 73 / 74 Branchbran 90.0% 18 / 20 Conditioncond 72.7% 8 / 11 MC/DCmcdc 16.6% 1 / 6 Subroutinesub 100% 16 / 16 Podpod 100% 2 / 2 totaltotal 91.4% 118 / 129 CC 15 SCAR 18.7
CC
15
Cov
94%
ith
13.2
pred
3.0
BEGIN
1.0
CRAP 6.5
« NumSeq/RadixWithoutDigit.pm ↑ Summary NumSeq/DeletablePrimes.pm »
1 # Copyright 2010, 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::MobiusFunction;
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 2 ▶use List::Util 'min','max';
Subroutine BEGIN: called CC=1 SCAR=0.0
22  
23 2 ▶use vars '$VERSION','@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
24 2 $VERSION = 75;
25  
26 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 2 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 2 @ISA = ('Math::NumSeq::Base::IterateIth',
29 'Math::NumSeq');
30 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
31  
32 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
33 2 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
34  
35 # uncomment this to run the ### lines
36 #use Smart::Comments;
37  
38  
39 # use constant name => Math::NumSeq::__('Mobius Function');
40 2 ▶use constant description => Math::NumSeq::__('The Mobius function, being 1 for an even number of prime factors, -1 for an odd number, or 0 if any repeated factors (ie. not square-free).');
Subroutine BEGIN: called CC=1 SCAR=0.0
41 2 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
42 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 2 ▶use constant values_min => -1;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 2 ▶use constant values_max => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 2 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
46  
47 #------------------------------------------------------------------------------
48 # cf A030059 the -1 positions, being odd number of distinct primes
49 # A030229 the 1 positions, being even number of distinct primes
50 # A013929 the 0 positions, being square factor, ie. the non-square-frees
51 # A005117 square free numbers, mobius -1 or +1
52 #
53 2 ▶use constant oeis_anum => 'A008683'; # mobius -1,0,1 starting i=1
Subroutine BEGIN: called CC=1 SCAR=0.0
54  
55  
56 #------------------------------------------------------------------------------
57  
58 114 ▶sub ith {
Subroutine ith: called CC=13 SCAR=25.8
Pod documented
59 114 my ($self, $i) = @_;
60 ### MobiusFunction ith(): $i
61  
62 114 my $ret = 0;
63  
64 114 ▶ if (_is_infinite($i) || $i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i) or $i < 0) 3 111 114
Condition66%2/3
_is_infinite($i) or $i < 0
l!l&&r!l&&!r
03111
MC/DC50%1/2
_is_infinite($i) or $i < 0
_is_infinite($i) $i < 0
Truth table66%2/3
A or B
A= _is_infinite($i)B= $i < 0
ABresult
1X1
011
000
65 3 return undef;
66 }
67  
68 111 ▶ if (($i % 2) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % 2 == 0) 58 53 111
69 58 $i /= 2;
70 58 ▶ if (($i % 2) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % 2 == 0) 25 33 58
71 25 return 0; # square factor
72 }
73 33 $ret = 1;
74 }
75  
76 86 ▶ if ($i <= 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= 4294967295) 86 0 86
77 86 $i = "$i"; # numize Math::BigInt for speed
78 }
79  
80 86 my $sqrt = int(sqrt($i));
81 86 ▶ my $limit = min ($sqrt,
Condition50%1/2
_blog2_estimate($i) || 1
l!l
086
MC/DC0%0/1
_blog2_estimate($i) || 1
_blog2_estimate($i)
Truth table50%1/2
A
A= _blog2_estimate($i)
Aresult
11
00
82 10_000 / (_blog2_estimate($i) || 1));
83 ### $sqrt
84 ### $limit
85  
86 86 ▶ for (my $p = 3; $p <= $limit; $p += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p <= $limit) 34 78 112
87 34 ▶ if (($i % $p) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % $p == 0) 14 20 34
88 14 $i /= $p;
89 14 ▶ if (($i % $p) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % $p == 0) 8 6 14
90 ### square factor, zero ...
91 8 return 0;
92 }
93 6 $ret ^= 1;
94 6 $sqrt = int(sqrt($i)); # new smaller limit
95 6 $limit = min ($sqrt, $limit);
96 ### factor: "$p new ret $ret new limit $limit"
97 }
98 }
99 78 ▶ if ($sqrt > $limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sqrt > $limit) 0 78 78
100 ### not all factors found up to limit ...
101 # ENHANCE-ME: prime_factors() here if <2^32
102 0 return undef;
103 }
104 78 ▶ if ($i != 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i != 1) 62 16 78
105 62 $ret ^= 1;
106 }
107 78 ▶ return ($ret ? -1 : 1);
Branch: 1 branch
BranchTrueFalseTotal
$ret ? : 47 31 78
108 }
109  
110 6 ▶sub pred {
Subroutine pred: called CC=3 SCAR=11.0
Pod documented
111 6 my ($self, $value) = @_;
112 6 ▶ return ($value == 0 || $value == 1 || $value == -1);
Condition83%5/6
$value == 0 || $value == 1 || $value == -1
l!l&&r!l&&!r
330
$value == 0 or $value == 1
l!l&&r!l&&!r
123
MC/DC0%0/3
$value == 0 || $value == 1 || $value == -1
$value == 0 $value == 1 $value == -1
Truth table75%3/4
A or B || C
A= $value == 0B= $value == 1C= $value == -1
ABCresult
1XX1
01X1
0011
0000
113 }
114  
115 2 1;
116 __END__
« NumSeq/RadixWithoutDigit.pm ↑ Summary NumSeq/DeletablePrimes.pm »