1Math::NumSeq::HafermanCUasrepretC(o3n)tributed Perl DocuMmaetnht:a:tNiuomnSeq::HafermanCarpet(3)
2
3
4

NAME

6       Math::NumSeq::HafermanCarpet -- bits of the Haferman carpet
7

SYNOPSIS

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

DESCRIPTION

14       This sequence is 0,1 bits of the Haferman carpet pattern flattened for
15       plotting in Z-Order or similar.
16
17           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
20       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
23            *  *  * *** * *** *  *  *  *  *  * *** * *** *  *  *  *  *  *
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
51       The pattern is formed by a "morphism" where each 0 or 1 bit expands to
52       a 3x3 array
53
54                 1  1  1             0  1  0
55           0 ->  1  1  1       1 ->  1  0  1
56                 1  1  1             0  1  0
57
58       For the purpose of this sequence those arrays are flattened so
59
60           0  -> 1,1,1,1,1,1,1,1,1
61           1  -> 0,1,0,1,0,1,0,1,0
62
63       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
68       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
73           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
78           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
84       See "Ith" below for how the position of the lowest odd digit of i in
85       base-9 determines the sequence values.
86
87   Initial 1
88       Option "initial_value => 1" can start the sequence from a single value
89       1 instead.
90
91           # 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
94       When plotted in Z-Order this begins
95
96           *** * ****** * ****** * *** *  *  * *** * *** *  *  * *** * ***
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
124       This form has some 1s where the initial_value=0 had 0s.  The positions
125       of these extra 1s are the box fractal.
126
127           * *   * *         * *   * *
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
155   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
160           # 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
163   Plotting Order
164       The Z-Order curve (per for example Math::PlanePath::ZOrderCurve)
165       numbers its sub-parts
166
167           +---+---+---+
168           | 6 | 7 | 8 |
169           +---+---+---+
170           | 3 | 4 | 5 |
171           +---+---+---+
172           | 0 | 1 | 2 |
173           +---+---+---+
174
175       This suits the sequence here because the numbering is alternately odd
176       and even in adjacent sub-parts,
177
178           +------+------+------+
179           | even | odd  | even |
180           +------+------+------+
181           | odd  | even | odd  |
182           +------+------+------+
183           | even | odd  | even |
184           +------+------+------+
185
186       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
191       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

FUNCTIONS

200       See "FUNCTIONS" in Math::NumSeq for the behaviour common to all path
201       classes.
202
203       "$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
208   Random Access
209       "$value = $seq->ith($i)"
210           Return the $i'th value from the sequence.
211

FORMULAS

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
217           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
224           Position counted from low end.
225           Least significant digit is position=0 so is an "even position".
226
227       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
231       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
234       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
241       "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
247       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
255   Density
256       The number of 1s in the first 9^k many values from the sequence is as
257       follows.
258
259                            9^(k+1) - (2*(-1)^k + 7) * 5^k
260           Seq1s_init0(k) = ------------------------------
261                                          14
262
263       and for initial_value=1
264
265                            9^(k+1) - (2*(-1)^k - 7) * 5^k
266           Seq1s_init1(k) = ------------------------------
267                                         14
268
269       The difference between the two is 5^k,
270
271           Seq1s_init1 = Seq1s_init0 + 5^k
272
273       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
278       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
282           <http://mathworld.wolfram.com/HafermanCarpet.html>,
283           <http://oeis.org/A118005>
284
285       Each point expands
286
287           0 -> 9 of 1s
288           1 -> 4 of 1s plus 5 of 0s
289
290       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
294           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
298       Expanding this recurrence repeatedly gives
299
300           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
307       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
311                              9^(k+1) - (-5)^(k+1)
312           Array1s_init1(k) = --------------------
313                                    9 - (-5)
314
315       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
318                              9^(k+1) - 9*(-5)^k
319           Array1s_init0(k) = ------------------
320                                   9 - (-5)
321
322       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
327           Seq1s_init0(k) = /  Array1s_init0(k)   if k even
328                            \  Array1s_init1(k)   if k odd
329
330       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

SEE ALSO

335       Math::NumSeq
336
337       Math::PlanePath::ZOrderCurve, Math::PlanePath::PeanoCurve,
338       Math::PlanePath::WunderlichSerpentine, Math::PlanePath::KochelCurve,
339       Math::PlanePath::GrayCode, Math::PlanePath::SquareReplicate
340
341       examples/other/haferman-carpet-x11.pl draws the carpet interactively
342       with "X11::Protocol".
343

HOME PAGE

345       <http://user42.tuxfamily.org/math-numseq/index.html>
346

LICENSE

348       Copyright 2013, 2014, 2016, 2017, 2019 Kevin Ryde
349
350       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
355       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
360       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/>.
362
363
364
365perl v5.32.0                      2020-07-28   Math::NumSeq::HafermanCarpet(3)
Impressum