File Coverage

blib/lib/Math/NumSeq/UlamSequence.pm
Criterion Covered Total %
statement 54 55 98.1
branch 8 10 80.0
condition n/a
subroutine 12 12 100.0
pod 3 3 100.0
total 77 80 96.2


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::UlamSequence;
19 1     1   1293 use 5.004;
  1         4  
20 1     1   4 use strict;
  1         2  
  1         21  
21              
22 1     1   4 use vars '$VERSION','@ISA';
  1         1  
  1         58  
23             $VERSION = 72;
24 1     1   4 use Math::NumSeq;
  1         1  
  1         36  
25             @ISA = ('Math::NumSeq');
26              
27             # uncomment this to run the ### lines
28             #use Smart::Comments;
29              
30              
31             # use constant name => Math::NumSeq::__('Ulam Sequence');
32 1     1   4 use constant description => Math::NumSeq::__('Ulam sequence, 1,2,3,4,6,8,11,etc starting 1,2 then each member being uniquely representable as the sum of two earlier values.');
  1         1  
  1         3  
33 1     1   3 use constant characteristic_increasing => 1;
  1         1  
  1         38  
34 1     1   3 use constant i_start => 1;
  1         1  
  1         35  
35 1     1   4 use constant values_min => 1;
  1         1  
  1         61  
36              
37 1         3 use constant parameter_info_array =>
38             [
39             { name => 'start_values',
40             display => Math::NumSeq::__('Start Values'),
41             type => 'string',
42             width => 5,
43             default => '1,2',
44             choices => ['1,2', '1,3', '1,4', '1,5',
45             '2,3', '2,4', '2,5'],
46             description => Math::NumSeq::__('Starting values for the sequence.'),
47             },
48 1     1   4 ];
  1         1  
49              
50             my %oeis_anum = ('1,2' => 'A002858',
51             '1,3' => 'A002859',
52             '1,4' => 'A003666',
53             '1,5' => 'A003667',
54             '2,3' => 'A001857',
55             '2,4' => 'A048951',
56             '2,5' => 'A007300',
57              
58             # OEIS-Catalogue: A002858 start_values=1,2
59             # OEIS-Catalogue: A002859 start_values=1,3
60             # OEIS-Catalogue: A003666 start_values=1,4
61             # OEIS-Catalogue: A003667 start_values=1,5
62             # OEIS-Catalogue: A001857 start_values=2,3
63             # OEIS-Catalogue: A048951 start_values=2,4
64             # OEIS-Catalogue: A007300 start_values=2,5
65             );
66             sub oeis_anum {
67 1     1 1 4 my ($self) = @_;
68 1         2 (my $key = $self->{'start_values'}) =~ tr/ \t//d;
69 1         2 return $oeis_anum{$key};
70             }
71              
72             # each 2-bit vec() value is
73             # 0 not a sum
74             # 1 sum one
75             # 2 sum two or more
76             # 3 (unused)
77              
78             my @transform = (0, 0, 1, -1);
79              
80             sub rewind {
81 3     3 1 508 my ($self) = @_;
82 3         16 $self->{'i'} = $self->i_start;
83 3         7 $self->{'upto'} = 0;
84 3         6 $self->{'string'} = '';
85              
86             ### start_values: $self->{'start_values'}
87 3         4 my $max = -1;
88 3         30 foreach my $value (split /(?:\s|,)+/, $self->{'start_values'}) {
89             ### $value
90 6         21 vec($self->{'string'}, $value, 2) = 1;
91 6 50       15 if ($value > $max) { $max = $value; }
  6         8  
92             }
93 3         11 $self->{'max'} = $max;
94             }
95              
96             # 0 => 1
97             # 1 => 2
98             # 2 => 2
99             my @incr = (1,2,2);
100              
101             sub next {
102 22     22 1 568 my ($self) = @_;
103              
104 22         18 my $upto = $self->{'upto'};
105 22         20 my $sref = \$self->{'string'};
106              
107 22         12 for (;;) {
108 52         37 $upto++;
109 52         30 my $entry = vec($$sref, $upto,2);
110             ### $upto
111             ### $entry
112 52 100       78 if ($entry == 1) {
    50          
113 22         17 my $max;
114 22         30 foreach my $i (1 .. $upto-1) {
115 194 100       218 if (vec($$sref, $i,2) == 1) {
116 110         132 vec($$sref, $i+$upto,2) = $incr[vec($$sref, $i+$upto,2)];
117 110         105 $max = $i+$upto;
118             }
119             }
120 22 100       28 if ($max) {
121 20         15 $self->{'max'} = $max;
122             }
123 22         36 return ($self->{'i'}++, ($self->{'upto'} = $upto));
124              
125             } elsif ($upto > $self->{'max'}) {
126 0           return;
127             }
128             }
129             }
130              
131             1;
132             __END__