File Coverage

blib/lib/Math/NumSeq/Polygonal.pm
Criterion Covered Total %
statement 73 76 96.0
branch 29 32 90.6
condition 5 7 71.4
subroutine 16 16 100.0
pod 6 6 100.0
total 129 137 94.1


line stmt bran cond sub pod time code
1             # Copyright 2010, 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::Polygonal;
19 1     1   1729858 use 5.004;
  1         5  
  1         64  
20 1     1   107 use strict;
  1         3  
  1         58  
21              
22 1     1   26 use vars '$VERSION', '@ISA';
  1         2  
  1         116  
23             $VERSION = 71;
24              
25 1     1   8 use Math::NumSeq;
  1         2  
  1         29  
26 1     1   14 use Math::NumSeq::Base::IterateIth;
  1         2  
  1         43  
27             @ISA = ('Math::NumSeq::Base::IterateIth',
28             'Math::NumSeq');
29              
30             # uncomment this to run the ### lines
31             #use Smart::Comments;
32              
33             # use constant name => Math::NumSeq::__('Polygonal Numbers');
34 1     1   7 use constant i_start => 0;
  1         3  
  1         70  
35 1     1   5 use constant values_min => 0;
  1         2  
  1         55  
36 1     1   5 use constant characteristic_increasing => 1;
  1         1  
  1         56  
37 1     1   6 use constant characteristic_integer => 1;
  1         2  
  1         159  
38 1         7 use constant parameter_info_array =>
39             [
40             { name => 'polygonal',
41             display => Math::NumSeq::__('Polygonal'),
42             type => 'integer',
43             default => 5,
44             minimum => 3,
45             width => 3,
46             description => Math::NumSeq::__('Which polygonal numbers to show. 3 is the triangular numbers, 4 the perfect squares, 5 the pentagonal numbers, etc.'),
47             },
48             { name => 'pairs',
49             display => Math::NumSeq::__('Pairs'),
50             type => 'enum',
51             default => 'first',
52             choices => ['first',
53             'second',
54             'both',
55             'average'],
56             choices_display => [Math::NumSeq::__('First'),
57             Math::NumSeq::__('Second'),
58             Math::NumSeq::__('Both'),
59             Math::NumSeq::__('Average')],
60             description => Math::NumSeq::__('Which of the pair of values to show.'),
61             },
62 1     1   8 ];
  1         2  
63              
64             sub description {
65 30     30 1 143 my ($self) = @_;
66 30 100       79 if (ref $self) {
67 15 100       141 return "$self->{'polygonal'}-gonal numbers"
    100          
    100          
68             . ($self->{'pairs'} eq 'second' ? " of the second kind"
69             : $self->{'pairs'} eq 'both' ? " of both first and second kind"
70             : $self->{'pairs'} eq 'average' ? ", average of first and second kind"
71             : '');
72             } else {
73             # class method
74 15         84 return Math::NumSeq::__('Polygonal numbers');
75             }
76             }
77              
78              
79             #------------------------------------------------------------------------------
80             # cf A183221 complement of 9-gonals
81             # A008795 molien from naive interleaved unsorted "average" polygonal=3
82             # A144065 generalized pentagonals - 1,
83             # being 2*3*4*(n+1)+1 is a perfect square
84              
85             my %oeis_anum;
86              
87             $oeis_anum{'first'}->[3] = 'A000217'; # 3 triangular
88             $oeis_anum{'second'}->[3] = 'A000217'; # triangular same as "first"
89             $oeis_anum{'both'}->[3] = 'A000217'; # no duplicates
90             $oeis_anum{'average'}->[3] = 'A000217'; # first==second so average same
91             # OEIS-Other: A000217 polygonal=3
92             # OEIS-Other: A000217 polygonal=3 pairs=second
93             # OEIS-Other: A000217 polygonal=3 pairs=both
94             # OEIS-Other: A000217 polygonal=3 pairs=average
95              
96             $oeis_anum{'first'}->[4] = 'A000290'; # 4 squares
97             $oeis_anum{'second'}->[4] = 'A000290'; # squares, same as "first"
98             $oeis_anum{'both'}->[4] = 'A000290'; # no duplicates
99             $oeis_anum{'average'}->[4] = 'A000290'; # squares, same as "first"
100             # OEIS-Other: A000290 polygonal=4
101             # OEIS-Other: A000290 polygonal=4 pairs=second
102             # OEIS-Other: A000290 polygonal=4 pairs=both
103             # OEIS-Other: A000290 polygonal=4 pairs=average
104              
105             $oeis_anum{'first'}->[5] = 'A000326'; # 5 pentagonal
106             $oeis_anum{'second'}->[5] = 'A005449';
107             $oeis_anum{'both'}->[5] = 'A001318';
108             # OEIS-Catalogue: A000326 polygonal=5 pairs=first
109             # OEIS-Catalogue: A005449 polygonal=5 pairs=second
110             # OEIS-Catalogue: A001318 polygonal=5 pairs=both
111              
112             $oeis_anum{'first'}->[6] = 'A000384'; # 6 hexagonal
113             $oeis_anum{'second'}->[6] = 'A014105';
114             $oeis_anum{'both'}->[6] = 'A000217'; # together triangular numbers
115             # OEIS-Catalogue: A000384 polygonal=6 pairs=first
116             # OEIS-Catalogue: A014105 polygonal=6 pairs=second
117             # OEIS-Other: A000217 polygonal=6 pairs=both
118              
119             $oeis_anum{'first'}->[7] = 'A000566'; # 7 heptagonal n(5n-3)/2
120             $oeis_anum{'both'}->[7] = 'A085787';
121             # OEIS-Catalogue: A000566 polygonal=7
122             # OEIS-Catalogue: A085787 polygonal=7 pairs=both
123             #
124             # Not quite, (5n-2)(n-1)/2 starting n=1 is the same values, whereas
125             # Polygonal seconds starting n=0 would be (-n)(5*-n-3)/2=n(5n+3)
126             # # $oeis_anum{'second'}->[7] = 'A147875'; # (5n-2)(n-1)/2
127             # # # OEIS-Catalogue: A147875 polygonal=7 pairs=second
128              
129             $oeis_anum{'first'}->[8] = 'A000567'; # 8 octagonal
130             $oeis_anum{'second'}->[8] = 'A045944'; # Rhombic matchstick n*(3*n+2)
131             # OEIS-Catalogue: A000567 polygonal=8
132             # OEIS-Catalogue: A045944 polygonal=8 pairs=second
133             #
134             # A001082 n(3n-4)/4 if n even, (n-1)(3n+1)/4 if n odd
135             # is not quite generalized octagonals
136             # Generalized would be n*(3n-2) for n=0,1,-1,2,-2,etc
137             # # $oeis_anum{'both'}->[8] = 'A001082';
138             # # # OEIS-Catalogue: A001082 polygonal=8 pairs=both
139              
140             $oeis_anum{'first'}->[9] = 'A001106'; # 9 nonagonal
141             $oeis_anum{'second'}->[9] = 'A179986'; # 9 nonagonal second n*(7*n+5)/2
142             $oeis_anum{'both'}->[9] = 'A118277'; # 9 nonagonal "generalized"
143             # OEIS-Catalogue: A001106 polygonal=9
144             # OEIS-Catalogue: A179986 polygonal=9 pairs=second
145             # OEIS-Catalogue: A118277 polygonal=9 pairs=both
146              
147             $oeis_anum{'first'}->[10] = 'A001107'; # 10 decogaonal
148             $oeis_anum{'second'}->[10] = 'A033954'; # 10 second n*(4*n+3)
149             $oeis_anum{'both'}->[10] = 'A074377'; # 10 both "generalized"
150             # OEIS-Catalogue: A001107 polygonal=10
151             # OEIS-Catalogue: A033954 polygonal=10 pairs=second
152             # OEIS-Catalogue: A074377 polygonal=10 pairs=both
153              
154             $oeis_anum{'first'}->[11] = 'A051682'; # 11 hendecagonal
155             $oeis_anum{'second'}->[11] = 'A062728'; # 11 second n*(9n+7)/2
156             $oeis_anum{'both'}->[11] = 'A195160'; # 11 generalized
157             # OEIS-Catalogue: A051682 polygonal=11
158             # OEIS-Catalogue: A062728 polygonal=11 pairs=second
159             # OEIS-Catalogue: A195160 polygonal=11 pairs=both
160              
161             $oeis_anum{'first'}->[12] = 'A051624'; # 12-gonal
162             $oeis_anum{'second'}->[12] = 'A135705'; # 12-gonal second
163             $oeis_anum{'both'}->[12] = 'A195162'; # 12-gonal generalized
164             # OEIS-Catalogue: A051624 polygonal=12
165             # OEIS-Catalogue: A135705 polygonal=12 pairs=second
166             # OEIS-Catalogue: A195162 polygonal=12 pairs=both
167              
168             $oeis_anum{'second'}->[13] = 'A211013'; # 13-gonal second
169             $oeis_anum{'both'}->[13] = 'A195313'; # 13-gonal generalized
170             # OEIS-Catalogue: A211013 polygonal=13 pairs=second
171             # OEIS-Catalogue: A195313 polygonal=13 pairs=both
172              
173             $oeis_anum{'second'}->[14] = 'A211014'; # 14-gonal second
174             $oeis_anum{'both'}->[14] = 'A195818'; # 14-gonal generalized
175             # OEIS-Catalogue: A211014 polygonal=14 pairs=second
176             # OEIS-Catalogue: A195818 polygonal=14 pairs=both
177              
178             # these in sequence ...
179             $oeis_anum{'first'}->[13] = 'A051865'; # 13 tridecagonal
180             $oeis_anum{'first'}->[14] = 'A051866'; # 14-gonal
181             $oeis_anum{'first'}->[15] = 'A051867'; # 15
182             $oeis_anum{'first'}->[16] = 'A051868'; # 16
183             $oeis_anum{'first'}->[17] = 'A051869'; # 17
184             $oeis_anum{'first'}->[18] = 'A051870'; # 18
185             $oeis_anum{'first'}->[19] = 'A051871'; # 19
186             $oeis_anum{'first'}->[20] = 'A051872'; # 20
187             $oeis_anum{'first'}->[21] = 'A051873'; # 21
188             $oeis_anum{'first'}->[22] = 'A051874'; # 22
189             $oeis_anum{'first'}->[23] = 'A051875'; # 23
190             $oeis_anum{'first'}->[24] = 'A051876'; # 24
191             # OEIS-Catalogue: A051865 polygonal=13
192             # OEIS-Catalogue: A051866 polygonal=14
193             # OEIS-Catalogue: A051867 polygonal=15
194             # OEIS-Catalogue: A051868 polygonal=16
195             # OEIS-Catalogue: A051869 polygonal=17
196             # OEIS-Catalogue: A051870 polygonal=18
197             # OEIS-Catalogue: A051871 polygonal=19
198             # OEIS-Catalogue: A051872 polygonal=20
199             # OEIS-Catalogue: A051873 polygonal=21
200             # OEIS-Catalogue: A051874 polygonal=22
201             # OEIS-Catalogue: A051875 polygonal=23
202             # OEIS-Catalogue: A051876 polygonal=24
203              
204             # A161935 (n+1)*(13*n+1) gives the 28-gonals starting from i=1, ie. the n
205             # has an extra +1
206              
207             $oeis_anum{'second'}->[30] = 'A195028';
208             # OEIS-Catalogue: A195028 polygonal=30 pairs=second # 30 second
209              
210             $oeis_anum{'average'}->[6] = 'A001105'; # (k-2)/2==2 is 2*n^2
211             # OEIS-Catalogue: A001105 polygonal=6 pairs=average
212              
213             $oeis_anum{'average'}->[8] = 'A033428'; # (k-2)/2==3 is 3*squares
214             # OEIS-Catalogue: A033428 polygonal=8 pairs=average
215              
216             $oeis_anum{'average'}->[10] = 'A016742'; # (k-2)/2==4 is 4*squares
217             # OEIS-Catalogue: A016742 polygonal=10 pairs=average
218              
219             $oeis_anum{'average'}->[12] = 'A033429'; # (k-2)/2==5 is 5*squares
220             # OEIS-Catalogue: A033429 polygonal=12 pairs=average
221              
222             $oeis_anum{'average'}->[14] = 'A033581'; # (k-2)/2==6 is 6*squares
223             # OEIS-Catalogue: A033581 polygonal=14 pairs=average
224              
225             $oeis_anum{'average'}->[16] = 'A033582'; # (k-2)/2==7 is 7*squares
226             # OEIS-Catalogue: A033582 polygonal=16 pairs=average
227              
228             $oeis_anum{'second'}->[18] = 'A139278';
229             $oeis_anum{'average'}->[18] = 'A139098'; # (k-2)/2==8 is 8*squares
230             # OEIS-Catalogue: A139278 polygonal=18 pairs=second
231             # OEIS-Catalogue: A139098 polygonal=18 pairs=average
232              
233             $oeis_anum{'average'}->[20] = 'A016766'; # (k-2)/2==9 is 9*squares
234             # OEIS-Catalogue: A016766 polygonal=20 pairs=average
235              
236             $oeis_anum{'average'}->[22] = 'A033583'; # (k-2)/2==10 is 10*squares
237             # OEIS-Catalogue: A033583 polygonal=22 pairs=average
238              
239             $oeis_anum{'average'}->[24] = 'A033584'; # (k-2)/2==11 is 11*squares
240             # OEIS-Catalogue: A033584 polygonal=24 pairs=average
241              
242             $oeis_anum{'average'}->[26] = 'A135453'; # (k-2)/2==12 is 12*squares
243             # OEIS-Catalogue: A135453 polygonal=26 pairs=average
244              
245             $oeis_anum{'average'}->[28] = 'A152742'; # (k-2)/2==13 is 13*squares
246             # OEIS-Catalogue: A152742 polygonal=28 pairs=average
247              
248             $oeis_anum{'average'}->[30] = 'A144555'; # (k-2)/2==14 is 14*squares
249             # OEIS-Catalogue: A144555 polygonal=30 pairs=average
250              
251             $oeis_anum{'average'}->[32] = 'A064761'; # (k-2)/2==15 is 15*squares
252             # OEIS-Catalogue: A064761 polygonal=32 pairs=average
253              
254             $oeis_anum{'average'}->[34] = 'A016802'; # (k-2)/2==16 is 16*squares
255             # OEIS-Catalogue: A016802 polygonal=34 pairs=average
256              
257             $oeis_anum{'average'}->[290] = 'A017522'; # (k-2)/2==290 is 144*squares (12n)^2
258             # OEIS-Catalogue: A017522 polygonal=290 pairs=average
259              
260              
261             sub oeis_anum {
262 15     15 1 76 my ($self) = @_;
263 15         70 return $oeis_anum{$self->{'pairs'}}->[$self->{'k'}];
264             }
265              
266             #------------------------------------------------------------------------------
267              
268             # ($k-2)*$i*($i+1)/2 - ($k-3)*$i
269             # = ($k-2)/2*$i*i + ($k-2)/2*$i - ($k-3)*$i
270             # = ($k-2)/2*$i*i + ($k - 2 - 2*$k + 6)/2*$i
271             # = ($k-2)/2*$i*i + (-$k + 4)/2*$i
272             # = 0.5 * (($k-2)*$i*i + (-$k +4)*$i)
273             # = 0.5 * $i * (($k-2)*$i - $k + 4)
274              
275             # 25*i*(i+1)/2 - 24i
276             # 25*i*(i+1)/2 - 48i/2
277             # i/2*(25*(i+1) - 48)
278             # i/2*(25*i + 25 - 48)
279             # i/2*(25*i - 23)
280             #
281             # P(i) = (k-2)/2 * i*(i+1) - (k-3)*i
282             # S(i) = (k-2)/2 * i*(i-1) + (k-3)*i
283             # P(i)-S(i)
284             # = (k-2)/2 * i*(i+1) - (k-3)*i - [ (k-2)/2 * i*(i-1) + (k-3)*i ]
285             # = (k-2)/2 * [ i*(i+1) - i*(i-1) ] - (k-3)*i - (k-3)*i
286             # = (k-2)/2 * [ i*i+i - (i*i-i) ] - 2*(k-3)*i
287             # = (k-2)/2 * [ i*i+i - i*i + i ] - 2*(k-3)*i
288             # = (k-2)/2 * [ i + i ] - 2*(k-3)*i
289             # = (k-2)/2 * 2*i] - 2*(k-3)*i
290             # = 2*i * [ (k-2)/2 - (k-3) ]
291             # = 2*i * [ (k-2) - (2k-6) ] / 2
292             # = i * [ -k + 4 ] / 2
293             # = i * (4-k) / 2
294             #
295             # average
296             # (P(i) + S(i)) / 2
297             # = [ (k-2)/2 * i*(i+1) - (k-3)*i + (k-2)/2 * i*(i-1) + (k-3)*i ] / 2
298             # = [ (k-2)/2 * i*(i+1) + (k-2)/2 * i*(i-1) ] / 2
299             # = (k-2)/2 * [ i*(i+1) + i*(i-1) ] / 2
300             # = (k-2)/2 * i * [ (i+1) + (i-1) ] / 2
301             # = (k-2)/2 * i * [ 2i ] / 2
302             # = (k-2)/2 * i*i
303              
304             sub rewind {
305 45     45 1 7291 my ($self) = @_;
306              
307 45   50     164 my $k = $self->{'polygonal'} || 2;
308 45         81 my $add = 4 - $k;
309 45   50     139 my $pairs = $self->{'pairs'} || ($self->{'pairs'} = 'first');
310 45 100       145 if ($k >= 5) {
311 39 100       172 if ($pairs eq 'second') {
    100          
    100          
312 3         8 $add = - $add;
313             } elsif ($pairs eq 'both') {
314 3         6 $add = - abs($add);
315             } elsif ($pairs eq 'average') {
316 3         6 $add = 0;
317             }
318             }
319 45         84 $self->{'k'} = $k;
320 45         81 $self->{'add'} = $add;
321              
322 45         598 $self->SUPER::rewind;
323             }
324              
325             sub ith {
326 2140     2140 1 3665 my ($self, $i) = @_;
327 2140         3149 my $k = $self->{'k'};
328 2140 50       4575 if ($k < 3) {
329 0 0       0 if ($i == 0) {
330 0         0 return 1;
331             } else {
332 0         0 return undef;
333             }
334             }
335 2140         3222 my $pairs = $self->{'pairs'};
336 2140 100 100     8048 if ($k >= 5 && $pairs eq 'both') {
337 93 100       164 if ($i & 1) {
338 41         66 $i = ($i+1)/2;
339             } else {
340 52         83 $i = -$i/2;
341             }
342             }
343             ### $i
344 2140         8157 return $i * (($k-2)*$i + $self->{'add'}) / 2;
345             }
346              
347             # k=3 -1/2 + sqrt(2/1 * $n + 1/4)
348             # k=4 sqrt(2/2 * $n )
349             # k=5 1/6 + sqrt(2/3 * $n + 1/36)
350             # k=6 2/8 + sqrt(2/4 * $n + 4/64)
351             # k=7 3/10 + sqrt(2/5 * $n + 9/100)
352             # k=8 4/12 + sqrt(2/6 * $n + 1/9)
353             #
354             # i = 1/(2*(k-2)) * [k-4 + sqrt( 8*(k-2)*n + (4-k)^2 ) ]
355             #
356             # average A(i) = (k-2)/2 * i*i
357             # i*i = A*2/(k-2)
358             # i = sqrt(2A / (k-2))
359             # i = sqrt(2A * (k-2)) / (k-2)
360             # i = sqrt(8A * (k-2)) / (2*(k-2))
361             # which is add==0
362             #
363             sub pred {
364 7698     7698 1 45640 my ($self, $value) = @_;
365             ### Polygonal pred(): $value
366             ### k: $self->{'k'}
367             ### add: $self->{'add'}
368              
369 7698 100       16631 if ($value <= 0) {
370 30         90 return ($value == 0);
371             }
372              
373 7668         13451 my $k = $self->{'k'};
374 7668         11255 my $add = $self->{'add'};
375 7668         14279 my $sqrt = int(sqrt(int(8*($k-2) * $value + $add*$add)));
376              
377             ### sqrt of: (8*($k-2) * $value + $add*$add)
378              
379 7668 100       15535 if ($self->{'pairs'} eq 'both') {
380 60         175 my $i = int (($sqrt + $self->{'add'}) / (2*($k-2)));
381 60 100       248 if ($value == $i * (($k-2)*$i - $self->{'add'}) / 2) {
382 8         30 return 1;
383             }
384             }
385 7660         12785 my $i = int (($sqrt - $self->{'add'}) / (2*($k-2)));
386              
387             ### $sqrt
388             ### $i
389              
390 7660         24449 return ($value == $i * (($k-2)*$i + $self->{'add'}) / 2);
391             }
392              
393             # P(i) = (k-2)/2 * i*(i+1) - (k-3)*i
394             # P(i) ~= (k-2)/2 * i*i
395             # i ~= sqrt( P(i)*2/(k-2) )
396             #
397             sub value_to_i_estimate {
398 292     292 1 13314 my ($self, $value) = @_;
399 292 100       689 if ($value < 0) { return 0; }
  105         302  
400 187         2691 return int(sqrt(int($value)*2/($self->{'k'}-2)));
401             }
402              
403             1;
404             __END__