1Math::NumSeq::GolayRudiUnsSehrapCiornotCruimbuuMltaaettdhi:vP:eeN(ru3lm)SDeoqc:u:mGeonltaaytRiuodninShapiroCumulative(3)
2
3
4

NAME

6       Math::NumSeq::GolayRudinShapiroCumulative -- cumulative
7       Golay/RudinShapiro sequence
8

SYNOPSIS

10        use Math::NumSeq::GolayRudinShapiroCumulative;
11        my $seq = Math::NumSeq::GolayRudinShapiroCumulative->new;
12        my ($i, $value) = $seq->next;
13

DESCRIPTION

15       This is the Golay/Rudin/Shapiro sequence values accumulated as
16       GRS(0)+...+GRS(i),
17
18           starting from i=0 value=GRS(0)
19
20           1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ...
21
22       The total is always positive, and in fact a given cumulative total k
23       occurs precisely k times (per Brillhart and Morton).  For example the
24       three occurrences of 3 shown above are all the places 3 occurs.
25
26       This GRS cumulative arises as in the alternate paper folding curve as
27       the coordinate sum X+Y.  The way k occurs k many times has a geometric
28       interpretation as the points on the diagonal X+Y=k of the curve visited
29       a total of k many times.  See "dSum" in
30       Math::PlanePath::AlternatePaper.
31

FUNCTIONS

33       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
34       classes.
35
36       "$seq = Math::NumSeq::GolayRudinShapiroCumulative->new ()"
37           Create and return a new sequence object.
38
39   Random Access
40       "$value = $seq->ith($i)"
41           Return the $i'th value from the sequence, being the total
42           "GRS(0)+GRS(1)+...+GRS($i)".
43
44       "$bool = $seq->pred($value)"
45           Return true if $value occurs in the sequence.  All positive
46           integers occur, so this simply means integer "$value >= 1".
47

FORMULAS

49   Ith
50       The cumulative total GRS(0)+...+GRS(i-1) can be calculated from the
51       1-bits of i.  Each 1-bit becomes a value 2^floor((pos+1)/2) in the
52       total,
53
54           pos    value
55           ---    -----
56            0       1
57            1       2
58            2       2
59            3       4
60            4       4
61           ...     ...
62            k      2^ceil(k/2)
63
64       The value is added or subtracted from the total according to the number
65       of 11 bit pairs above that bit position, not including the bit itself,
66
67           add value    if even count of adjacent 11 bit pairs above
68           sub value    if odd count
69
70       For example i=27 is 110011 in binary so
71
72           1      -1      bit0 low bit
73           1      -2      bit1
74           0              bit2
75           1      +4      bit3
76           1      +4      bit4 high bit
77                 ----
78                   5      cumulative value GRS(0)+...+GRS(26)
79
80       The second lowest bit is negated as value -2 because there's one "11"
81       bit pair above it, and -1 the same because above and not including that
82       bit there's just one "11" bit pair.
83
84       Or for example i=31 is 11111 in binary so
85
86           1      -1      bit0 low bit
87           1      +2      bit1
88           1      -2      bit2
89           1      +4      bit3
90           1      +4      bit4 high bit
91                 ----
92                   7      cumulative total GRS(0)+...+GRS(30)
93
94       Here at bit2 the value is -2 because there's one adjacent 11 above, not
95       including bit2 itself.  Then at pos=1 there's two 11 pairs above so +2,
96       and at pos=0 there's three so -1.
97
98       The total can be formed by examining the bits high to low and counting
99       adjacent 11 bits on the way down to add or subtract.  Or it can be
100       formed from low to high by negating the total so far when a 11 pair is
101       encountered.
102
103       For an inclusive sum GRS(0)+...+GRS(i) as per this module, the extra
104       GRS(i) can be worked into the calculation by its GRS definition +1 or
105       -1 according to the total number of adjacent 11 bits.  This can be
106       thought of as an extra value 1 below the least significant bit.  For
107       example i=27 inclusive
108
109                  +1      below all bits
110           1      -1      bit0 low bit
111           1      -2      bit1
112           0              bit2
113           1      +4      bit3
114           1      +4      bit4 high bit
115                 ----
116                   5      cumulative value GRS(0)+...+GRS(27)
117
118       For low to high calculation, this lowest +/-1 can be handled simply by
119       starting the total at 1.  It then becomes +1 or -1 by the negations as
120       11s are encountered for the rest of the bit handling.
121
122           total = 1   # initial value below all bits to be inclusive GRS(i)
123           power = 1   # 2^ceil(bitpos/2)
124           thisbit = take bit from low end of i
125
126           loop
127             nextbit = take bit from low end of i
128             if thisbit&&nextbit
129               then total = -total    # negate lower values added
130             if thisbit
131               then total += power
132             thisbit = nextbit
133
134             power *= 2
135             exit loop if i==0
136
137             nextbit = bit from low end of i
138             if thisbit&&nextbit
139               then total = -total    # negate lower values added
140             if thisbit
141               then total += power
142             thisbit = nextbit
143             exit loop if i==0
144           endloop
145
146           total += power     # final for highest 1-bit in i
147           # total=GRS(0)+...+GRS(i)
148
149       This sort of calculation arises implicitly in the alternate paper
150       folding curve to calculate X,Y for a given N point on the curve.  Bits
151       of the cumulative GRS can be generated from base 4 digits of 2*N.  See
152       the author's alternate paperfolding curve write-up for some more
153       ("GRScumul" in the index)
154
155           <http://user42.tuxfamily.org/alternate/index.html>
156

SEE ALSO

158       Math::NumSeq, Math::NumSeq::GolayRudinShapiro
159
160       Math::PlanePath::AlternatePaper
161

HOME PAGE

163       <http://user42.tuxfamily.org/math-numseq/index.html>
164

LICENSE

166       Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde
167
168       Math-NumSeq is free software; you can redistribute it and/or modify it
169       under the terms of the GNU General Public License as published by the
170       Free Software Foundation; either version 3, or (at your option) any
171       later version.
172
173       Math-NumSeq is distributed in the hope that it will be useful, but
174       WITHOUT ANY WARRANTY; without even the implied warranty of
175       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
176       General Public License for more details.
177
178       You should have received a copy of the GNU General Public License along
179       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
180
181
182
183perl v5.36.0                      2M0a2t2h-:0:7N-u2m2Seq::GolayRudinShapiroCumulative(3)
Impressum