NumSeq/GolombSequence.pm

filter: Statementstmt 99.1% 121 / 122 Branchbran 95.0% 19 / 20 Conditioncond 50.0% 1 / 2 MC/DCmcdc 0.0% 0 / 1 Subroutinesub 100% 21 / 21 Podpod 100% 3 / 3 totaltotal 97.6% 165 / 169 CC 12 SCAR 11.6
CC
12
Cov
98%
rewind
8.0
next
4.0
_upto_primes
2.0
CRAP 3.2
« NumSeq/Primes.pm ↑ Summary NumSeq/PowerPart.pm »
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  
19  
20 # Maybe: using_values => 'primes'
21 #
22 # http://mathworld.wolfram.com/SilvermansSequence.html
23 #
24 # Y.-F. S. Petermann, J.-L. Remy and I. Vardi, Discrete derivatives of
25 # sequences, Adv. in Appl. Math. 27 (2001), 562-84.
26 # http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/publications.html
27 # http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/discrete_derivatives.ps
28 #
29 # cf A112377 self seq sub1 drop 0s 1, 2, 1, 1, 3, 1, 2
30 # A112378 self seq add1 drop 0s
31 # A112379 self seq sub1 drop 0s 1, 2, 1, 3,
32 # A112380 self seq sub1 drop 0s 1, 2, 1, 1, 3, 2, 1
33  
34  
35 package Math::NumSeq::GolombSequence;
36 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
38 2 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
39  
40 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
41 2 $VERSION = 75;
42  
43 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 2 @ISA = ('Math::NumSeq');
45  
46 # uncomment this to run the ### lines
47 #use Smart::Comments;
48  
49 # use constant name => Math::NumSeq::__('Golomb Sequence');
50 2 ▶use constant description => Math::NumSeq::__('Golomb sequence 1,2,2,3,3,4,4,4,etc, its own run lengths.');
Subroutine BEGIN: called CC=1 SCAR=0.0
51 2 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
52 2 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
53 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
54 2 ▶use constant characteristic_non_decreasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
55 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
56  
57 2 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
58 [
59 { name => 'using_values',
60 display => Math::NumSeq::__('Using Values'),
61 type => 'enum',
62 default => 'all',
63 choices => ['all','odd','even','3k','squares','primes'],
64 choices_display => [Math::NumSeq::__('All'),
65 Math::NumSeq::__('Odd'),
66 Math::NumSeq::__('Even'),
67 # TRANSLATORS: "3k" meaning triples 3,6,9,12,15, probably no need to translate except into another script if Latin letter "k" won't be recognised
68 Math::NumSeq::__('3k'),
69 Math::NumSeq::__('Squares'),
70 Math::NumSeq::__('Primes'),
71 ],
72 description => Math::NumSeq::__('Which values to use in the sequence. Default "all" means all integers.'),
73 },
74 2 ];
75  
76 #------------------------------------------------------------------------------
77  
78 # cf A001463 golomb seq partial sums
79 # A088517 golomb first diffs, is 0/1 characteristic of partial sums
80 # A163563 a(n)+1 reps
81 # A113722 a(n) reps of 2n+1
82 # A113724 a(n) reps of 2n+2 evens
83 # A103320 condensed 1,22,33,444,555,6666 etc
84 # A104236 n*golomb(n)
85 # A143125 n*golomb(n) cumulative
86 # A095773 generalizing
87 # A116548 divisors occurring fewer than a(n) times
88 # A072649 n occurs Fibonacci(n) times
89 # A108229 n occurs Lucas(n) times
90 # A109167 n appears a(n) times
91 #
92 2 my %oeis_anum = (all => 'A001462',
93 # OEIS-Catalogue: A001462
94  
95 odd => 'A080605',
96 # OEIS-Catalogue: A080605 using_values=odd
97  
98 even => 'A080606',
99 # OEIS-Catalogue: A080606 using_values=even
100  
101 '3k' => 'A080607',
102 # OEIS-Catalogue: A080607 using_values=3k
103  
104 'squares' => 'A013189',
105 # OEIS-Catalogue: A013189 using_values=squares
106  
107 'primes' => 'A169682',
108 # OEIS-Catalogue: A169682 using_values=primes
109 );
110 6 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
111 6 my ($self) = @_;
112 6 return $oeis_anum{$self->{'using_values'}};
113 }
114  
115 #------------------------------------------------------------------------------
116 #
117 # count[0] is how many of value[0] still to be returned
118 # when count[0]==0 must increment value[0] and new count from k=1
119  
120  
121 31 ▶sub rewind {
Subroutine rewind: called CC=8 SCAR=20.8
Pod documented
122 31 my ($self) = @_;
123 31 $self->{'i'} = $self->i_start;
124  
125 31 my $using_values = $self->{'using_values'};
126 31 ▶ $self->{'upto_func'} = $self->can("_upto_$using_values")
Condition50%1/2
$self->can("_upto_$using_values") || croak(qq[Unrecognised using_values "$using_values"])
l!l
310
MC/DC0%0/1
$self->can("_upto_$using_values") || croak(qq[Unrecognised using_values "$using_values"])
$self->can("_upto_$using_values")
Truth table50%1/2
A
A= $self->can("_upto_$using_values")
Aresult
11
00
127 || croak "Unrecognised using_values \"$using_values\"";
128  
129 # ENHANCE-ME: a hash table for these initializations, but would have to
130 # clone the arrays
131 31 ▶ if ($using_values eq 'all') {
Branch: 6 branches
BranchTrueFalseTotal
if ($using_values eq 'all') { } 6 25 31
elsif ($using_values eq 'odd') { } 5 20 25
elsif ($using_values eq 'even') { } 5 15 20
elsif ($using_values eq '3k') { } 5 10 15
elsif ($using_values eq 'squares') { } 5 5 10
elsif ($using_values eq 'primes') { } 5 0 5
132 6 $self->{'small'} = [ 1, 2, 2 ];
133 6 $self->{'counts'} = [ 2 ];
134 6 $self->{'values'} = [ 3 ];
135 6 $self->{'upto'} = [ 3 ];
136 6 $self->{'extend_count'} = 2;
137 6 $self->{'extend_value'} = 3;
138 6 $self->{'extend_upto'} = 3;
139  
140 } elsif ($using_values eq 'odd') {
141 5 $self->{'counts'} = [ 1, 3 ];
142 5 $self->{'upto'} = [ 1, 2 ];
143 5 $self->{'values'} = [ 1, 3 ];
144 5 $self->{'extend_count'} = 2;
145 5 $self->{'extend_value'} = 3;
146 5 $self->{'extend_upto'} = 2;
147  
148 } elsif ($using_values eq 'even') {
149 5 $self->{'counts'} = [ 2 ];
150 5 $self->{'values'} = [ 4 ];
151 5 $self->{'upto'} = [ 2 ];
152 5 $self->{'small'} = [ 2, 2 ];
153 5 $self->{'extend_count'} = 2;
154 5 $self->{'extend_value'} = 4;
155 5 $self->{'extend_upto'} = 2;
156  
157 } elsif ($using_values eq '3k') {
158 5 $self->{'counts'} = [ 3 ];
159 5 $self->{'values'} = [ 3 ];
160 5 $self->{'upto'} = [ 1 ];
161 5 $self->{'extend_count'} = 2;
162 5 $self->{'extend_value'} = 3;
163 5 $self->{'extend_upto'} = 1;
164  
165 } elsif ($using_values eq 'squares') {
166 5 $self->{'counts'} = [ 1, 4 ];
167 5 $self->{'values'} = [ 1, 4 ];
168 5 $self->{'upto'} = [ 1, 2 ];
169 5 $self->{'extend_count'} = 3;
170 5 $self->{'extend_value'} = 4;
171 5 $self->{'extend_upto'} = 2;
172  
173 } elsif ($using_values eq 'primes') {
174 5 $self->{'small'} = [ 2, 2 ];
175 5 $self->{'counts'} = [ 2 ];
176 5 $self->{'values'} = [ 3 ];
177 5 $self->{'upto'} = [ 2 ];
178 5 $self->{'extend_count'} = 2;
179 5 $self->{'extend_value'} = 3;
180 5 $self->{'extend_upto'} = 2;
181 5 $self->{'primes'} = [ 2, 3, 5 ];
182  
183 } else {
184 0 croak "Unrecognised using_values: ",$using_values;
185 }
186 }
187  
188 141 ▶sub _upto_all {
Subroutine _upto_all: called CC=1 SCAR=0.0
189 141 my ($self, $upto) = @_;
190 141 return $upto;
191 }
192 108 ▶sub _upto_odd {
Subroutine _upto_odd: called CC=1 SCAR=0.0
193 108 my ($self, $upto) = @_;
194 108 return 2*$upto-1;
195 }
196 100 ▶sub _upto_even {
Subroutine _upto_even: called CC=1 SCAR=0.0
197 100 my ($self, $upto) = @_;
198 100 return 2*$upto;
199 }
200 90 ▶sub _upto_3k {
Subroutine _upto_3k: called CC=1 SCAR=0.0
201 90 my ($self, $upto) = @_;
202 90 return 3*$upto;
203 }
204 62 ▶sub _upto_squares {
Subroutine _upto_squares: called CC=1 SCAR=0.0
205 62 my ($self, $upto) = @_;
206 62 return $upto*$upto;
207 }
208 89 ▶sub _upto_primes {
Subroutine _upto_primes: called CC=2 SCAR=6.9
209 89 my ($self, $upto) = @_;
210 89 $upto--;
211 89 my $primes = $self->{'primes'};
212 89 ▶ if ($upto > $#$primes) {
Branch: 1 branch
BranchTrueFalseTotal
if ($upto > $primes->$#*) 15 74 89
213 15 require Math::NumSeq::Primes;
214 15 @$primes = Math::NumSeq::Primes::_primes_list (2, 2 * $primes->[-1]);
215 }
216 89 return $primes->[$upto];
217 }
218  
219 6542 ▶sub next {
Subroutine next: called CC=4 SCAR=13.9
Pod documented
220 6542 my ($self) = @_;
221 ### GolombSequence next(): "i=$self->{'i'}"
222 ### counts: join(',',@{$self->{'counts'}})
223 ### values: join(',',@{$self->{'values'}})
224  
225 6542 ▶ if (defined (my $value = shift @{$self->{'small'}})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $value = shift @{$$self{"small"};})) 28 6514 6542
226 28 return ($self->{'i'}++, $value);
227 }
228  
229 6514 my $values = $self->{'values'};
230 6514 my $upto = $self->{'upto'};
231 6514 my $ret = $values->[0];
232  
233 6514 my $counts = $self->{'counts'};
234 6514 ▶ for (my $pos = 0; --$counts->[$pos] <= 0; $pos++) {
Branch: 1 branch
BranchTrueFalseTotal
if (--$counts->[$pos] <= 0) 590 6514 7104
235 590 ▶ if ($pos >= $#$counts) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos >= $counts->$#*) 58 532 590
236 ### extend ...
237 58 push @$counts, $self->{'extend_count'};
238 58 push @$upto, $self->{'extend_upto'};
239 58 push @$values, $self->{'extend_value'};
240 }
241 590 $upto->[$pos]++;
242 590 my $upto_func = $self->{'upto_func'};
243 590 $values->[$pos] = $self->$upto_func($upto->[$pos]);
244 590 $counts->[$pos] = $values->[$pos+1];
245 }
246 6514 return ($self->{'i'}++, $ret);
247 }
248  
249 2 1;
250 __END__
« NumSeq/Primes.pm ↑ Summary NumSeq/PowerPart.pm »