1Math::NumSeq::HafermanCUasrepretC(o3n)tributed Perl DocuMmaetnht:a:tNiuomnSeq::HafermanCarpet(3)
2
6 Math::NumSeq::HafermanCarpet -- bits of the Haferman carpet
7
9 use Math::NumSeq::HafermanCarpet;
10 my $seq = Math::NumSeq::HafermanCarpet->new;
11 my ($i, $value) = $seq->next;
12
14 This sequence is 0,1 bits of the Haferman carpet pattern flattened for
15 plotting in Z-Order or similar.
16 0,1,0,1,0,1,0,1,0, 0,1,0,1,0,1,0,1,0, 0,1,0,1,0,1,0,1,0, 0,..
18 starting i=0
19 When plotted in Z-Order with radix=3 the result begins as follows. At
21 a bigger size an attractive pattern of interlocking loops can be seen.
22 * * * *** * *** * * * * * * *** * *** * * * * * *
24 * ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
25 * * * *** * *** * * * * * * *** * *** * * * * * *
26 * * * * *** * * * * * * * * *** * * * * * * *
27 * ** ** ** ***** ** ** ** ** ** ** ** ***** ** ** ** ** ** ** *
28 * * * * *** * * * * * * * * *** * * * * * * *
29 * * * *** * *** * * * * * * *** * *** * * * * * *
30 * ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
31 * * * *** * *** * * * * * * *** * *** * * * * * *
32 *** * *** * * * *** * ****** * *** * * * *** * ****** * ***
33 **** ***** ** ** ***** ******** ***** ** ** ***** ******** ****
34 *** * *** * * * *** * ****** * *** * * * *** * ****** * ***
35 * *** * * * * * *** * * *** * * * * * *** * * *** *
36 * ***** ** ** ** ** ***** ** ***** ** ** ** ** ***** ** ***** *
37 * *** * * * * * *** * * *** * * * * * *** * * *** *
38 *** * *** * * * *** * ****** * *** * * * *** * ****** * ***
39 **** ***** ** ** ***** ******** ***** ** ** ***** ******** ****
40 *** * *** * * * *** * ****** * *** * * * *** * ****** * ***
41 * * * *** * *** * * * * * * *** * *** * * * * * *
42 * ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
43 * * * *** * *** * * * * * * *** * *** * * * * * *
44 * * * * *** * * * * * * * * *** * * * * * * *
45 * ** ** ** ***** ** ** ** ** ** ** ** ***** ** ** ** ** ** ** *
46 * * * * *** * * * * * * * * *** * * * * * * *
47 * * * *** * *** * * * * * * *** * *** * * * * * *
48 * ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
49 * * * *** * *** * * * * * * *** * *** * * * * * *
50 The pattern is formed by a "morphism" where each 0 or 1 bit expands to
52 a 3x3 array
53 1 1 1 0 1 0
55 0 -> 1 1 1 1 -> 1 0 1
56 1 1 1 0 1 0
57 For the purpose of this sequence those arrays are flattened so
59 0 -> 1,1,1,1,1,1,1,1,1
61 1 -> 0,1,0,1,0,1,0,1,0
62 The sequence starts from a single initial value 0. The expansion rules
64 are applied twice so as to grow that initial value to 9*9=81 values.
65 Then the rules applied to each of those values twice again to give
66 9^4=6561 values, and so on indefinitely.
67 An even number of expansion steps ensures the existing values are
69 unchanged. If an odd number of expansions were done then the first bit
70 flips 0<->1. The even number of expansions can also be expressed as
71 each bit morphing into an 81-long run.
72 0 -> 0,1,0,1,0,1,0,1,0, # 9 times repeat
74 0,1,0,1,0,1,0,1,0,
75 0,1,0,1,0,1,0,1,0,
76 ...
77 1 -> 1,1,1,1,1,1,1,1,1, # 9 times repeat
79 0,1,0,1,0,1,0,1,0, # alternate 111..111 or 010..010
80 1,1,1,1,1,1,1,1,1,
81 0,1,0,1,0,1,0,1,0,
82 ...
83 See "Ith" below for how the position of the lowest odd digit of i in
85 base-9 determines the sequence values.
86 Initial 1
88 Option "initial_value => 1" can start the sequence from a single value
89 1 instead.
90 # initial_value => 1
92 1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,...
93 When plotted in Z-Order this begins
95 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
97 **** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
98 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
99 * *** * * *** * * *** * * * * * *** * * * * * *** *
100 * ***** ** ***** ** ***** ** ** ** ** ***** ** ** ** ** ***** *
101 * *** * * *** * * *** * * * * * *** * * * * * *** *
102 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
103 **** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
104 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
105 *** * ****** * ****** * ****** * *** * * * *** * ****** * ***
106 **** ******** ******** ******** ***** ** ** ***** ******** ****
107 *** * ****** * ****** * ****** * *** * * * *** * ****** * ***
108 * *** * * *** * * *** * * *** * * * * * *** * * *** *
109 * ***** ** ***** ** ***** ** ***** ** ** ** ** ***** ** ***** *
110 * *** * * *** * * *** * * *** * * * * * *** * * *** *
111 *** * ****** * ****** * ****** * *** * * * *** * ****** * ***
112 **** ******** ******** ******** ***** ** ** ***** ******** ****
113 *** * ****** * ****** * ****** * *** * * * *** * ****** * ***
114 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
115 **** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
116 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
117 * *** * * *** * * *** * * * * * *** * * * * * *** *
118 * ***** ** ***** ** ***** ** ** ** ** ***** ** ** ** ** ***** *
119 * *** * * *** * * *** * * * * * *** * * * * * *** *
120 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
121 **** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
122 *** * ****** * ****** * *** * * * *** * *** * * * *** * ***
123 This form has some 1s where the initial_value=0 had 0s. The positions
125 of these extra 1s are the box fractal.
126 * * * * * * * *
128 * * * *
129 * * * * * * * *
130 * * * *
131 * *
132 * * * *
133 * * * * * * * *
134 * * * *
135 * * * * * * * *
136 * * * *
137 * *
138 * * * *
139 * *
140 *
141 * *
142 * * * *
143 * *
144 * * * *
145 * * * * * * * *
146 * * * *
147 * * * * * * * *
148 * * * *
149 * *
150 * * * *
151 * * * * * * * *
152 * * * *
153 * * * * * * * *
154 Inverse
156 The "inverse => 1" option (a boolean) can invert the 0,1 bits to
157 instead 1,0. This can be applied to any of the types. For example on
158 the default initial_value=0,
159 # inverse => 1
161 1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,...
162 Plotting Order
164 The Z-Order curve (per for example Math::PlanePath::ZOrderCurve)
165 numbers its sub-parts
166 +---+---+---+
168 | 6 | 7 | 8 |
169 +---+---+---+
170 | 3 | 4 | 5 |
171 +---+---+---+
172 | 0 | 1 | 2 |
173 +---+---+---+
174 This suits the sequence here because the numbering is alternately odd
176 and even in adjacent sub-parts,
177 +------+------+------+
179 | even | odd | even |
180 +------+------+------+
181 | odd | even | odd |
182 +------+------+------+
183 | even | odd | even |
184 +------+------+------+
185 Any self-similar expansion which numbers by an odd/even alternation
187 like this gives the same result. This includes the Peano curve,
188 Wunderlich's serpentine and meander, Haverkort's Kochel curve, and
189 reflected Gray code path (radix=3).
190 Incidentally, drawing each pixel by this sequence is not very
192 efficient. It's much faster to follow the array expansions described
193 above and block copy areas of "0" or "1". An initial single pixel 0
194 expands to 3x3 then 9x9, etc. Two images representing a "0" or a "1"
195 can be maintained, though with care some copying of sub-parts allows
196 just one image to be built up. See
197 examples/other/haferman-carpet-x11.pl in the Math-NumSeq sources for
198 some code doing that.
199
201 See "FUNCTIONS" in Math::NumSeq for the behaviour common to all path
202 classes.
203 "$seq = Math::NumSeq::HafermanCarpet->new (initial_value => $integer,
205 inverse => $bool)"
206 Create and return a new sequence object. "initial_value" can be 0
207 or 1.
208 Random Access
210 "$value = $seq->ith($i)"
211 Return the $i'th value from the sequence.
212
214 Ith
215 The effect of the morphism described above is to find the least
216 significant odd digit 1,3,5,7 when i is written in base-9.
217 i lowest base-9
219 digit 1,3,5,7 value
220 -------------- -------------
221 even position 1
222 odd position 0
223 no such digit initial_value
224 Position counted from low end.
226 Least significant digit is position=0 so is an "even position".
227 For example i=609 is base-9 "746" and its lowest odd digit is the "7"
229 which is 2 digits from the low end and thus an "even position" and so
230 value=1.
231 Or i=357 is base-9 "436" and its lowest odd digit is the "3" which is 1
233 digit from the low end and thus an "odd position" so value=0.
234 If i contains no odd base-9 digits at all then it's "no such digit" and
236 the result is the "initial_value". For example i=58 is base-9 "64"
237 which has no odd digits so value=0 in the default "initial_value=0".
238 These i with no odd base-9 digit are the box fractal pattern shown
239 above which are the places where initial_value 0 or 1 changes the
240 sequence value.
241 "Position of lowest odd base-9 digit" can also be thought of as "count
243 trailing even base-9 digits". If i is entirely even digits then that
244 count should be reckoned as infinite by imagining 0 digits extending
245 infinitely at the high end of i. That "infinite" case is then the "no
246 such digit" of the table.
247 The value assigned to the three cases odd,even,none can each be 0 or 1
249 for a total 8 combinations. The cases above are 1,0,0 and 1,0,1 and
250 their 1<->0 inverses 0,1,1 and 0,1,0 per the "inverse" option are the
251 four most intersting combinations. The box fractal 0,0,1 and its
252 inverse 1,1,0 are interesting but not generated by the code here. The
253 remaining two 0,0,0 which is all zeros or 1,1,1 all ones are not very
254 interesting.
255 Density
257 The number of 1s in the first 9^k many values from the sequence is as
258 follows.
259 9^(k+1) - (2*(-1)^k + 7) * 5^k
261 Seq1s_init0(k) = ------------------------------
262 14
263 and for initial_value=1
265 9^(k+1) - (2*(-1)^k - 7) * 5^k
267 Seq1s_init1(k) = ------------------------------
268 14
269 The difference between the two is 5^k,
271 Seq1s_init1 = Seq1s_init0 + 5^k
273 This difference is the box fractal 1s described above which are gained
275 in the initial_value=1 form. They're at positions where i has only
276 even digits 0,2,4,6,8 in base 9, so 5 digit possibilities at each of k
277 many digit positions giving 5^k.
278 The formulas can be calculated by considering how the 0s and 1s expand.
280 The array morphism form with initial_value=1 is given by Eric
281 Weinstein,
282 <http://mathworld.wolfram.com/HafermanCarpet.html>,
284 <http://oeis.org/A118005>
285 Each point expands
287 0 -> 9 of 1s
289 1 -> 4 of 1s plus 5 of 0s
290 The 1s in the expanded form are therefore 9 from each existing "0" and
292 4 from each existing "1". Since 0s+1s = 9^k this can be expressed in
293 terms of Array1s.
294 Array1s(k+1) = 4*Array1s(k) + 9*Array0s(k)
296 = 4*Array1s(k) + 9*(9^k - Array1s(k)) # 0s+1s=9^k
297 = 9^(k+1) - 5*Array1s(k)
298 Expanding this recurrence repeatedly gives
300 Array1s(k) = 5^0 * 9^k
302 - 5^1 * 9^(k-1)
303 + 5^2 * 9^(k-2)
304 ...
305 - (-5)^(k-1) * 9^1
306 - (-5)^k * 9^0 * Array1s(0)
307 The alternating signs in each term are -5 as the increasing power.
309 Since Array1s(0)=1 the last term is included and the powers sum as
310 follows in the usual way.
311 9^(k+1) - (-5)^(k+1)
313 Array1s_init1(k) = --------------------
314 9 - (-5)
315 If the initial starting cell is 0 instead of 1 then Array1s(0)=0 and
317 the last term (-1)^k * 5^k is omitted. Subtracting that leaves
318 9^(k+1) - 9*(-5)^k
320 Array1s_init0(k) = ------------------
321 9 - (-5)
322 For the sequence forms here the initial value does not change, unlike
324 the array alternating 0<->1. The sequence takes the array starting 0
325 or 1 according as k is even or odd, thereby ensuring the first value is
326 0. So,
327 Seq1s_init0(k) = / Array1s_init0(k) if k even
329 \ Array1s_init1(k) if k odd
330 The term (2*(-1)^k - 7) seen above in the Seq1s_init0() formula selects
332 between 9 or 5 as the multiplier for (-5)^k. That 9 or 5 multiplier is
333 the difference between the two Array1s forms.
334
336 Math::NumSeq
337 Math::PlanePath::ZOrderCurve, Math::PlanePath::PeanoCurve,
339 Math::PlanePath::WunderlichSerpentine, Math::PlanePath::KochelCurve,
340 Math::PlanePath::GrayCode, Math::PlanePath::SquareReplicate
341 examples/other/haferman-carpet-x11.pl in the Math-NumSeq sources draws
343 the carpet interactively with "X11::Protocol".
344
346 <http://user42.tuxfamily.org/math-numseq/index.html>
347
349 Copyright 2013, 2014 Kevin Ryde
350 Math-NumSeq is free software; you can redistribute it and/or modify it
352 under the terms of the GNU General Public License as published by the
353 Free Software Foundation; either version 3, or (at your option) any
354 later version.
355 Math-NumSeq is distributed in the hope that it will be useful, but
357 WITHOUT ANY WARRANTY; without even the implied warranty of
358 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
359 General Public License for more details.
360 You should have received a copy of the GNU General Public License along
362 with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
363perl v5.28.1 2014-12-30 Math::NumSeq::HafermanCarpet(3)