NumSeq/ProthNumbers.pm

filter: Statementstmt 96.0% 96 / 100 Branchbran 91.6% 22 / 24 Conditioncond 66.6% 4 / 6 MC/DCmcdc 33.3% 1 / 3 Subroutinesub 100% 17 / 17 Podpod 100% 6 / 6 totaltotal 93.5% 146 / 156 CC 14 SCAR 11.5
CC
14
Cov
94%
pred
7.0
seek_to_i
4.0
next
3.2
CRAP 3.2
« NumSeq/PowerPart.pm ↑ Summary NumSeq/Beastly.pm »
1 # Copyright 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::ProthNumbers;
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  
22 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 2 $VERSION = 75;
24  
25 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 2 @ISA = ('Math::NumSeq');
27 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
28  
29 2 ▶use Math::NumSeq::NumAronson;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 2 *_round_down_pow = \&Math::NumSeq::NumAronson::_round_down_pow;
31  
32 # uncomment this to run the ### lines
33 # use Smart::Comments;
34  
35  
36 # use constant name => Math::NumSeq::__('Proth Numbers');
37 2 ▶use constant description => Math::NumSeq::__('Proth numbers k*2^n+1 for odd k and k < 2^n.');
Subroutine BEGIN: called CC=1 SCAR=0.0
38 2 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 2 ▶use constant values_min => 3;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 2 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
42  
43 # cf A157892 - value of k
44 # A157893 - value of n
45 # A080076 - Proth primes
46 # A134876 - how many Proth primes for given n
47 #
48 # A002253 3*2^n+1 is prime
49 # A002254 5*2^n+1
50 # A032353 7*2^n+1
51 # A002256 9*2^n+1
52 #
53 # A086341 - 2^x+/-1 is sqrt of Proth squares
54 #
55 2 ▶use constant oeis_anum => 'A080075';
Subroutine BEGIN: called CC=1 SCAR=0.0
56  
57  
58 # $uv_limit is the biggest power 4**k which fits in a UV
59 #
60 2 my $uv_limit = do {
61 2 my $max = ~0;
62  
63 # limit <= floor(max/4) means 4*limit <= max is still good
64 2 my $limit = 4;
65 2 ▶ while ($limit <= ($max >> 2)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($limit <= $max >> 2) 60 2 62
66 60 $limit <<= 2;
67 }
68  
69 ### ProthNumbers UV limit ...
70 ### $limit
71 ### limit: sprintf('%#X',$limit)
72  
73 $limit
74 2 };
75  
76 7 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
77 7 my ($self) = @_;
78 7 $self->{'value'} = 1;
79 7 $self->{'inc'} = 2;
80 7 $self->{'limit'} = 4;
81 7 $self->{'i'} = $self->i_start;
82 }
83 1531 ▶sub next {
Subroutine next: called CC=3 SCAR=11.7
Pod documented
84 1531 my ($self) = @_;
85 ### ProthNumbers next(): sprintf('value=%b inc=%b limit=%b', $self->{'value'}, $self->{'inc'}, $self->{'limit'})
86  
87 1531 my $value = ($self->{'value'} += $self->{'inc'});
88 1531 ▶ if ($value >= $self->{'limit'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value >= $self->{"limit"}) 78 1453 1531
89 ### bigger 2^n now ...
90 78 ▶ if ($self->{'limit'} == $uv_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"limit"} == $uv_limit) 0 78 78
91 ### go to BigInt
92 0 $self->{'value'} = Math::NumSeq::_to_bigint($self->{'value'});
93 0 $self->{'inc'} = Math::NumSeq::_to_bigint($self->{'inc'});
94 0 $self->{'limit'} = Math::NumSeq::_to_bigint($self->{'limit'});
95 }
96 78 $self->{'inc'} *= 2;
97 78 $self->{'limit'} *= 4;
98 }
99 1531 return ($self->{'i'}++, $value);
100 }
101  
102 # seek value at i-1, inc and limit ready to make next value
103 #
104 # i i value inc limit next value
105 # 1 1 1 10 100 11
106 # 2 10 11 10 100 101
107 # 3 11 101 100 10000 1001
108 # 4 100 1001 100 10000 1101
109 # 5 101 1101 100 10000 10001
110 # 6 110 10001 1000 1000000 11001
111 # 7 111 11001 1000 1000000 100001
112 # 8 1000 100001 1000 1000000 101001
113 # 9 1001 101001 1000 1000000 110001
114 # 10 1010 110001 1000 1000000 111001
115 # 11 1011 111001 1000 1000000 1000001
116 # 12 1100 1000001 10000 100000000 1010001
117 # 13 1101 1010001 10000 100000000 1100001
118 # 14 1110 1100001 10000 100000000 1110001
119 # 15 1111 1110001 10000 100000000 10000001
120 # 16 10000 10000001 10000 100000000 10010001
121 #
122 575 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=4 SCAR=13.9
Pod documented
123 575 my ($self, $i) = @_;
124 575 $self->{'i'} = $i;
125  
126 575 my ($pow) = _round_down_pow($i, 2); # i = 1zxxx
127 575 $i -= $pow; # without high bit, so i=zxxx
128  
129 # $zpow is the z bit position, or 1 if $i==1
130 575 ▶ my $zpow = ($pow >= 2 ? $pow/2 : 0);
Branch: 1 branch
BranchTrueFalseTotal
$pow >= 2 ? : 573 2 575
131  
132 575 ▶ if ($i >= $zpow) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $zpow) { } 278 297 575
133 # z=1 so return value=1xxx 0 0001, extra low 0-bit
134 278 $pow *= 2;
135 } else {
136 # z=0 so return value=1xxx 0001, turn on 1-bit in i
137 297 $i += $zpow; # i=0xxx becomes i=1xxx
138 }
139  
140 575 ▶ if ($pow*$pow >= $uv_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pow * $pow >= $uv_limit) 0 575 575
141 0 $pow = Math::NumSeq::_to_bigint($pow);
142 }
143 575 $self->{'value'} = $pow*$i + 1;
144 575 $self->{'inc'} = $pow;
145 575 $self->{'limit'} = $pow*$pow;
146 }
147  
148 162 ▶sub ith {
Subroutine ith: called CC=2 SCAR=6.9
Pod documented
149 162 my ($self, $i) = @_;
150 ### ProthNumbers ith(): $i
151  
152 162 $i += 1;
153 162 my ($pow) = _round_down_pow($i, 2); # i = 1zxxx
154 162 $i -= $pow; # without high bit, so i=zxxx
155  
156 162 my $zpow = $pow/2;
157 162 ▶ if ($i >= $zpow) { # test z bit
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $zpow) { } 67 95 162
158 # z=1 so return value=1xxx 0 0001, extra low 0-bit
159 67 $pow *= 2;
160 } else {
161 # z=1 so return value=1xxx 0001, turn on 1-bit in i
162 95 $i += $zpow; # i=0xxx becomes i=1xxx
163 }
164 162 return $i*$pow + 1;
165 }
166  
167 2043 ▶sub pred {
Subroutine pred: called CC=7 SCAR=19.5
Pod documented
168 2043 my ($self, $value) = @_;
169 ### ProthNumbers pred(): $value
170 {
171 2043 my $int = int($value);
172 2043 ▶ if ($value != $int) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value != $int) 990 1053 2043
173 1053 $value = $int;
174 }
175 1053 ▶ unless ($value >= 3
Branch: 1 branch
BranchTrueFalseTotal
unless ($value >= 3 and $value % 2 and not _is_infinite($value)) 500 553 1053
Condition66%4/6
$value >= 3 and $value % 2 and not _is_infinite($value)
!ll&&!rl&&r
5000553
$value >= 3 and $value % 2
!ll&&!rl&&r
0499554
MC/DC33%1/3
$value >= 3 and $value % 2 and not _is_infinite($value)
$value >= 3 $value % 2 not _is_infinite($value)
Truth table50%2/4
A and B and not(C)
A= $value >= 3B= $value % 2C= not _is_infinite($value)
ABCresult
0XX0
10X0
1100
1111
176 && ($value % 2)
177 && ! _is_infinite($value)) {
178 500 return 0;
179 }
180  
181 # ENHANCE-ME: maybe BigInt as_bin() and string match position of lowest 1
182 # ENHANCE-ME: maybe (v^(v-1))+1 for lowest 1, ask if v < m*m
183 #
184 553 my $pow = ($value*0) + 2; # inherit bignum 2
185 553 for (;;) {
186 ### at: "$value $pow"
187 1200 $value = int($value/2);
188 1200 ▶ if ($value < $pow) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < $pow) 103 1097 1200
189 103 return 1;
190 }
191 1097 ▶ if ($value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value % 2) 450 647 1097
192 450 return ($value < $pow);
193 }
194 647 $pow *= 2;
195 }
196 }
197  
198 # use 41/29 ~= sqrt(2) in case $value is a Math::BigInt, since can't
199 # multiply BigInt*float
200 #
201 62 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=2 SCAR=6.9
Pod documented
202 62 my ($self, $value) = @_;
203 62 ▶ if ($value < 0) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 6 56 62
204 56 my $est = int(sqrt(int($value)) * 41 / 29);
205 }
206  
207 2 1;
208 __END__
« NumSeq/PowerPart.pm ↑ Summary NumSeq/Beastly.pm »