File Coverage

blib/lib/Math/NumSeq/AllDigits.pm
Criterion Covered Total %
statement 74 75 98.6
branch 15 16 93.7
condition n/a
subroutine 12 12 100.0
pod 4 4 100.0
total 105 107 98.1


line stmt bran cond sub pod time code
1             # Copyright 2011, 2012, 2013, 2014 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 .
17              
18             package Math::NumSeq::AllDigits;
19 1     1   1764 use 5.004;
  1         4  
20 1     1   22 use strict;
  1         3  
  1         44  
21              
22 1     1   6 use vars '$VERSION', '@ISA';
  1         2  
  1         98  
23             $VERSION = 72;
24 1     1   7 use Math::NumSeq::Base::Digits;
  1         3  
  1         89  
25             @ISA = ('Math::NumSeq::Base::Digits');
26              
27 1     1   6 use Math::NumSeq 7; # v.7 for _is_infinite()
  1         16  
  1         69  
28             *_is_infinite = \&Math::NumSeq::_is_infinite;
29              
30             # uncomment this to run the ### lines
31             #use Smart::Comments;
32              
33              
34             # use constant name => Math::NumSeq::__('All Integer Digits');
35 1     1   6 use constant description => Math::NumSeq::__('Digits of all the integers.');
  1         3  
  1         5  
36 1     1   6 use constant default_i_start => 0;
  1         2  
  1         145  
37              
38 1         6 use constant parameter_info_array =>
39             [
40             Math::NumSeq::Base::Digits->parameter_info_list, # 'radix'
41             {
42             name => 'order',
43             share_key => 'order_frs',
44             type => 'enum',
45             default => 'forward',
46             choices => ['forward','reverse','sorted'],
47             choices_display => [Math::NumSeq::__('Forward'),
48             Math::NumSeq::__('Reverse'),
49             Math::NumSeq::__('Sorted'),
50             ],
51             description => Math::NumSeq::__('Order for the digits within each integer.'),
52             },
53 1     1   8 ];
  1         3  
54              
55             #------------------------------------------------------------------------------
56              
57             # cf A030303 - base 2 positions of 1s, start 1
58             # A030309 - positions of 0 in reverse
59             # A030310 - positions of 1 in reverse
60             # A030305 - base 2 lengths of runs of 0s
61             # A030306 - base 2 lengths of runs of 1s
62             # A058935 - base 2 concats as bignums
63             #
64             # A054637 - base 3 partial sums digits, start i=0 value=0
65             #
66             # A054632 - decimal partial sums
67             #
68             # A136414 - decimal 2 digits at a time, start i=1 value=1
69             # A193431 - decimal 3 digits at a time
70             # A193492 - decimal 4 digits at a time
71             # A193493 - decimal 5 digits at a time
72             # A019519 - decimal concat odd nums as bignums
73             # A000422 - decimal reverse concats as bignums
74             #
75             # A031324 - decimal digits of Fibonacci numbers
76             # A034004 - decimal digits of triangular numbers
77             # A034005 - decimal digits of Catalan numbers
78             #
79             my %oeis_anum;
80              
81             $oeis_anum{'forward'}->[0]->[2] = 'A030190'; # base 2, start i=0 value=0
82             $oeis_anum{'forward'}->[1]->[2] = 'A030302'; # base 2, start i=1 value=1
83             # OEIS-Catalogue: A030190 radix=2 i_start=0
84             # OEIS-Catalogue: A030302 radix=2 i_start=1
85             $oeis_anum{'reverse'}->[0]->[2] = 'A030308'; # base 2 LE start i=1 value=1
86             # OEIS-Catalogue: A030308 radix=2 order=reverse i_start=0
87              
88             $oeis_anum{'forward'}->[0]->[3] = 'A054635'; # base 3, start i=0 value=0
89             $oeis_anum{'forward'}->[1]->[3] = 'A003137'; # base 3, start i=1 value=1
90             $oeis_anum{'reverse'}->[0]->[3] = 'A030341'; # base 3, start i=0 value=0
91             # OEIS-Catalogue: A054635 radix=3 i_start=0
92             # OEIS-Catalogue: A003137 radix=3 i_start=1
93             # OEIS-Catalogue: A030341 radix=3 order=reverse i_start=0
94              
95             $oeis_anum{'forward'}->[1]->[4] = 'A030373'; # base 4, start i=1 value=1
96             $oeis_anum{'reverse'}->[0]->[4] = 'A030386'; # base 4, start i=0 value=0
97             # OEIS-Catalogue: A030373 radix=4 i_start=1
98             # OEIS-Catalogue: A030386 radix=4 order=reverse i_start=0
99              
100             $oeis_anum{'forward'}->[1]->[5] = 'A031219'; # base 5, start i=1 value=1
101             $oeis_anum{'reverse'}->[0]->[5] = 'A031235'; # base 5, start i=0 value=0
102             # OEIS-Catalogue: A031219 radix=5 i_start=1
103             # OEIS-Catalogue: A031235 radix=5 order=reverse i_start=0
104              
105             $oeis_anum{'reverse'}->[0]->[6] = 'A030567'; # base 6, start i=0 value=0
106             # OEIS-Catalogue: A030567 radix=6 order=reverse i_start=0
107              
108             $oeis_anum{'forward'}->[0]->[7] = 'A030998'; # base 7, start i=0 value=0
109             $oeis_anum{'reverse'}->[1]->[7] = 'A031007'; # base 7 LE start i=1 value=1
110             # OEIS-Catalogue: A030998 radix=7 i_start=0
111             # OEIS-Catalogue: A031007 radix=7 order=reverse i_start=1
112              
113             $oeis_anum{'forward'}->[0]->[8] = 'A054634'; # base 8, start i=0 value=0
114             $oeis_anum{'forward'}->[1]->[8] = 'A031035'; # base 8, start i=1 value=1
115             # OEIS-Catalogue: A054634 radix=8 i_start=0
116             # OEIS-Catalogue: A031035 radix=8 i_start=1
117             $oeis_anum{'reverse'}->[1]->[8] = 'A031045'; # base 8 LE start i=1 value=1
118             # OEIS-Catalogue: A031045 radix=8 order=reverse i_start=1
119              
120             $oeis_anum{'forward'}->[1]->[9] = 'A031076'; # base 9, start i=1 value=1
121             # OEIS-Catalogue: A031076 radix=9 i_start=1
122             $oeis_anum{'reverse'}->[1]->[9] = 'A031087'; # base 9 LE start i=1 value=1
123             # OEIS-Catalogue: A031087 radix=9 order=reverse i_start=1
124              
125             $oeis_anum{'forward'}->[1]->[10] = 'A007376'; # base 10, start i=1 value=1
126             # OEIS-Catalogue: A007376 i_start=1
127             $oeis_anum{'reverse'}->[1]->[10] = 'A031298'; # base 10 LE start i=1 value=1
128             # OEIS-Catalogue: A031298 radix=10 order=reverse i_start=1
129             #
130             # A033307 is the digits starting from 1 the same as A007376, but with
131             # offset=0 for that 1.
132              
133             sub oeis_anum {
134 3     3 1 11 my ($self) = @_;
135             ### $self
136 3         10 return $oeis_anum{$self->{'order'}}->[$self->i_start]->[$self->{'radix'}];
137             }
138              
139             #------------------------------------------------------------------------------
140              
141             sub rewind {
142 9     9 1 1552 my ($self) = @_;
143 9         29 my $i_start = $self->i_start;
144 9         16 $self->{'n'} = $self->{'i'} = $i_start;
145 9         35 $self->{'pending'} = [ $i_start ];
146             }
147             sub next {
148 144     144 1 1339 my ($self) = @_;
149             ### AllDigits next(): $self->{'i'}
150              
151 144         90 my $value;
152 144 100       89 unless (defined ($value = shift @{$self->{'pending'}})) {
  144         242  
153 96         73 my $pending = $self->{'pending'};
154 96         61 my $radix = $self->{'radix'};
155 96         71 my $n = ++$self->{'n'};
156 96         127 while ($n) {
157 138         128 push @$pending, $n % $radix;
158 138         202 $n = int($n/$radix);
159             }
160 96         75 my $order = $self->{'order'};
161 96 100       152 if ($order eq 'forward') {
    100          
162 32         44 @$pending = reverse @$pending;
163             } elsif ($order eq 'sorted') {
164 32         41 @$pending = sort {$a<=>$b} @$pending;
  14         23  
165             }
166 96         85 $value = shift @$pending;
167             }
168 144         192 return ($self->{'i'}++, $value);
169             }
170              
171             # 1 to 9 r-1 of 1 digit
172             # i=0 to i=9
173             # 10 to 99 r^2-r of 2 digits is 2*(r^2-r) values
174             # total 2*r^2-2r+r = 2*r^2 - r
175             # i=10 to i=10+2*(99-10+1)-1=189
176             # 100 to 999 r^3-r^2 of 3 digits is 3*(r^3-r^2) values
177             # total 2*r^2 - r + 3*(r^3-r^2)
178             # = 3*r^3 + 2*r^2 - r + -3*r^2
179             # = 3*r^3 - r^2 - r
180             # i=191 to ...
181             # 1000 to 9999 r^4-r^3 of 4 digits is values
182             # total 4*(r^4-r^3) + 3*r^3 - r^2 - r
183             # = 4*r^4 - r^3 - r^2 - r
184             #
185             # i = k*r^k - (r^k-1)/(r-1)
186             # = (k*(r-1)*r^k - r^k + 1) / (r-1)
187             # = ((kr-k-1)*r^k + 1) / (r-1)
188             #
189             # ((kr-k-1)*r^k + 1) = i*(r-1)
190             # (kr-k-1)*r^k = i*(r-1)-1
191             #
192              
193             sub ith {
194 225     225 1 347 my ($self, $i) = @_;
195             ### AllDigits ith(): "$i"
196 225 100       292 if ($i < 0) {
197 9         13 return undef;
198             }
199 216 50       299 if (_is_infinite($i)) {
200 0         0 return $i;
201             }
202              
203 216         228 my $radix = $self->{'radix'};
204 216         190 my $len = my $n = ($i*0) + 1; # inherit bignum 1
205 216         143 $i -= 1;
206 216         148 for (;;) {
207 342         273 my $limit = $len*$n*($radix-1);
208             ### len: "$len"
209             ### n: "$n"
210             ### i rem: "$i"
211             ### limit: "$limit"
212              
213 342 100       448 last if $i < $limit;
214 126         91 $i -= $limit;
215 126         86 $n *= $radix;
216 126         91 $len++;
217             }
218              
219             ### remainder: $i
220             ### $len
221             ### $n
222              
223 216         205 $n += int($i/$len);
224 216         151 my $pos = $i % $len;
225              
226             ### $pos
227             ### $n
228              
229 216 100       321 if ($self->{'order'} eq 'sorted') {
230 72         49 my @digits;
231 72         89 while ($len--) {
232 114         80 push @digits, $n % $radix;
233 114         150 $n = int($n/$radix);
234             }
235 72         76 @digits = sort {$a<=>$b} @digits;
  42         41  
236 72         126 return $digits[$pos];
237             }
238              
239 144 100       204 if ($self->{'order'} eq 'forward') {
240 72         71 $pos = $len-1 - $pos;
241             }
242 144         214 while ($pos--) {
243 42         72 $n = int($n/$radix);
244             }
245 144         252 return $n % $radix;
246             }
247              
248             1;
249             __END__