NumSeq/PythagoreanHypots.pm

filter: Statementstmt 97.8% 89 / 91 Branchbran 92.8% 26 / 28 Conditioncond 88.8% 8 / 9 MC/DCmcdc 80.0% 4 / 5 Subroutinesub 100% 17 / 17 Podpod 100% 4 / 4 totaltotal 96.1% 148 / 154 CC 19 SCAR 21.0
CC
19
Cov
96%
pred
16.2
_hypots_block
3.0
next
2.0
CRAP 8.2
« NumSeq/LemoineCount.pm ↑ Summary NumSeq/OEIS/Catalogue/Plugin/FractionDigits.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::PythagoreanHypots;
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  
25 1 ▶use Math::NumSeq 7; # v.7 for _is_infinite()
Subroutine BEGIN: called CC=1 SCAR=0.0
26 1 @ISA = ('Math::NumSeq');
27 1 *_is_infinite = \&Math::NumSeq::_is_infinite;
28  
29 1 ▶use Math::NumSeq::Primes;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 1 ▶use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099
Subroutine BEGIN: called CC=1 SCAR=0.0
31  
32 # uncomment this to run the ### lines
33 #use Smart::Comments;
34  
35  
36 # use constant name => Math::NumSeq::__('Pyathagorean Hypotenuses');
37 1 ▶use constant description => Math::NumSeq::__('The hypotenuses of Pythagorean triples, ie. integers C for which there\'s some A>=1,B>=1 satisfying A^2+B^2=C^2. Primitive hypotenuses are where A,B have no common factor.');
Subroutine BEGIN: called CC=1 SCAR=0.0
38 1 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 1 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 1 ▶use constant values_min => 5;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 1 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
42  
43 1 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
44 [ {
45 name => 'pythagorean_type',
46 type => 'enum',
47 default => 'all',
48 choices => ['all','primitive'],
49 choices_display => [Math::NumSeq::__('All'),
50 Math::NumSeq::__('Primitive'),
51 ],
52 },
53 1 ];
54  
55 #------------------------------------------------------------------------------
56  
57 # cf A002144 - primes 4n+1, the primitive elements of hypots x!=y
58 # -1 is a quadratic residue ...
59 # A002365 - the "y" of prime "c" ??
60 # A002366 - the "x" of prime "c" ??
61 # A046083 - the "a" smaller number, ordered by "c"
62 # A046084 - the "b" second number, ordered by "c"
63 #
64 # A008846 - primitives, x,y no common factor
65 # A004613 - all prime factors are 4n+1, is 1 then primitive hypots
66 #
67 # A009000 - hypots with repetitions
68 # A009012 - "b" second number, ordered by "b", with repetitions
69 #
70 1 my %oeis_anum = (all => 'A009003', # distinct a!=b and a,b>0
71 primitive => 'A008846',
72 );
73 # OEIS-Catalogue: A009003
74 # OEIS-Catalogue: A008846 pythagorean_type=primitive
75 2 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
76 2 my ($self) = @_;
77 2 return $oeis_anum{$self->{'pythagorean_type'}};
78 }
79  
80 #------------------------------------------------------------------------------
81  
82 6 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
83 6 my ($self) = @_;
84 6 $self->{'array'} = [];
85 6 $self->{'i'} = $self->i_start;
86 6 $self->{'hi'} = 1;
87 }
88  
89 24 ▶sub next {
Subroutine next: called CC=2 SCAR=6.9
Pod documented
90 24 my ($self) = @_;
91 24 my $array = $self->{'array'};
92 24 for (;;) {
93 28 ▶ if (defined (my $value = shift @$array)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $value = shift @$array)) 24 4 28
94 24 return ($self->{'i'}++,
95 $value);
96 }
97 4 my $lo = $self->{'hi'} + 1;
98 4 $self->{'hi'} = my $hi = $lo + 1000;
99 4 @$array = _hypots_block ($self, $lo, $hi);
100 }
101 }
102  
103 4 ▶sub _hypots_block {
Subroutine _hypots_block: called CC=3 SCAR=11.0
104 4 my ($self, $lo, $hi) = @_;
105  
106 4 ▶ if ($self->{'pythagorean_type'} eq 'primitive') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'pythagorean_type'} eq 'primitive') { } 2 2 4
107 2 return grep {$self->pred($_)} $lo .. $hi;
108  
109 } else {
110 2 my %hypots;
111 2 foreach my $p (grep {($_ & 3)==1}
112 Math::NumSeq::Primes::_primes_list(2, $hi)) {
113 160 @hypots{map {$_*$p}
114 (int(($lo+$p-1)/$p) .. int($hi/$p))
115 } = ();
116 }
117 2 return sort {$a<=>$b} keys %hypots;
118 }
119 }
120  
121 2110 ▶sub pred {
Subroutine pred: called CC=16 SCAR=27.8
Pod documented
122 2110 my ($self, $value) = @_;
123 ### pred: $value
124  
125 2110 ▶ if ($value < 5
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 5 or _is_infinite($value) or $value != int $value) 53 2057 2110
Condition83%5/6
$value < 5 or _is_infinite($value) or $value != int $value
l!l&&r!l&&!r
6472057
$value < 5 or _is_infinite($value)
l!l&&r!l&&!r
602104
MC/DC66%2/3
$value < 5 or _is_infinite($value) or $value != int $value
$value < 5 _is_infinite($value) $value != int $value
Truth table75%3/4
A or B or C
A= $value < 5B= _is_infinite($value)C= $value != int $value
ABCresult
1XX1
01X1
0011
0000
126 || _is_infinite($value)
127 || $value != int($value)) {
128 53 return 0;
129 }
130  
131 2057 my $pythagorean_type = $self->{'pythagorean_type'};
132 ### $pythagorean_type
133  
134 2057 ▶ unless ($value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value % 2) 1024 1033 2057
135 ### even ...
136 1024 ▶ if ($pythagorean_type ne 'all') {
Branch: 1 branch
BranchTrueFalseTotal
if ($pythagorean_type ne "all") 1014 10 1024
137 ### primitive and prime never even ...
138 1014 return 0;
139 }
140 10 ▶ do {
Branch: 1 branch
BranchTrueFalseTotal
$value % 2 or do { do { $value /= 2 } } 10 8 18
141 18 $value /= 2;
142 } until ($value % 2);
143 }
144 1043 ▶ unless ($value <= 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value <= 4294967295) 0 1043 1043
145 0 return undef;
146 }
147 1043 $value = "$value"; # numize Math::BigInt for speed
148  
149 1043 my $limit = int(sqrt($value));
150  
151 1043 ▶ for (my $p = 3; $p <= $limit; $p += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p <= $limit) 4940 542 5482
152 4940 ▶ if (($value % $p) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value % $p == 0) 698 4242 4940
153 698 ▶ if (($p & 3) == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (($p & 3) == 1) { } 193 505 698
154 ### found 4k+1 prime: $p
155 193 ▶ if ($pythagorean_type eq 'all') {
Branch: 1 branch
BranchTrueFalseTotal
if ($pythagorean_type eq "all") 0 193 193
156 0 return 1;
157 }
158 } else {
159 ### found 4k+3 prime: $p
160 505 ▶ if ($pythagorean_type eq 'primitive') {
Branch: 1 branch
BranchTrueFalseTotal
if ($pythagorean_type eq "primitive") 501 4 505
161 501 return 0;
162 }
163 }
164  
165 197 ▶ do {
Branch: 1 branch
BranchTrueFalseTotal
$value % $p == 0 and do { do { $value /= $p } } 46 197 243
166 243 $value /= $p;
167 } while (($value % $p) == 0);
168  
169 197 $limit = int(sqrt($value)); # new smaller limit
170 ### divide out prime: "$p new limit $limit"
171 }
172 }
173  
174 # $value now 1 or prime
175 542 ▶ if ($pythagorean_type eq 'primitive') {
Branch: 1 branch
BranchTrueFalseTotal
if ($pythagorean_type eq 'primitive') { } 520 22 542
176 # all, check this isn't a 4k+3 prime
177 520 return ($value % 4) != 3;
178 } else {
179 # all, last chance to see a 4k+1 prime
180 22 ▶ return ($value > 1
Condition100%3/3
$value > 1 && $value % 4 == 1
!ll&&!rl&&r
4612
MC/DC100%2/2
$value > 1 && $value % 4 == 1
$value > 1 $value % 4 == 1
Truth table100%3/3
A && B
A= $value > 1B= $value % 4 == 1
ABresult
0X0
100
111
181 && ($value % 4) == 1);
182 }
183 }
184  
185 1 1;
186 __END__
« NumSeq/LemoineCount.pm ↑ Summary NumSeq/OEIS/Catalogue/Plugin/FractionDigits.pm »