NumSeq/RadixWithoutDigit.pm

filter: Statementstmt 95.5% 107 / 112 Branchbran 78.5% 22 / 28 Conditioncond 58.3% 7 / 12 MC/DCmcdc 20.0% 1 / 5 Subroutinesub 100% 14 / 14 Podpod 100% 3 / 3 totaltotal 88.5% 154 / 174 CC 19 SCAR 18.7
CC
19
Cov
89%
ith
11.0
pred
9.3
oeis_anum
2.0
CRAP 6.5
« NumSeq/Runs.pm ↑ Summary NumSeq/MobiusFunction.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::RadixWithoutDigit;
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;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 1 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 1 @ISA = ('Math::NumSeq::Base::IterateIth',
28 'Math::NumSeq');
29 1 *_is_infinite = \&Math::NumSeq::_is_infinite;
30  
31 # uncomment this to run the ### lines
32 # use Smart::Comments;
33  
34 # use constant name => Math::NumSeq::__('Without chosen digit');
35 1 ▶use constant description => Math::NumSeq::__('Integers which don\'t have a given digit when written out in a radix.');
Subroutine BEGIN: called CC=1 SCAR=0.0
36 1 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 1 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
38 1 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39  
40 1 ▶use Math::NumSeq::Base::Digits;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 1 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
42 [ Math::NumSeq::Base::Digits->parameter_info_list(),
43 {
44 name => 'digit',
45 type => 'integer',
46 display => Math::NumSeq::__('Digit'),
47 default => -1,
48 minimum => -1,
49 width => 2,
50 description => Math::NumSeq::__('Digit to exclude. Default -1 means the highest digit, ie. radix-1.'),
51 },
52 1 ];
53  
54 #------------------------------------------------------------------------------
55 # cf A011531 - numbers with a 1 digit
56 # A011532 ... A011539 - numbers with a 2 to 9 digit
57 #
58  
59 1 my @oeis_anum;
60  
61 # Not quite A000225 = 2^n-1 is base 2 without 0, but includes a(0)=0 as
62 # 2^0-1 = 0 whereas RadixWithoutDigit doesn't include value=0.
63 # A000225 is generated by Math::NumSeq::Repdigits anyway.
64  
65 1 $oeis_anum[1]->[3]->[0] = 'A032924'; # base 3 no 0 OFFSET=1
66 1 $oeis_anum[1]->[3]->[1] = 'A005823'; # base 3 no 1 OFFSET=1
67 1 $oeis_anum[1]->[3]->[2] = 'A005836'; # base 3 no 2 OFFSET=1
68 # OEIS-Catalogue: A032924 radix=3 digit=0 # base 3 no 0
69 # OEIS-Catalogue: A005823 radix=3 digit=1 # base 3 no 1
70 # OEIS-Catalogue: A005836 radix=3 digit=2 # base 3 no 2
71  
72 1 $oeis_anum[1]->[4]->[0] = 'A023705'; # base 4 no 0 OFFSET=1
73 1 $oeis_anum[1]->[4]->[1] = 'A023709'; # base 4 no 1 OFFSET=1
74 1 $oeis_anum[1]->[4]->[2] = 'A023713'; # base 4 no 2 OFFSET=1
75 1 $oeis_anum[0]->[4]->[3] = 'A023717'; # base 4 no 3 OFFSET=0
76 # OEIS-Catalogue: A023705 radix=4 digit=0 # base 4 no 0
77 # OEIS-Catalogue: A023709 radix=4 digit=1 # base 4 no 1
78 # OEIS-Catalogue: A023713 radix=4 digit=2 # base 4 no 2
79 # OEIS-Catalogue: A023717 radix=4 digit=3 i_start=0 # base 4 no 3
80  
81 1 $oeis_anum[1]->[5]->[0] = 'A023721'; # base 5 no 0 OFFSET=1
82 1 $oeis_anum[1]->[5]->[1] = 'A023725'; # base 5 no 1 OFFSET=1
83 1 $oeis_anum[1]->[5]->[2] = 'A023729'; # base 5 no 2 OFFSET=1
84 1 $oeis_anum[1]->[5]->[3] = 'A023733'; # base 5 no 3 OFFSET=1
85 1 $oeis_anum[1]->[5]->[4] = 'A023737'; # base 5 no 4 OFFSET=1
86 # OEIS-Catalogue: A023721 radix=5 digit=0 # base 5 no 0
87 # OEIS-Catalogue: A023725 radix=5 digit=1 # base 5 no 1
88 # OEIS-Catalogue: A023729 radix=5 digit=2 # base 5 no 2
89 # OEIS-Catalogue: A023733 radix=5 digit=3 # base 5 no 3
90 # OEIS-Catalogue: A023737 radix=5 digit=4 # base 5 no 4
91  
92 # cf A037465 radix=6 digit=5 i_start=1 # base 6 no 5, starting i=1
93  
94 1 $oeis_anum[1]->[7]->[6] = 'A020657'; # "no 7-term arithmetic progression" OFFSET=1
95 # OEIS-Catalogue: A020657 radix=7 digit=6
96  
97 # starting OFFSET=1 value=1
98 # $oeis_anum[1]->[8]->[7] = 'A037474'; # base 7 written out in octal
99 # # OEIS-Catalogue: A037474 radix=8 digit=7 i_start=1
100  
101 # starting OFFSET=1 value=1
102 # $oeis_anum[1]->[9]->[8] = 'A037477'; # base 8 written out in base 9
103 # # OEIS-Catalogue: A037477 radix=9 digit=8 i_start=1
104  
105 1 $oeis_anum[1]->[10]->[0] = 'A052382'; # decimal numbers without 0, OFFSET=1
106 1 $oeis_anum[1]->[10]->[1] = 'A052383'; # decimal numbers without 1, OFFSET=1 start 0
107 1 $oeis_anum[0]->[10]->[2] = 'A052404'; # decimal numbers without 2, OFFSET=0 start 0
108 1 $oeis_anum[0]->[10]->[3] = 'A052405'; # decimal numbers without 3, OFFSET=0 start 0
109 1 $oeis_anum[1]->[10]->[4] = 'A052406'; # decimal numbers without 4, OFFSET=1 start 0
110 1 $oeis_anum[0]->[10]->[5] = 'A052413'; # OFFSET=0 start 0
111 1 $oeis_anum[0]->[10]->[6] = 'A052414'; # OFFSET=0
112 1 $oeis_anum[0]->[10]->[7] = 'A052419'; # OFFSET=0
113 1 $oeis_anum[0]->[10]->[8] = 'A052421'; # OFFSET=0
114 1 $oeis_anum[0]->[10]->[9] = 'A007095'; # "numbers in base 9" OFFSET=0
115 # OEIS-Catalogue: A052382 radix=10 digit=0
116 # OEIS-Catalogue: A052383 radix=10 digit=1
117 # OEIS-Catalogue: A052404 radix=10 digit=2 i_start=0
118 # OEIS-Catalogue: A052405 radix=10 digit=3 i_start=0
119 # OEIS-Catalogue: A052406 radix=10 digit=4
120 # OEIS-Catalogue: A052413 radix=10 digit=5 i_start=0
121 # OEIS-Catalogue: A052414 radix=10 digit=6 i_start=0
122 # OEIS-Catalogue: A052419 radix=10 digit=7 i_start=0
123 # OEIS-Catalogue: A052421 radix=10 digit=8 i_start=0
124 # OEIS-Catalogue: A007095 radix=10 digit=9 i_start=0 # base 10 no 9
125  
126 8 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=2 SCAR=6.9
Pod documented
127 8 my ($self) = @_;
128 8 my $radix = $self->{'radix'};
129 8 my $digit = $self->{'digit'};
130 8 ▶ if ($digit == -1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit == -1) 1 7 8
131 1 $digit = $radix-1;
132 }
133 8 return $oeis_anum[$self->i_start]->[$radix]->[$digit];
134 }
135  
136  
137 #------------------------------------------------------------------------------
138  
139 # sub rewind {
140 # my ($self) = @_;
141 #
142 # my $radix = $self->{'radix'};
143 # my $digit = $self->{'digit'};
144 # if ($digit == -1) { $digit = $radix - 1; }
145 # $digit = $digit % $radix;
146 #
147 # # my $lo = 0;
148 # # my $n = 0;
149 # # my $i = $self->i_start;
150 # # if ($radix == 2) {
151 # # if ($digit == 1) {
152 # # my $n = 1;
153 # # while ($n < $lo) {
154 # # $i++;
155 # # }
156 # # }
157 # # } else {
158 # # # look at the $radix digits of $n, build $i by treating as $radix-1,
159 # # # increment any $digit to go to the next without that
160 # # my $power = 1;
161 # # while ($n) {
162 # # my $rem = $n % $radix;
163 # # if ($rem >= $digit) {
164 # # $n++;
165 # # } else {
166 # # $i += $rem * $power;
167 # # }
168 # # $n = int ($n / $radix);
169 # # $power *= ($radix-1);
170 # # }
171 # #
172 # # if ($lo < 0) {
173 # # $i = -$i;
174 # # if ($n == $lo) {
175 # # $i--;
176 # # }
177 # # }
178 # # }
179 #
180 # $self->Math::NumSeq::Base::IterateIth::rewind();
181 # }
182  
183 # without 0
184 # 1-9 1-9 ... 1-9 for len digits
185 # each is 9^len many
186 # start at i = 9^1 + ... + 9^(len-1)
187 # = 9^0 + 9^1 + ... + 9^(len-1) - 1
188 # = (9^len - 1)/8 - 1
189 # = (9^len - 1 - 8)/8
190 # = (9^len - 9)/8
191 # 8*i + 1 = 9^level
192 #
193 # add sentinel 1*9^len, so
194 # from = i - (9^len - 9)/8 + 9^len
195 # = i + (- 9^len + 9)/8 + 9^len
196 # = i + (- 9^len + 9 + 8*9^len)/8
197 # = i + (7*9^len + 9) / 8
198 #
199 # and which is then a high digit 2*9^len too big
200 #
201 786 ▶sub ith {
Subroutine ith: called CC=10 SCAR=24.0
Pod documented
202 786 my ($self, $i) = @_;
203 ### RadixWithoutDigit ith(): $i
204  
205 786 $i -= $self->i_start; # i_start=0 or i_start=1 both begin at value=0
206  
207 786 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 786 786
208 0 return $i; # don't loop forever if $i is +infinity
209 }
210  
211 786 my $radix = $self->{'radix'};
212 786 my $digit = $self->{'digit'};
213  
214 786 ▶ if ($radix == 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($radix == 2) 0 786 786
215 0 ▶ if ($digit == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit == 0) { } 0 0 0
216 0 ▶ my $base = ($i < 30 ? 2 : Math::NumSeq::_to_bigint(2));
Branch: 1 branch
BranchTrueFalseTotal
$i < 30 ? : 0 0 0
217 0 return ($base ** ($i+1)) - 1;
218 } else {
219 ### radix 2 without 1 no values ...
220 0 return undef;
221 }
222 }
223  
224 786 ▶ if ($digit == -1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit == -1) 108 678 786
225 108 $digit = $radix-1;
226 }
227  
228 786 my $r1 = $radix - 1;
229 # if ($i < $r1) {
230 # return $i + ($i >= $digit);
231 # }
232 786 my $r2 = $radix - 2;
233 ### $radix
234 ### $r1
235 ### $r2
236  
237 786 my $value = 0;
238 786 ▶ if ($digit == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit == 0) 231 555 786
239 231 my $len = 1;
240 231 ▶ while (($r1**$len - $r1) / $r2 <= $i) {
Branch: 1 branch
BranchTrueFalseTotal
if (($r1 ** $len - $r1) / $r2 <= $i) 476 231 707
241 476 $len++;
242 }
243 231 $len--;
244 ### $len
245 ### base: ($r1**$len - $r1) / $r2
246 ### sentinel: $r1**$len
247 ### adj add: $r1**$len - ($r1**$len - $r1) / $r2
248 ### adj formula: (($r2-1)*$r1**$len + $r1) / $r2
249  
250 ### assert: $i >= ($r1 ** $len - $r1) / $r2
251 ### assert: $i < ($r1 ** $len - $r1) / $r2 + $r1 ** $len
252  
253 231 $i += (($r2-1)*$r1**$len + $r1) / $r2;
254 231 $value = -2 * $radix**$len;
255 ### i remainder: $i
256 ### $value
257  
258 ### assert: $i >= $r1 ** $len
259 ### assert: $i < 2 * $r1 ** $len
260 }
261  
262 # $i converted to radix-1 digits, built back up as radix
263 786 my $power = 1;
264 786 ▶ while ($i > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > 0) 1971 786 2757
265 1971 my $d = $i % $r1;
266 1971 $i = int($i/$r1);
267 ### $value
268 ### $d
269 ### $power
270 1971 ▶ if ($d >= $digit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($d >= $digit) 823 1148 1971
271 823 $d++;
272 ### inc to d: $d
273 }
274 1971 $value += $power * $d;
275 1971 $power *= $radix;
276 }
277 ### stop at i: $i
278 786 $value += $power * $i;
279  
280 ### $value
281 786 return $value;
282  
283 # my $digit = 1;
284 # my $x = $i;
285 # while ($x) {
286 # ### x mod $radix: $x%$radix
287 # if (($x % $radix) == $digit) {
288 # ### add: $digit
289 # $i += $digit;
290 # $x++;
291 # }
292 # $x = int($x/$radix);
293 # $digit *= $radix;
294 # }
295 # return (($self->{'i'} = $i),
296 # 1);
297 }
298  
299 338 ▶sub pred {
Subroutine pred: called CC=9 SCAR=22.3
Pod documented
300 338 my ($self, $value) = @_;
301  
302 338 my $radix = $self->{'radix'};
303 338 my $digit = $self->{'digit'};
304 338 ▶ if ($digit == -1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit == -1) 67 271 338
305 67 $digit = $radix-1;
306 }
307  
308 338 ▶ if ($value < 0
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0 or $digit == 0 and $value == 0 or $value != int $value or _is_infinite($value)) 130 208 338
Condition58%7/12
$value < 0 or $digit == 0 and $value == 0 or $value != int $value or _is_infinite($value)
l!l&&r!l&&!r
1300208
$value < 0 or $digit == 0 and $value == 0 or $value != int $value
l!l&&r!l&&!r
0130208
$value < 0 or $digit == 0 and $value == 0
l!l&&r!l&&!r
00338
$digit == 0 and $value == 0
!ll&&!rl&&r
265730
MC/DC20%1/5
$value < 0 or $digit == 0 and $value == 0 or $value != int $value or _is_infinite($value)
$value < 0 $digit == 0 $value == 0 $value != int $value _is_infinite($value)
Truth table50%4/8
A or B and C or D or E
A= $value < 0B= $digit == 0C= $value == 0D= $value != int $valueE= _is_infinite($value)
ABCDEresult
1XXXX1
011XX1
00X1X1
0101X1
00X011
010011
00X000
010000
309 || ($digit == 0 && $value == 0)
310 || $value != int($value)
311 || _is_infinite($value)) { # don't loop forever if $value is +infinity
312 130 return 0;
313 }
314  
315 208 ▶ while ($value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value) 385 140 525
316 385 my $got_digit = $value % $radix;
317 385 ▶ if ($got_digit == $digit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($got_digit == $digit) 68 317 385
318 68 return 0; # contains $digit, so no
319 }
320 317 $value = int(($value-$got_digit) / $radix); # subtract to stay in UV integer
321 }
322 140 return 1;
323 }
324  
325 1 1;
326 __END__
« NumSeq/Runs.pm ↑ Summary NumSeq/MobiusFunction.pm »