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__ |