NumSeq/Totient.pm

filter: Statementstmt 88.1% 89 / 101 Branchbran 68.7% 22 / 32 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 94.7% 18 / 19 Podpod 100% 2 / 2 totaltotal 85.0% 131 / 154 CC 19 SCAR 16.8
CC
19
Cov
83%
_pred_f
11.1
pred
6.9
_totient
6.1
CRAP 5.4
« NumSeq/DedekindPsiSteps.pm ↑ Summary NumSeq/PowerFlip.pm »
1 # Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 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 package Math::NumSeq::Totient;
20 3 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
21 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
22 3 ▶use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099
Subroutine BEGIN: called CC=1 SCAR=0.0
23 3 ▶use Math::Factor::XS 'factors';
Subroutine BEGIN: called CC=1 SCAR=0.0
24  
25 3 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
26 3 $VERSION = 75;
27  
28 3 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
29 3 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 3 @ISA = ('Math::NumSeq::Base::IterateIth',
31 'Math::NumSeq');
32 3 *_is_infinite = \&Math::NumSeq::_is_infinite;
33  
34 3 ▶use Math::NumSeq::PrimeFactorCount;;
Subroutine BEGIN: called CC=1 SCAR=0.0
35 3 *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors;
36  
37 # uncomment this to run the ### lines
38 #use Smart::Comments;
39  
40  
41 # use constant name => Math::NumSeq::__('Totient');
42 3 ▶use constant description => Math::NumSeq::__('Euler totient function, the count of how many numbers coprime to N.');
Subroutine BEGIN: called CC=1 SCAR=0.0
43 3 ▶use constant characteristic_count => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 3 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 3 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 3 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47 3 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
48  
49 #------------------------------------------------------------------------------
50 # cf A007617 non-totients, all odds, plus evens per A005277
51 # A005277 even non-totients, n s.t. n==phi(something) no solution
52 # A058980 non-totients 0mod4
53 # A056595 - sum non-square divisors
54 # A007614 totients ascending, with multiplicity
55  
56 # Dressler (1970) N(x) = num phi(n)<=x, then N(x)/x -> A
57 # A = zeta(2)*zeta(3)/zeta(6) = product primes 1+1/(p*(p-1))
58 #
59 # 2p is a non-totient if 2p+1 composite (p not an S-G prime)
60 # 4p is a non-totient iff 2p+1 and 4p+1 both composite
61 # if n non-totient and 2n+1 composite then 2n also non-totient
62 #
63 3 ▶use constant oeis_anum => 'A000010';
Subroutine BEGIN: called CC=1 SCAR=0.0
64  
65 0 ▶sub ith {
Subroutine ith: not called CC=1 SCAR=6.9
Pod documented
66 0 my ($self, $i) = @_;
67 0 return _totient($i);
68 }
69 1135 ▶sub _totient {
Subroutine _totient: called CC=6 SCAR=18.0
70 1135 my ($n) = @_;
71 ### _totient(): $n
72  
73 1135 ▶ if (_is_infinite($n)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($n)) 0 1135 1135
74 0 return $n;
75 }
76 1135 ▶ if ($n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 0) 98 1037 1135
77 98 return 0;
78 }
79 1037 my ($good, @primes) = _prime_factors($n);
80 1037 ▶ return undef unless $good;
Branch: 1 branch
BranchTrueFalseTotal
unless $good 0 1037 1037
81  
82 1037 my $prev = 0;
83 1037 my $ret = 1;
84 1037 foreach my $p (@primes) {
85 1467 ▶ if ($p == $prev) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p == $prev) { } 362 1105 1467
86 362 $ret *= $p;
87 } else {
88 1105 $ret *= $p - 1;
89 1105 $prev = $p;
90 }
91 }
92 1037 return $ret;
93 }
94  
95 # totient(x)=p^a.q^b.r^c=n
96 # seek a prime w for x with w-1 dividing in n
97 # combinations of the primes of n to make w-1
98 #
99 # factor 2*f of n, arising from prime 2*f+1
100 #
101 # 8 arises from totient(15=3*5) = (3-1)*(5-1)=2*4
102 # 484=2*2*11*11 2*11=23 prime
103 #
104 2 ▶sub pred {
Subroutine pred: called CC=5 SCAR=19.3
Pod documented
105 2 my ($self, $value) = @_;
106 ### Totient pred(): $value
107  
108 2 ▶ if ($value <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 1) 0 2 2
109 0 return ($value == 1); # $value==0 no, $value==1 yes
110 }
111 2 ▶ if ($value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value % 2) 0 2 2
112 ### no because odd ...
113 0 return 0;
114 }
115 2 ▶ unless ($value <= 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value <= 4294967295) 0 2 2
116 0 return undef;
117 }
118 2 $value = "$value"; # numize any Math::BigInt for factors()
119 2 ▶ if (_pred_f($value,$value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_pred_f($value, $value)) 2 0 2
120 2 return 1;
121 }
122 0 return 0;
123 }
124 16 ▶sub _pred_f {
Subroutine _pred_f: called CC=10 SCAR=24.1
125 16 my ($n, $prev_factor) = @_;
126 ### _pred_f(): "n=$n prev=$prev_factor"
127  
128 16 ▶ if ($n & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n & 1) 6 10 16
129 ### no odd ...
130 6 return 0;
131 }
132  
133 10 $n >>= 1;
134 ### halved: $n
135 10 ▶ if ($n == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == 1) 0 10 10
136 0 return 1; # totient(3)=2 occurs
137 }
138  
139 10 foreach my $f (1, factors($n)) {
140 ### at: "n=$n f=$f"
141 14 ▶ if ($f >= $prev_factor) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f >= $prev_factor) 6 8 14
142 ### f too big, chop search ...
143 6 return 0;
144 }
145 8 my $p = 2*$f+1;
146 ### $p
147  
148 8 my $r = $n / $f;
149 ### divide out: "f=$f to r=$r"
150  
151 8 ▶ unless (is_prime($p)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (is_prime($p)) 0 8 8
152 ### no, not prime ...
153 0 next;
154 }
155  
156 8 for (;;) {
157 14 ▶ if (_pred_f ($r, $f)) { # recurse
Branch: 1 branch
BranchTrueFalseTotal
if (_pred_f($r, $f)) 2 12 14
158 2 return 1;
159 }
160 12 ▶ if ($r % $p) {
Branch: 1 branch
BranchTrueFalseTotal
if ($r % $p) 4 8 12
161 4 last;
162 }
163 8 ▶ if ($r == $p) {
Branch: 1 branch
BranchTrueFalseTotal
if ($r == $p) 2 6 8
164 2 return 1;
165 }
166 6 $r /= $p;
167 ### divide out prime: "p=$p to r=$r"
168 }
169 }
170  
171 ### whole: "n=$n p=".(2*$n+1)
172 0 ▶ if ($n >= $prev_factor) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n >= $prev_factor) 0 0 0
173 ### f too big, chop search ...
174 0 return 0;
175 }
176 0 return is_prime(2*$n+1);
177 }
178  
179  
180 # sub _totient {
181 # my ($x) = @_;
182 # my $count = (($x >= 1) # y=1 always
183 # + ($x > 2 && ($x&1)) # y=2 if $x odd
184 # + ($x > 3 && ($x % 3) != 0) # y=3
185 # + ($x > 4 && ($x&1)) # y=4 if $x odd
186 # );
187 # for (my $y = 5; $y < $x; $y++) {
188 # $count += _coprime($x,$y);
189 # }
190 # return $count;
191 # }
192 # sub _coprime { # for x<y
193 # my ($x, $y) = @_;
194 # #### _coprime(): "$x,$y"
195 # if ($y > $x) {
196 # return 0;
197 # }
198 # for (;;) {
199 # if ($y <= 1) {
200 # return ($y == 1);
201 # }
202 # ($x,$y) = ($y, $x % $y);
203 # }
204 # }
205  
206  
207 3 1;
208 __END__
« NumSeq/DedekindPsiSteps.pm ↑ Summary NumSeq/PowerFlip.pm »