| 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::AllDigits; | ||||||||||||||
| 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 | 1 | ▶ | use Math::NumSeq::Base::Digits; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 25 | 1 | @ISA = ('Math::NumSeq::Base::Digits'); | |||||||||||||
| 26 | |||||||||||||||
| 27 | 1 | ▶ | use Math::NumSeq 7; # v.7 for _is_infinite() | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 28 | 1 | *_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 | ▶ | use constant description => Math::NumSeq::__('Digits of all the integers.'); | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 36 | 1 | ▶ | use constant default_i_start => 0; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 37 | |||||||||||||||
| 38 | 1 | ▶ | use constant parameter_info_array => | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 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 | ]; | |||||||||||||
| 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 | 1 | my %oeis_anum; | |||||||||||||
| 80 | |||||||||||||||
| 81 | 1 | $oeis_anum{'forward'}->[0]->[2] = 'A030190'; # base 2, start i=0 value=0 | |||||||||||||
| 82 | 1 | $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 | 1 | $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 | 1 | $oeis_anum{'forward'}->[0]->[3] = 'A054635'; # base 3, start i=0 value=0 | |||||||||||||
| 89 | 1 | $oeis_anum{'forward'}->[1]->[3] = 'A003137'; # base 3, start i=1 value=1 | |||||||||||||
| 90 | 1 | $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 | 1 | $oeis_anum{'forward'}->[1]->[4] = 'A030373'; # base 4, start i=1 value=1 | |||||||||||||
| 96 | 1 | $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 | 1 | $oeis_anum{'forward'}->[1]->[5] = 'A031219'; # base 5, start i=1 value=1 | |||||||||||||
| 101 | 1 | $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 | 1 | $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 | 1 | $oeis_anum{'forward'}->[0]->[7] = 'A030998'; # base 7, start i=0 value=0 | |||||||||||||
| 109 | 1 | $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 | 1 | $oeis_anum{'forward'}->[0]->[8] = 'A054634'; # base 8, start i=0 value=0 | |||||||||||||
| 114 | 1 | $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 | 1 | $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 | 1 | $oeis_anum{'forward'}->[1]->[9] = 'A031076'; # base 9, start i=1 value=1 | |||||||||||||
| 121 | # OEIS-Catalogue: A031076 radix=9 i_start=1 | ||||||||||||||
| 122 | 1 | $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 | 1 | $oeis_anum{'forward'}->[1]->[10] = 'A007376'; # base 10, start i=1 value=1 | |||||||||||||
| 126 | # OEIS-Catalogue: A007376 i_start=1 | ||||||||||||||
| 127 | 1 | $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 | 3 | ▶ | sub oeis_anum { | ||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||
| 134 | 3 | my ($self) = @_; | |||||||||||||
| 135 | ### $self | ||||||||||||||
| 136 | 3 | return $oeis_anum{$self->{'order'}}->[$self->i_start]->[$self->{'radix'}]; | |||||||||||||
| 137 | } | ||||||||||||||
| 138 | |||||||||||||||
| 139 | #------------------------------------------------------------------------------ | ||||||||||||||
| 140 | |||||||||||||||
| 141 | 9 | ▶ | sub rewind { | ||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||
| 142 | 9 | my ($self) = @_; | |||||||||||||
| 143 | 9 | my $i_start = $self->i_start; | |||||||||||||
| 144 | 9 | $self->{'n'} = $self->{'i'} = $i_start; | |||||||||||||
| 145 | 9 | $self->{'pending'} = [ $i_start ]; | |||||||||||||
| 146 | } | ||||||||||||||
| 147 | 144 | ▶ | sub next { | ||||||||||||
|
Subroutine
next: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||
| 148 | 144 | my ($self) = @_; | |||||||||||||
| 149 | ### AllDigits next(): $self->{'i'} | ||||||||||||||
| 150 | |||||||||||||||
| 151 | 144 | my $value; | |||||||||||||
| 152 | 144 | ▶ | unless (defined ($value = shift @{$self->{'pending'}})) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 153 | 96 | my $pending = $self->{'pending'}; | |||||||||||||
| 154 | 96 | my $radix = $self->{'radix'}; | |||||||||||||
| 155 | 96 | my $n = ++$self->{'n'}; | |||||||||||||
| 156 | 96 | ▶ | while ($n) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 157 | 138 | push @$pending, $n % $radix; | |||||||||||||
| 158 | 138 | $n = int($n/$radix); | |||||||||||||
| 159 | } | ||||||||||||||
| 160 | 96 | my $order = $self->{'order'}; | |||||||||||||
| 161 | 96 | ▶ | if ($order eq 'forward') { | ||||||||||||
|
Branch: 2 branches
| |||||||||||||||
| 162 | 32 | @$pending = reverse @$pending; | |||||||||||||
| 163 | } elsif ($order eq 'sorted') { | ||||||||||||||
| 164 | 32 | @$pending = sort {$a<=>$b} @$pending; | |||||||||||||
| 165 | } | ||||||||||||||
| 166 | 96 | $value = shift @$pending; | |||||||||||||
| 167 | } | ||||||||||||||
| 168 | 144 | 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 | 225 | ▶ | sub ith { | ||||||||||||
|
Subroutine
ith: called CC=8 SCAR=20.8
Pod
documented
| |||||||||||||||
| 194 | 225 | my ($self, $i) = @_; | |||||||||||||
| 195 | ### AllDigits ith(): "$i" | ||||||||||||||
| 196 | 225 | ▶ | if ($i < 0) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 197 | 9 | return undef; | |||||||||||||
| 198 | } | ||||||||||||||
| 199 | 216 | ▶ | if (_is_infinite($i)) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 200 | 0 | return $i; | |||||||||||||
| 201 | } | ||||||||||||||
| 202 | |||||||||||||||
| 203 | 216 | my $radix = $self->{'radix'}; | |||||||||||||
| 204 | 216 | my $len = my $n = ($i*0) + 1; # inherit bignum 1 | |||||||||||||
| 205 | 216 | $i -= 1; | |||||||||||||
| 206 | 216 | for (;;) { | |||||||||||||
| 207 | 342 | my $limit = $len*$n*($radix-1); | |||||||||||||
| 208 | ### len: "$len" | ||||||||||||||
| 209 | ### n: "$n" | ||||||||||||||
| 210 | ### i rem: "$i" | ||||||||||||||
| 211 | ### limit: "$limit" | ||||||||||||||
| 212 | |||||||||||||||
| 213 | 342 | ▶ | last if $i < $limit; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 214 | 126 | $i -= $limit; | |||||||||||||
| 215 | 126 | $n *= $radix; | |||||||||||||
| 216 | 126 | $len++; | |||||||||||||
| 217 | } | ||||||||||||||
| 218 | |||||||||||||||
| 219 | ### remainder: $i | ||||||||||||||
| 220 | ### $len | ||||||||||||||
| 221 | ### $n | ||||||||||||||
| 222 | |||||||||||||||
| 223 | 216 | $n += int($i/$len); | |||||||||||||
| 224 | 216 | my $pos = $i % $len; | |||||||||||||
| 225 | |||||||||||||||
| 226 | ### $pos | ||||||||||||||
| 227 | ### $n | ||||||||||||||
| 228 | |||||||||||||||
| 229 | 216 | ▶ | if ($self->{'order'} eq 'sorted') { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 230 | 72 | my @digits; | |||||||||||||
| 231 | 72 | ▶ | while ($len--) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 232 | 114 | push @digits, $n % $radix; | |||||||||||||
| 233 | 114 | $n = int($n/$radix); | |||||||||||||
| 234 | } | ||||||||||||||
| 235 | 72 | @digits = sort {$a<=>$b} @digits; | |||||||||||||
| 236 | 72 | return $digits[$pos]; | |||||||||||||
| 237 | } | ||||||||||||||
| 238 | |||||||||||||||
| 239 | 144 | ▶ | if ($self->{'order'} eq 'forward') { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 240 | 72 | $pos = $len-1 - $pos; | |||||||||||||
| 241 | } | ||||||||||||||
| 242 | 144 | ▶ | while ($pos--) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 243 | 42 | $n = int($n/$radix); | |||||||||||||
| 244 | } | ||||||||||||||
| 245 | 144 | return $n % $radix; | |||||||||||||
| 246 | } | ||||||||||||||
| 247 | |||||||||||||||
| 248 | 1 | 1; | |||||||||||||
| 249 | __END__ | ||||||||||||||