| 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 | # Christopher Williamson, "An Overview of the Thue-Morse Sequence", | ||||||||||||||||||||||||||||||||||
| 20 | # www.math.washington.edu/~morrow/336_12/papers/christopher.pdf | ||||||||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||||||||
| 23 | package Math::NumSeq::DigitSumModulo; | ||||||||||||||||||||||||||||||||||
| 24 | 1 | ▶ | use 5.004; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 25 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 26 | 1 | ▶ | use List::Util 'sum'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||||||||
| 28 | 1 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 29 | 1 | $VERSION = 75; | |||||||||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||||||||
| 31 | 1 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 32 | 1 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 33 | 1 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||||||||||||||||
| 34 | 'Math::NumSeq'); | ||||||||||||||||||||||||||||||||||
| 35 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||||||||
| 37 | 1 | ▶ | use Math::NumSeq::Repdigits; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 38 | 1 | *_digit_split_lowtohigh = \&Math::NumSeq::Repdigits::_digit_split_lowtohigh; | |||||||||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||||||||
| 40 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||||||||
| 41 | #use Smart::Comments; | ||||||||||||||||||||||||||||||||||
| 42 | |||||||||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||||||||
| 44 | 1 | ▶ | use Math::NumSeq::Base::Digits; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 45 | 1 | ▶ | use constant parameter_info_array => | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 46 | [ Math::NumSeq::Base::Digits->parameter_info_list, | ||||||||||||||||||||||||||||||||||
| 47 | { name => 'modulus', | ||||||||||||||||||||||||||||||||||
| 48 | share_key => 'modulus_0', | ||||||||||||||||||||||||||||||||||
| 49 | type => 'integer', | ||||||||||||||||||||||||||||||||||
| 50 | display => Math::NumSeq::__('Modulus'), | ||||||||||||||||||||||||||||||||||
| 51 | default => 0, | ||||||||||||||||||||||||||||||||||
| 52 | minimum => 0, | ||||||||||||||||||||||||||||||||||
| 53 | width => 3, | ||||||||||||||||||||||||||||||||||
| 54 | description => Math::NumSeq::__('Modulus, or 0 to use the radix.'), | ||||||||||||||||||||||||||||||||||
| 55 | }, | ||||||||||||||||||||||||||||||||||
| 56 | 1 | ]; | |||||||||||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||||||||||||
| 58 | 1 | ▶ | use constant i_start => 0; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 59 | 1 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 60 | 1 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 61 | 1 | ▶ | use constant values_min => 0; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 62 | 9 | ▶ | sub values_max { | ||||||||||||||||||||||||||||||||
|
Subroutine
values_max: called CC=2 SCAR=7.6
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 63 | 9 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 64 | 9 | ▶ | if (my $modulus = $self->{'modulus'}) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 65 | 9 | return $modulus - 1; | |||||||||||||||||||||||||||||||||
| 66 | } | ||||||||||||||||||||||||||||||||||
| 67 | 0 | return $self->{'radix'} - 1; | |||||||||||||||||||||||||||||||||
| 68 | } | ||||||||||||||||||||||||||||||||||
| 69 | |||||||||||||||||||||||||||||||||||
| 70 | # use constant name => Math::NumSeq::__('Digit Sum Modulo'); | ||||||||||||||||||||||||||||||||||
| 71 | 2 | ▶ | sub description { | ||||||||||||||||||||||||||||||||
|
Subroutine
description: called CC=5 SCAR=17.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 72 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 73 | 2 | ▶ | if (ref $self) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 74 | 1 | my $radix = $self->{'radix'}; | |||||||||||||||||||||||||||||||||
| 75 | 1 | ▶ | my $modulus = ($self->{'modulus'} ? $self->{'modulus'} : $radix); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 76 | 1 | ▶ | return Math::NumSeq::__('Sum digits of i in base ') . $radix | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$radix == 2 and $modulus == 2
MC/DC0%0/2
$radix == 2 and $modulus == 2
$radix == 2
$modulus == 2
Truth table33%1/3
A and B
A= $radix == 2B= $modulus == 2
| |||||||||||||||||||||||||||||||||||
| 77 | . Math::NumSeq::__(', then that sum taken modulo ') . $modulus | ||||||||||||||||||||||||||||||||||
| 78 | . ($radix == 2 && $modulus == 2 | ||||||||||||||||||||||||||||||||||
| 79 | ? Math::NumSeq::__(", which means bitwise parity.") | ||||||||||||||||||||||||||||||||||
| 80 | : Math::NumSeq::__('.')); | ||||||||||||||||||||||||||||||||||
| 81 | } else { | ||||||||||||||||||||||||||||||||||
| 82 | 1 | return Math::NumSeq::__('Sum of the digits in the given radix, modulo that radix or a given modulus. Eg. for binary this is the bitwise parity.'); | |||||||||||||||||||||||||||||||||
| 83 | } | ||||||||||||||||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||||||||
| 86 | # cf A001969 "evil" numbers with even 1s | ||||||||||||||||||||||||||||||||||
| 87 | # A000069 "odious" numbers with odd 1s | ||||||||||||||||||||||||||||||||||
| 88 | # A026147 position of n'th thue-morse parity 1 | ||||||||||||||||||||||||||||||||||
| 89 | # A059448 1,0 parity of number of 0 digits when written in binary | ||||||||||||||||||||||||||||||||||
| 90 | # A001285 Thue-Morse as 1,2 | ||||||||||||||||||||||||||||||||||
| 91 | # A010059 Thue-Morse as 1,0 | ||||||||||||||||||||||||||||||||||
| 92 | # A010060 Thue-Morse as 0,1 | ||||||||||||||||||||||||||||||||||
| 93 | # A106400 Thue-Morse as 1,-1 1, -1, -1, 1, -1, 1 | ||||||||||||||||||||||||||||||||||
| 94 | # A186032 Thue-Morse as -1,1 offset one 1, 1, -1, 1, -1 | ||||||||||||||||||||||||||||||||||
| 95 | # A108784 Thue-Morse as -1,1 1, 1, -1, 1, -1 | ||||||||||||||||||||||||||||||||||
| 96 | # A076826 Thue-Morse as 0,2 with a(2n+1)=1 in between | ||||||||||||||||||||||||||||||||||
| 97 | # A080813 lexico is 1,1,0,1,1,0 then thue-morse 0,1 thue-morse | ||||||||||||||||||||||||||||||||||
| 98 | # | ||||||||||||||||||||||||||||||||||
| 99 | # A143579 alternately odious and evil, permutation of the integers | ||||||||||||||||||||||||||||||||||
| 100 | # A143580 alternately, modulo 2 | ||||||||||||||||||||||||||||||||||
| 101 | # seems A143580 == A010059 thue-morse 1,0 | ||||||||||||||||||||||||||||||||||
| 102 | # | ||||||||||||||||||||||||||||||||||
| 103 | 1 | my %oeis_anum = ('2,2' => 'A010060', | |||||||||||||||||||||||||||||||||
| 104 | '3,3' => 'A053838', | ||||||||||||||||||||||||||||||||||
| 105 | '4,4' => 'A053839', # radix=4 | ||||||||||||||||||||||||||||||||||
| 106 | '5,5' => 'A053840', # radix=5 | ||||||||||||||||||||||||||||||||||
| 107 | '6,6' => 'A053841', # radix=6 | ||||||||||||||||||||||||||||||||||
| 108 | '7,7' => 'A053842', # radix=7 | ||||||||||||||||||||||||||||||||||
| 109 | '8,8' => 'A053843', # radix=8 | ||||||||||||||||||||||||||||||||||
| 110 | '9,9' => 'A053844', # radix=9 | ||||||||||||||||||||||||||||||||||
| 111 | '10,10' => 'A053837', | ||||||||||||||||||||||||||||||||||
| 112 | # OEIS-Catalogue: A053837 | ||||||||||||||||||||||||||||||||||
| 113 | # OEIS-Catalogue: A053844 radix=9 | ||||||||||||||||||||||||||||||||||
| 114 | # OEIS-Catalogue: A053843 radix=8 | ||||||||||||||||||||||||||||||||||
| 115 | # OEIS-Catalogue: A053842 radix=7 | ||||||||||||||||||||||||||||||||||
| 116 | # OEIS-Catalogue: A053841 radix=6 | ||||||||||||||||||||||||||||||||||
| 117 | # OEIS-Catalogue: A053840 radix=5 | ||||||||||||||||||||||||||||||||||
| 118 | # OEIS-Catalogue: A053839 radix=4 | ||||||||||||||||||||||||||||||||||
| 119 | # OEIS-Catalogue: A053838 radix=3 | ||||||||||||||||||||||||||||||||||
| 120 | # OEIS-Catalogue: A010060 radix=2 # binary, Thue-Morse | ||||||||||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||||||||
| 122 | '10,2' => 'A179081', | ||||||||||||||||||||||||||||||||||
| 123 | # OEIS-Catalogue: A179081 modulus=2 | ||||||||||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||||||||
| 125 | '2,3' => 'A071858', | ||||||||||||||||||||||||||||||||||
| 126 | '2,4' => 'A179868', | ||||||||||||||||||||||||||||||||||
| 127 | # OEIS-Catalogue: A071858 radix=2 modulus=3 | ||||||||||||||||||||||||||||||||||
| 128 | # OEIS-Catalogue: A179868 radix=2 modulus=4 | ||||||||||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||||||||||
| 130 | '3,4' => 'A051329', # ternary modulo 4 | ||||||||||||||||||||||||||||||||||
| 131 | # OEIS-Catalogue: A051329 radix=3 modulus=4 | ||||||||||||||||||||||||||||||||||
| 132 | ); | ||||||||||||||||||||||||||||||||||
| 133 | 1 | ▶ | sub oeis_anum { | ||||||||||||||||||||||||||||||||
|
Subroutine
oeis_anum: called CC=4 SCAR=16.8
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 134 | 1 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 135 | 1 | my $radix = $self->{'radix'}; | |||||||||||||||||||||||||||||||||
| 136 | 1 | ▶ | my $modulus = ($self->{'modulus'} || $radix); | ||||||||||||||||||||||||||||||||
|
Condition33%1/3
$self->{'modulus'} || $radix
MC/DC0%0/2
$self->{'modulus'} || $radix
$self->{'modulus'}
$radix
Truth table33%1/3
A || B
A= $self->{'modulus'}B= $radix
| |||||||||||||||||||||||||||||||||||
| 137 | |||||||||||||||||||||||||||||||||||
| 138 | 1 | ▶ | if ($modulus == 1) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 139 | 0 | return 'A000004'; # all zeros | |||||||||||||||||||||||||||||||||
| 140 | # OEIS-Other: A000004 modulus=1 | ||||||||||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||||||||
| 143 | # radix==M+1, 2M+1 etc any radix==1modM is same as whole modulo M. | ||||||||||||||||||||||||||||||||||
| 144 | # Including radix=odd modulus=2 is 0,1 repeating. | ||||||||||||||||||||||||||||||||||
| 145 | 1 | ▶ | if (($radix % $modulus) == 1) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 146 | ### ENHANCE-ME: Modulo a-num without creating object, maybe | ||||||||||||||||||||||||||||||||||
| 147 | 0 | require Math::NumSeq::Modulo; | |||||||||||||||||||||||||||||||||
| 148 | 0 | return Math::NumSeq::Modulo->new(modulus=>$modulus)->oeis_anum; | |||||||||||||||||||||||||||||||||
| 149 | |||||||||||||||||||||||||||||||||||
| 150 | # OEIS-Other: A000035 radix=3 modulus=2 # n mod 2, parity | ||||||||||||||||||||||||||||||||||
| 151 | # OEIS-Other: A000035 radix=5 modulus=2 | ||||||||||||||||||||||||||||||||||
| 152 | # OEIS-Other: A000035 radix=37 modulus=2 | ||||||||||||||||||||||||||||||||||
| 153 | # OEIS-Other: A010872 radix=4 modulus=3 # n mod 3 | ||||||||||||||||||||||||||||||||||
| 154 | } | ||||||||||||||||||||||||||||||||||
| 155 | |||||||||||||||||||||||||||||||||||
| 156 | 1 | return $oeis_anum{"$radix,$modulus"}; | |||||||||||||||||||||||||||||||||
| 157 | } | ||||||||||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||||||||
| 159 | # ENHANCE-ME: | ||||||||||||||||||||||||||||||||||
| 160 | # next() is +1 mod m, except when xx09 wraps to xx10 which is +2, | ||||||||||||||||||||||||||||||||||
| 161 | # or when x099 to x100 then +3, etc extra is how many low 9s | ||||||||||||||||||||||||||||||||||
| 162 | # | ||||||||||||||||||||||||||||||||||
| 163 | # sub next { | ||||||||||||||||||||||||||||||||||
| 164 | # my ($self) = @_; | ||||||||||||||||||||||||||||||||||
| 165 | # my $radix = $self->{'radix'}; | ||||||||||||||||||||||||||||||||||
| 166 | # my $sum = $self->{'sum'} + 1; | ||||||||||||||||||||||||||||||||||
| 167 | # if (++$self->{'digits'}->[0] >= $radix) { | ||||||||||||||||||||||||||||||||||
| 168 | # $self->{'digits'}->[0] = 0; | ||||||||||||||||||||||||||||||||||
| 169 | # my $i = 1; | ||||||||||||||||||||||||||||||||||
| 170 | # for (;;) { | ||||||||||||||||||||||||||||||||||
| 171 | # $sum++; | ||||||||||||||||||||||||||||||||||
| 172 | # if (++$self->{'digits'}->[$i] < $radix) { | ||||||||||||||||||||||||||||||||||
| 173 | # last; | ||||||||||||||||||||||||||||||||||
| 174 | # } | ||||||||||||||||||||||||||||||||||
| 175 | # } | ||||||||||||||||||||||||||||||||||
| 176 | # } | ||||||||||||||||||||||||||||||||||
| 177 | # return ($self->{'i'}++, ($self->{'sum'} = ($sum % $radix))); | ||||||||||||||||||||||||||||||||||
| 178 | # } | ||||||||||||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||||||||||||
| 180 | 93 | ▶ | sub ith { | ||||||||||||||||||||||||||||||||
|
Subroutine
ith: called CC=3 SCAR=12.7
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 181 | 93 | my ($self, $i) = @_; | |||||||||||||||||||||||||||||||||
| 182 | |||||||||||||||||||||||||||||||||||
| 183 | 93 | ▶ | if (_is_infinite ($i)) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 184 | 0 | return $i; | |||||||||||||||||||||||||||||||||
| 185 | } | ||||||||||||||||||||||||||||||||||
| 186 | 93 | my $radix = $self->{'radix'}; | |||||||||||||||||||||||||||||||||
| 187 | return sum(0,_digit_split_lowtohigh($i,$radix)) | ||||||||||||||||||||||||||||||||||
| 188 | 93 | ▶ | % ($self->{'modulus'} || $radix); | ||||||||||||||||||||||||||||||||
|
Condition33%1/3
$self->{'modulus'} || $radix
MC/DC0%0/2
$self->{'modulus'} || $radix
$self->{'modulus'}
$radix
Truth table33%1/3
A || B
A= $self->{'modulus'}B= $radix
| |||||||||||||||||||||||||||||||||||
| 189 | } | ||||||||||||||||||||||||||||||||||
| 190 | |||||||||||||||||||||||||||||||||||
| 191 | 9 | ▶ | sub pred { | ||||||||||||||||||||||||||||||||
|
Subroutine
pred: called CC=3 SCAR=14.2
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 192 | 9 | my ($self, $value) = @_; | |||||||||||||||||||||||||||||||||
| 193 | 9 | ▶ | return ($value == int($value) | ||||||||||||||||||||||||||||||||
|
Condition33%2/6
$value == int $value && $value >= 0 && $value <= $self->values_max
$value == int $value and $value >= 0
MC/DC0%0/3
$value == int $value && $value >= 0 && $value <= $self->values_max
$value == int $value
$value >= 0
$value <= $self->values_max
Truth table25%1/4
A and B && C
A= $value == int $valueB= $value >= 0C= $value <= $self->values_max
| |||||||||||||||||||||||||||||||||||
| 194 | && $value >= 0 | ||||||||||||||||||||||||||||||||||
| 195 | && $value <= $self->values_max); | ||||||||||||||||||||||||||||||||||
| 196 | } | ||||||||||||||||||||||||||||||||||
| 197 | |||||||||||||||||||||||||||||||||||
| 198 | 1 | 1; | |||||||||||||||||||||||||||||||||
| 199 | __END__ | ||||||||||||||||||||||||||||||||||