NumSeq/RepdigitRadix.pm

filter: Statementstmt 97.3% 110 / 113 Branchbran 88.6% 39 / 44 Conditioncond 62.5% 5 / 8 MC/DCmcdc 40.0% 2 / 5 Subroutinesub 100% 18 / 18 Podpod 100% 6 / 6 totaltotal 92.7% 180 / 194 CC 28 SCAR 22.1
CC
28
Cov
93%
ith
18.4
next
7.0
_nth_root_floor
3.1
CRAP 9.1
« NumSeq/SqrtDigits.pm ↑ Summary NumSeq/HafermanCarpet.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  
19 # ENHANCE-ME: ith() might be a touch faster than next() now, perhaps
20 # something sieve/flag in next()
21  
22  
23 package Math::NumSeq::RepdigitRadix;
24 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
28 2 $VERSION = 75;
29 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 2 @ISA = ('Math::NumSeq');
31 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
32  
33 2 ▶use Math::NumSeq::NumAronson;
Subroutine BEGIN: called CC=1 SCAR=0.0
34 2 *_round_down_pow = \&Math::NumSeq::NumAronson::_round_down_pow;
35  
36 2 ▶use Math::Factor::XS 0.40 'factors'; # version 0.40 for factors() on BigInt
Subroutine BEGIN: called CC=1 SCAR=0.0
37  
38 # uncomment this to run the ### lines
39 #use Smart::Comments;
40  
41  
42 # use constant name => Math::NumSeq::__('Repdigit Radix');
43 2 ▶use constant description => Math::NumSeq::__('First radix in which i is a repdigit (at most base=i-1 since otherwise "11" would always give i).');
Subroutine BEGIN: called CC=1 SCAR=0.0
44 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 2 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47 2 ▶use constant characteristic_value_is_radix => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
48 1 ▶sub values_min {
Subroutine values_min: called CC=2 SCAR=7.2
Pod documented
49 1 my ($self) = @_;
50 1 ▶ return ($self->i_start >= 3 ? 2 : 0);
Branch: 1 branch
BranchTrueFalseTotal
$self->i_start >= 3 ? : 0 1 1
51 }
52 15 ▶sub i_start {
Subroutine i_start: called CC=2 SCAR=7.2
Pod documented
53 15 my ($self) = @_;
54 15 ▶ return $self->{'i_start'} || 0;
Condition50%1/2
$self->{'i_start'} || 0
l!l
015
MC/DC0%0/1
$self->{'i_start'} || 0
$self->{'i_start'}
Truth table50%1/2
A
A= $self->{'i_start'}
Aresult
11
00
55 }
56  
57 # smallest base in which n is a repdigit, starting n=3
58 1 ▶sub oeis_anum { 'A059711' }
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
59 # OEIS-Catalogue: A059711 i_start=3
60  
61  
62 # d * (b^3 + b^2 + b + 1) = i
63 # b^3 + b^2 + b + 1 = i/d
64 # (b+1)^3 = b^3 + 3b^2 + 3b + 1
65 #
66 # (b-1) * (b^3 + b^2 + b + 1) = b^4 - 1
67 #
68 # 8888 base 9 = 6560
69 # 1111 base 10
70  
71 # b^2 + b + 1 = k
72 # (b+0.5)^2 + .75 = k
73 # (b+0.5)^2 = (k-0.75)
74 # b = sqrt(k-0.75)-0.5;
75  
76 6 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
77 6 my ($self) = @_;
78 6 $self->{'i'} = $self->i_start;
79 6 $self->{'ones'} = [ undef, undef, 7 ];
80 6 $self->{'digits'} = [ undef, undef, 1 ];
81 ### rewind to: $self
82 }
83  
84 # (r+1)^2 + (r+1) + 1
85 # = r^2 + 2r + 1 + r +1 + 1
86 # = r^2 + 3r + 3
87 # = (r + 3)*r + 3
88  
89 # 0 1 2
90 2 my @small = (2, 0, 0);
91  
92 519 ▶sub next {
Subroutine next: called CC=7 SCAR=19.5
Pod documented
93 519 my ($self) = @_;
94 ### RepdigitRadix next(): $self->{'i'}
95  
96 519 my $i = $self->{'i'}++;
97 519 my $ones = $self->{'ones'};
98 519 my $digits = $self->{'digits'};
99  
100 519 ▶ if ($i < 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 3) 9 510 519
101 9 return ($i, $small[$i]);
102 }
103  
104 510 for (my $radix = 2; ; $radix++) {
105 ### $radix
106 ### ones: $ones->[$radix]
107 ### digit: $digits->[$radix]
108  
109 35515 my $one;
110 35515 ▶ if ($radix > $#$ones) {
Branch: 1 branch
BranchTrueFalseTotal
if ($radix > $ones->$#*) { } 505 35010 35515
111 ### maybe extend array: $radix
112 505 $one = $radix + 1; # or three digits ... ($radix + 1) *
113 505 ▶ unless ($one <= $i) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($one <= $i) 3 502 505
114 ### not repdigit of 3 digits in any radix, take as 2 digits ...
115 3 return ($i, $i-1);
116 }
117 502 $ones->[$radix] = $one;
118 502 $digits->[$radix] = 1;
119  
120 } else {
121 35010 $one = $ones->[$radix];
122 }
123  
124 35512 my $repdigit = $one * $digits->[$radix];
125 35512 ▶ while ($repdigit < $i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($repdigit < $i) 1634 35512 37146
126 1634 my $digit = ++$digits->[$radix];
127 1634 ▶ if ($digit >= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit >= $radix) 36 1598 1634
128 36 $digit = $digits->[$radix] = 1;
129 36 $one = $ones->[$radix] = ($one * $radix + 1);
130 }
131 1634 $repdigit = $one * $digit;
132 }
133 ### consider repdigit: $repdigit
134 35512 ▶ if ($repdigit == $i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($repdigit == $i) 507 35005 35512
135 ### found radix: $radix
136 507 return ($i, $radix);
137 }
138 }
139 }
140  
141 # d=r-1
142 # v = d*(r^(len-1)+...+1)
143 # = r^len-1
144 # dlimit = nthroot(v+1, len)
145 #
146 # q=v/d
147 # q=r^(len-1)+...+1
148 # q > r^(len-1) # when len>2
149 # r < nthroot(q, len-1)
150  
151 533 ▶sub ith {
Subroutine ith: called CC=18 SCAR=29.1
Pod documented
152 533 my ($self, $i) = @_;
153 ### RepdigitRadix ith(): $i
154 533 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 3 530 533
155 3 $i = abs($i);
156 }
157 533 ▶ if ($i < 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 3) 14 519 533
158 14 return $small[$i];
159 }
160 519 ▶ if ($i > 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > 4294967295) 0 519 519
161 0 return undef;
162 }
163 519 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 519 519
164 0 return $i; # nan
165 }
166  
167 519 my @factors = reverse (1, factors($i));
168 ### @factors
169  
170 519 my ($pow, $len) = _round_down_pow ($i, 2);
171 519 $len++;
172 ### initial len: $len
173  
174 519 my $r_found;
175 519 ▶ for ( ; $len >= 3; $len--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($len >= 3) 3035 519 3554
176 3035 ▶ my $d_limit = (defined $r_found ? $r_found-1 : _nth_root_floor($i+1,$len));
Branch: 1 branch
BranchTrueFalseTotal
defined $r_found ? : 33 3002 3035
177 ### $len
178 ### $d_limit
179  
180 3035 foreach my $d (grep {$_<=$d_limit} @factors) { # descending order
181 ### try d: $d
182  
183 # if ($d > $d_limit) {
184 # ### stop for d > d_limit ...
185 # last;
186 # }
187  
188 4963 my $q = $i / $d;
189 4963 my $r = _nth_root_floor($q,$len-1);
190 ### $q
191 ### $r
192 ### ones: ($r**$len - 1) / ($r-1)
193  
194 4963 ▶ if (defined $r_found && $r >= $r_found) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $r_found and $r >= $r_found) 70 4893 4963
Condition66%2/3
defined $r_found and $r >= $r_found
!ll&&!rl&&r
4893070
MC/DC50%1/2
defined $r_found and $r >= $r_found
defined $r_found $r >= $r_found
Truth table66%2/3
A and B
A= defined $r_foundB= $r >= $r_found
ABresult
0X0
100
111
195 ### stop at r >= r_found ...
196 70 last;
197 }
198  
199 4893 ▶ if ($r <= $d) {
Branch: 1 branch
BranchTrueFalseTotal
if ($r <= $d) 858 4035 4893
200 ### r smaller than d ...
201 # since d>=1 this also excludes r<2
202 858 next;
203 }
204  
205 4035 ▶ if ($q == ($r**$len - 1) / ($r-1)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($q == ($r ** $len - 1) / ($r - 1)) 71 3964 4035
206 71 $r_found = $r;
207 }
208 }
209 }
210  
211 519 ▶ my $d_limit = (defined $r_found ? $r_found-1 : int(sqrt($i+1)));
Branch: 1 branch
BranchTrueFalseTotal
defined $r_found ? : 71 448 519
212 519 foreach my $d (grep {$_<=$d_limit} @factors) { # descending order
213 ### try d: $d
214  
215 # v = d*(r+1)
216 # v/d = r+1
217 # r = v/d - 1
218 #
219 908 my $r = $i/$d - 1;
220 ### $r
221  
222 908 ▶ if (defined $r_found && $r >= $r_found) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $r_found and $r >= $r_found) 417 491 908
Condition66%2/3
defined $r_found and $r >= $r_found
!ll&&!rl&&r
4910417
MC/DC50%1/2
defined $r_found and $r >= $r_found
defined $r_found $r >= $r_found
Truth table66%2/3
A and B
A= defined $r_foundB= $r >= $r_found
ABresult
0X0
100
111
223 ### stop at r >= r_found ...
224 417 last;
225 }
226  
227 491 ▶ if ($r <= $d) {
Branch: 1 branch
BranchTrueFalseTotal
if ($r <= $d) 43 448 491
228 ### r smaller than d ...
229 # since d>=1 this also excludes r<2
230 43 next;
231 }
232  
233 448 $r_found = $r;
234 }
235  
236 519 ▶ return (defined $r_found ? $r_found : $i-1);
Branch: 1 branch
BranchTrueFalseTotal
defined $r_found ? : 519 0 519
237  
238  
239 # for (my $radix = 2; ; $radix++) {
240 # ### $radix
241 #
242 # my $one = $radix + 1; # ... or 3 digits 111 ($radix + 1) *
243 # unless ($one <= $i) {
244 # ### stop at ones too big not a 3-digit repdigit: $one
245 # return $i-1;
246 # }
247 # ### $one
248 #
249 # do {
250 # if ($one == $i) {
251 # return $radix;
252 # }
253 # foreach my $digit (2 .. $radix-1) {
254 # ### $digit
255 # if ((my $repdigit = $digit * $one) <= $i) {
256 # if ($repdigit == $i) {
257 # return $radix;
258 # }
259 # }
260 # }
261 # } while (($one = $one * $radix + 1) <= $i);
262 # }
263 }
264  
265 # value = root^power
266 # log(value) = power*log(root)
267 # log(root) = log(value)/power
268 # root = exp(log(value)/power)
269 #
270 7965 ▶sub _nth_root_floor {
Subroutine _nth_root_floor: called CC=3 SCAR=11.2
271 7965 my ($value, $power) = @_;
272 7965 my $root = int (exp (log($value)/$power));
273 7965 ▶ if ($root**$power > $value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($root ** $power > $value) 0 7965 7965
274 0 return $root-1;
275 }
276 7965 ▶ if (($root+1)**$power < $value) {
Branch: 1 branch
BranchTrueFalseTotal
if (($root + 1) ** $power < $value) 11 7954 7965
277 11 return $root+1;
278 }
279 7954 return $root;
280 }
281  
282 # R^2+R+1
283 # R=65 "111"=4291
284 #
285 # Does every radix occur? Is it certain that at least one repdigit in base
286 # R is not a repdigit in anything smaller?
287 #
288 # sub pred {
289 # my ($self, $value) = @_;
290 # return ($value == int($value)
291 # && ($value == 0 || $value >= 2));
292 # }
293  
294 2 1;
295 __END__
« NumSeq/SqrtDigits.pm ↑ Summary NumSeq/HafermanCarpet.pm »