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 for some code doing that.
198
200 See "FUNCTIONS" in Math::NumSeq for the behaviour common to all path
201 classes.
202 "$seq = Math::NumSeq::HafermanCarpet->new (initial_value => $integer,
204 inverse => $bool)"
205 Create and return a new sequence object. "initial_value" can be 0
206 or 1.
207 Random Access
209 "$value = $seq->ith($i)"
210 Return the $i'th value from the sequence.
211
213 Ith
214 The effect of the morphism described above is to find the least
215 significant odd digit 1,3,5,7 when i is written in base-9.
216 i lowest base-9
218 digit 1,3,5,7 value
219 -------------- -------------
220 even position 1
221 odd position 0
222 no such digit initial_value
223 Position counted from low end.
225 Least significant digit is position=0 so is an "even position".
226 For example i=609 is base-9 "746" and its lowest odd digit is the "7"
228 which is 2 digits from the low end and thus an "even position" and so
229 value=1.
230 Or i=357 is base-9 "436" and its lowest odd digit is the "3" which is 1
232 digit from the low end and thus an "odd position" so value=0.
233 If i contains no odd base-9 digits at all then it's "no such digit" and
235 the result is the "initial_value". For example i=58 is base-9 "64"
236 which has no odd digits so value=0 in the default "initial_value=0".
237 These i with no odd base-9 digit are the box fractal pattern shown
238 above which are the places where initial_value 0 or 1 changes the
239 sequence value.
240 "Position of lowest odd base-9 digit" can also be thought of as "count
242 trailing even base-9 digits". If i is entirely even digits then that
243 count should be reckoned as infinite by imagining 0 digits extending
244 infinitely at the high end of i. That "infinite" case is then the "no
245 such digit" of the table.
246 The value assigned to the three cases odd,even,none can each be 0 or 1
248 for a total 8 combinations. The cases above are 1,0,0 and 1,0,1 and
249 their 1<->0 inverses 0,1,1 and 0,1,0 per the "inverse" option are the
250 four most intersting combinations. The box fractal 0,0,1 and its
251 inverse 1,1,0 are interesting but not generated by the code here. The
252 remaining two 0,0,0 which is all zeros or 1,1,1 all ones are not very
253 interesting.
254 Density
256 The number of 1s in the first 9^k many values from the sequence is as
257 follows.
258 9^(k+1) - (2*(-1)^k + 7) * 5^k
260 Seq1s_init0(k) = ------------------------------
261 14
262 and for initial_value=1
264 9^(k+1) - (2*(-1)^k - 7) * 5^k
266 Seq1s_init1(k) = ------------------------------
267 14
268 The difference between the two is 5^k,
270 Seq1s_init1 = Seq1s_init0 + 5^k
272 This difference is the box fractal 1s described above which are gained
274 in the initial_value=1 form. They're at positions where i has only
275 even digits 0,2,4,6,8 in base 9, so 5 digit possibilities at each of k
276 many digit positions giving 5^k.
277 The formulas can be calculated by considering how the 0s and 1s expand.
279 The array morphism form with initial_value=1 is given by Eric
280 Weinstein,
281 <http://mathworld.wolfram.com/HafermanCarpet.html>,
283 <http://oeis.org/A118005>
284 Each point expands
286 0 -> 9 of 1s
288 1 -> 4 of 1s plus 5 of 0s
289 The 1s in the expanded form are therefore 9 from each existing "0" and
291 4 from each existing "1". Since 0s+1s = 9^k this can be expressed in
292 terms of Array1s.
293 Array1s(k+1) = 4*Array1s(k) + 9*Array0s(k)
295 = 4*Array1s(k) + 9*(9^k - Array1s(k)) # 0s+1s=9^k
296 = 9^(k+1) - 5*Array1s(k)
297 Expanding this recurrence repeatedly gives
299 Array1s(k) = 5^0 * 9^k
301 - 5^1 * 9^(k-1)
302 + 5^2 * 9^(k-2)
303 ...
304 - (-5)^(k-1) * 9^1
305 - (-5)^k * 9^0 * Array1s(0)
306 The alternating signs in each term are -5 as the increasing power.
308 Since Array1s(0)=1 the last term is included and the powers sum as
309 follows in the usual way.
310 9^(k+1) - (-5)^(k+1)
312 Array1s_init1(k) = --------------------
313 9 - (-5)
314 If the initial starting cell is 0 instead of 1 then Array1s(0)=0 and
316 the last term (-1)^k * 5^k is omitted. Subtracting that leaves
317 9^(k+1) - 9*(-5)^k
319 Array1s_init0(k) = ------------------
320 9 - (-5)
321 For the sequence forms here the initial value does not change, unlike
323 the array alternating 0<->1. The sequence takes the array starting 0
324 or 1 according as k is even or odd, thereby ensuring the first value is
325 0. So,
326 Seq1s_init0(k) = / Array1s_init0(k) if k even
328 \ Array1s_init1(k) if k odd
329 The term (2*(-1)^k - 7) seen above in the Seq1s_init0() formula selects
331 between 9 or 5 as the multiplier for (-5)^k. That 9 or 5 multiplier is
332 the difference between the two Array1s forms.
333
335 Math::NumSeq
336 Math::PlanePath::ZOrderCurve, Math::PlanePath::PeanoCurve,
338 Math::PlanePath::WunderlichSerpentine, Math::PlanePath::KochelCurve,
339 Math::PlanePath::GrayCode, Math::PlanePath::SquareReplicate
340 examples/other/haferman-carpet-x11.pl draws the carpet interactively
342 with "X11::Protocol".
343
345 <http://user42.tuxfamily.org/math-numseq/index.html>
346
348 Copyright 2013, 2014, 2016, 2017, 2019 Kevin Ryde
349 Math-NumSeq is free software; you can redistribute it and/or modify it
351 under the terms of the GNU General Public License as published by the
352 Free Software Foundation; either version 3, or (at your option) any
353 later version.
354 Math-NumSeq is distributed in the hope that it will be useful, but
356 WITHOUT ANY WARRANTY; without even the implied warranty of
357 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
358 General Public License for more details.
359 You should have received a copy of the GNU General Public License along
361 with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
362perl v5.32.0 2020-07-28 Math::NumSeq::HafermanCarpet(3)