1Math::NumSeq::GolayRudiUnsSehrapCiornotCruimbuuMltaaettdhi:vP:eeN(ru3lm)SDeoqc:u:mGeonltaaytRiuodninShapiroCumulative(3)
2
6 Math::NumSeq::GolayRudinShapiroCumulative -- cumulative
7 Golay/RudinShapiro sequence
8
10 use Math::NumSeq::GolayRudinShapiroCumulative;
11 my $seq = Math::NumSeq::GolayRudinShapiroCumulative->new;
12 my ($i, $value) = $seq->next;
13
15 This is the Golay/Rudin/Shapiro sequence values accumulated as
16 GRS(0)+...+GRS(i),
17 starting from i=0 value=GRS(0)
19 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ...
21 The total is always positive, and in fact a given cumulative total k
23 occurs precisely k times. For example the three occurrences of 3 shown
24 above are all the places 3 occurs.
25 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
33 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
34 classes.
35 "$seq = Math::NumSeq::GolayRudinShapiroCumulative->new ()"
37 Create and return a new sequence object.
38 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 "$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
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 bit 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 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 add value if even count of adjacent 11 bit pairs above
68 sub value if odd count
69 For example i=27 is 110011 in binary so
71 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 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 Or for example i=31 is 11111 in binary so
85 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 Here at bit2 the value is -2 because there's one adjacent 11 above, not
95 including bit2 itself. Then at bit1 there's two 11 pairs above so +2,
96 and at bit0 there's three so -1.
97 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 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 +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 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 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 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 power *= 2
135 exit loop if i==0
136 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 total += power # final for highest 1-bit in i
147 # total=GRS(0)+...+GRS(i)
148 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. But
151 that calculation does a simultaneous using the base 4 digits of N.
152 X=GRStotal(ceil(N/2))
154 Y=GRStotal(floor(N/2))
155
157 Math::NumSeq, Math::NumSeq::GolayRudinShapiro
158 Math::PlanePath::AlternatePaper
160
162 <http://user42.tuxfamily.org/math-numseq/index.html>
163
165 Copyright 2012, 2013, 2014 Kevin Ryde
166 Math-NumSeq is free software; you can redistribute it and/or modify it
168 under the terms of the GNU General Public License as published by the
169 Free Software Foundation; either version 3, or (at your option) any
170 later version.
171 Math-NumSeq is distributed in the hope that it will be useful, but
173 WITHOUT ANY WARRANTY; without even the implied warranty of
174 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
175 General Public License for more details.
176 You should have received a copy of the GNU General Public License along
178 with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
179perl v5.28.0 2M0a1t4h-:0:6N-u2m9Seq::GolayRudinShapiroCumulative(3)