| 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
| |||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||
| 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
Condition83%5/6
$value < 5 or _is_infinite($value) or $value != int $value
$value < 5 or _is_infinite($value)
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
| |||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||
| 135 | ### even ... | ||||||||||||||||||||||||||||||||||||||||||
| 136 | 1024 | ▶ | if ($pythagorean_type ne 'all') { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 137 | ### primitive and prime never even ... | ||||||||||||||||||||||||||||||||||||||||||
| 138 | 1014 | return 0; | |||||||||||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||||||||||
| 140 | 10 | ▶ | do { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 141 | 18 | $value /= 2; | |||||||||||||||||||||||||||||||||||||||||
| 142 | } until ($value % 2); | ||||||||||||||||||||||||||||||||||||||||||
| 143 | } | ||||||||||||||||||||||||||||||||||||||||||
| 144 | 1043 | ▶ | unless ($value <= 0xFFFF_FFFF) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||
| 152 | 4940 | ▶ | if (($value % $p) == 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 153 | 698 | ▶ | if (($p & 3) == 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 154 | ### found 4k+1 prime: $p | ||||||||||||||||||||||||||||||||||||||||||
| 155 | 193 | ▶ | if ($pythagorean_type eq 'all') { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 156 | 0 | return 1; | |||||||||||||||||||||||||||||||||||||||||
| 157 | } | ||||||||||||||||||||||||||||||||||||||||||
| 158 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 159 | ### found 4k+3 prime: $p | ||||||||||||||||||||||||||||||||||||||||||
| 160 | 505 | ▶ | if ($pythagorean_type eq 'primitive') { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 161 | 501 | return 0; | |||||||||||||||||||||||||||||||||||||||||
| 162 | } | ||||||||||||||||||||||||||||||||||||||||||
| 163 | } | ||||||||||||||||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||||||||||||||||
| 165 | 197 | ▶ | do { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||
| 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
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
| |||||||||||||||||||||||||||||||||||||||||||
| 181 | && ($value % 4) == 1); | ||||||||||||||||||||||||||||||||||||||||||
| 182 | } | ||||||||||||||||||||||||||||||||||||||||||
| 183 | } | ||||||||||||||||||||||||||||||||||||||||||
| 184 | |||||||||||||||||||||||||||||||||||||||||||
| 185 | 1 | 1; | |||||||||||||||||||||||||||||||||||||||||
| 186 | __END__ | ||||||||||||||||||||||||||||||||||||||||||