NAME
Math::NumSeq::HafermanCarpet -- bits of the Haferman carpet
SYNOPSIS
use Math::NumSeq::HafermanCarpet;
my $seq = Math::NumSeq::HafermanCarpet->new;
my ($i, $value) = $seq->next;DESCRIPTION
This sequence is 0,1 bits of the Haferman carpet pattern flattened for plotting in Z-Order or similar.
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,..
starting i=0When plotted in Z-Order with radix=3 the result begins as follows. At a bigger size an attractive pattern of interlocking loops can be seen.
* * * *** * *** * * * * * * *** * *** * * * * * *
* ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
* * * *** * *** * * * * * * *** * *** * * * * * *
* * * * *** * * * * * * * * *** * * * * * * *
* ** ** ** ***** ** ** ** ** ** ** ** ***** ** ** ** ** ** ** *
* * * * *** * * * * * * * * *** * * * * * * *
* * * *** * *** * * * * * * *** * *** * * * * * *
* ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
* * * *** * *** * * * * * * *** * *** * * * * * *
*** * *** * * * *** * ****** * *** * * * *** * ****** * ***
**** ***** ** ** ***** ******** ***** ** ** ***** ******** ****
*** * *** * * * *** * ****** * *** * * * *** * ****** * ***
* *** * * * * * *** * * *** * * * * * *** * * *** *
* ***** ** ** ** ** ***** ** ***** ** ** ** ** ***** ** ***** *
* *** * * * * * *** * * *** * * * * * *** * * *** *
*** * *** * * * *** * ****** * *** * * * *** * ****** * ***
**** ***** ** ** ***** ******** ***** ** ** ***** ******** ****
*** * *** * * * *** * ****** * *** * * * *** * ****** * ***
* * * *** * *** * * * * * * *** * *** * * * * * *
* ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
* * * *** * *** * * * * * * *** * *** * * * * * *
* * * * *** * * * * * * * * *** * * * * * * *
* ** ** ** ***** ** ** ** ** ** ** ** ***** ** ** ** ** ** ** *
* * * * *** * * * * * * * * *** * * * * * * *
* * * *** * *** * * * * * * *** * *** * * * * * *
* ** ** ***** ***** ** ** ** ** ** ***** ***** ** ** ** ** ** *
* * * *** * *** * * * * * * *** * *** * * * * * *The pattern is formed by a "morphism" where each 0 or 1 bit expands to a 3x3 array
1 1 1 0 1 0
0 -> 1 1 1 1 -> 1 0 1
1 1 1 0 1 0For the purpose of this sequence those arrays are flattened so
0 -> 1,1,1,1,1,1,1,1,1
1 -> 0,1,0,1,0,1,0,1,0The sequence starts from a single initial value 0. The expansion rules are applied twice so as to grow that initial value to 9*9=81 values. Then the rules applied to each of those values twice again to give 9^4=6561 values, and so on indefinitely.
An even number of expansion steps ensures the existing values are unchanged. If an odd number of expansions were done then the first bit flips 0<->1. The even number of expansions can also be expressed as each bit morphing into an 81-long run.
0 -> 0,1,0,1,0,1,0,1,0, # 9 times repeat
0,1,0,1,0,1,0,1,0,
0,1,0,1,0,1,0,1,0,
...
1 -> 1,1,1,1,1,1,1,1,1, # 9 times repeat
0,1,0,1,0,1,0,1,0, # alternate 111..111 or 010..010
1,1,1,1,1,1,1,1,1,
0,1,0,1,0,1,0,1,0,
...See "Ith" below for how the position of the lowest odd digit of i in base-9 determines the sequence values.
Initial 1
Option initial_value => 1 can start the sequence from a single value 1 instead.
# initial_value => 1
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,...When plotted in Z-Order this begins
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
**** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
* *** * * *** * * *** * * * * * *** * * * * * *** *
* ***** ** ***** ** ***** ** ** ** ** ***** ** ** ** ** ***** *
* *** * * *** * * *** * * * * * *** * * * * * *** *
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
**** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
*** * ****** * ****** * ****** * *** * * * *** * ****** * ***
**** ******** ******** ******** ***** ** ** ***** ******** ****
*** * ****** * ****** * ****** * *** * * * *** * ****** * ***
* *** * * *** * * *** * * *** * * * * * *** * * *** *
* ***** ** ***** ** ***** ** ***** ** ** ** ** ***** ** ***** *
* *** * * *** * * *** * * *** * * * * * *** * * *** *
*** * ****** * ****** * ****** * *** * * * *** * ****** * ***
**** ******** ******** ******** ***** ** ** ***** ******** ****
*** * ****** * ****** * ****** * *** * * * *** * ****** * ***
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
**** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
* *** * * *** * * *** * * * * * *** * * * * * *** *
* ***** ** ***** ** ***** ** ** ** ** ***** ** ** ** ** ***** *
* *** * * *** * * *** * * * * * *** * * * * * *** *
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***
**** ******** ******** ***** ** ** ***** ***** ** ** ***** ****
*** * ****** * ****** * *** * * * *** * *** * * * *** * ***This form has some 1s where the initial_value=0 had 0s. The positions of these extra 1s are the box fractal.
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* *
* * * *
* *
*
* *
* * * *
* *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* *
* * * *
* * * * * * * *
* * * *
* * * * * * * *Inverse
The inverse => 1 option (a boolean) can invert the 0,1 bits to instead 1,0. This can be applied to any of the types. For example on the default initial_value=0,
# inverse => 1
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,...Plotting Order
The Z-Order curve (per for example Math::PlanePath::ZOrderCurve) numbers its sub-parts
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 0 | 1 | 2 |
+---+---+---+This suits the sequence here because the numbering is alternately odd and even in adjacent sub-parts,
+------+------+------+
| even | odd | even |
+------+------+------+
| odd | even | odd |
+------+------+------+
| even | odd | even |
+------+------+------+Any self-similar expansion which numbers by an odd/even alternation like this gives the same result. This includes the Peano curve, Wunderlich's serpentine and meander, Haverkort's Kochel curve, and reflected Gray code path (radix=3).
Incidentally, drawing each pixel by this sequence is not very efficient. It's much faster to follow the array expansions described above and block copy areas of "0" or "1". An initial single pixel 0 expands to 3x3 then 9x9, etc. Two images representing a "0" or a "1" can be maintained, though with care some copying of sub-parts allows just one image to be built up. See examples/other/haferman-carpet-x11.pl for some code doing that.
FUNCTIONS
See "FUNCTIONS" in Math::NumSeq for the behaviour common to all path classes.
$seq = Math::NumSeq::HafermanCarpet->new (initial_value => $integer, inverse => $bool)-
Create and return a new sequence object.
initial_valuecan be 0 or 1.
Random Access
FORMULAS
Ith
The effect of the morphism described above is to find the least significant odd digit 1,3,5,7 when i is written in base-9.
i lowest base-9
digit 1,3,5,7 value
-------------- -------------
even position 1
odd position 0
no such digit initial_value
Position counted from low end.
Least significant digit is position=0 so is an "even position".For example i=609 is base-9 "746" and its lowest odd digit is the "7" which is 2 digits from the low end and thus an "even position" and so value=1.
Or i=357 is base-9 "436" and its lowest odd digit is the "3" which is 1 digit from the low end and thus an "odd position" so value=0.
If i contains no odd base-9 digits at all then it's "no such digit" and the result is the initial_value. For example i=58 is base-9 "64" which has no odd digits so value=0 in the default "initial_value=0". These i with no odd base-9 digit are the box fractal pattern shown above which are the places where initial_value 0 or 1 changes the sequence value.
"Position of lowest odd base-9 digit" can also be thought of as "count trailing even base-9 digits". If i is entirely even digits then that count should be reckoned as infinite by imagining 0 digits extending infinitely at the high end of i. That "infinite" case is then the "no such digit" of the table.
The value assigned to the three cases odd,even,none can each be 0 or 1 for a total 8 combinations. The cases above are 1,0,0 and 1,0,1 and their 1<->0 inverses 0,1,1 and 0,1,0 per the inverse option are the four most intersting combinations. The box fractal 0,0,1 and its inverse 1,1,0 are interesting but not generated by the code here. The remaining two 0,0,0 which is all zeros or 1,1,1 all ones are not very interesting.
Density
The number of 1s in the first 9^k many values from the sequence is as follows.
9^(k+1) - (2*(-1)^k + 7) * 5^k
Seq1s_init0(k) = ------------------------------
14and for initial_value=1
9^(k+1) - (2*(-1)^k - 7) * 5^k
Seq1s_init1(k) = ------------------------------
14The difference between the two is 5^k,
Seq1s_init1 = Seq1s_init0 + 5^kThis difference is the box fractal 1s described above which are gained in the initial_value=1 form. They're at positions where i has only even digits 0,2,4,6,8 in base 9, so 5 digit possibilities at each of k many digit positions giving 5^k.
The formulas can be calculated by considering how the 0s and 1s expand. The array morphism form with initial_value=1 is given by Eric Weinstein,
Each point expands
0 -> 9 of 1s
1 -> 4 of 1s plus 5 of 0sThe 1s in the expanded form are therefore 9 from each existing "0" and 4 from each existing "1". Since 0s+1s = 9^k this can be expressed in terms of Array1s.
Array1s(k+1) = 4*Array1s(k) + 9*Array0s(k)
= 4*Array1s(k) + 9*(9^k - Array1s(k)) # 0s+1s=9^k
= 9^(k+1) - 5*Array1s(k)Expanding this recurrence repeatedly gives
Array1s(k) = 5^0 * 9^k
- 5^1 * 9^(k-1)
+ 5^2 * 9^(k-2)
...
- (-5)^(k-1) * 9^1
- (-5)^k * 9^0 * Array1s(0)The alternating signs in each term are -5 as the increasing power. Since Array1s(0)=1 the last term is included and the powers sum as follows in the usual way.
9^(k+1) - (-5)^(k+1)
Array1s_init1(k) = --------------------
9 - (-5)If the initial starting cell is 0 instead of 1 then Array1s(0)=0 and the last term (-1)^k * 5^k is omitted. Subtracting that leaves
9^(k+1) - 9*(-5)^k
Array1s_init0(k) = ------------------
9 - (-5)For the sequence forms here the initial value does not change, unlike the array alternating 0<->1. The sequence takes the array starting 0 or 1 according as k is even or odd, thereby ensuring the first value is 0. So,
Seq1s_init0(k) = / Array1s_init0(k) if k even
\ Array1s_init1(k) if k oddThe term (2*(-1)^k - 7) seen above in the Seq1s_init0() formula selects between 9 or 5 as the multiplier for (-5)^k. That 9 or 5 multiplier is the difference between the two Array1s forms.
SEE ALSO
Math::PlanePath::ZOrderCurve, Math::PlanePath::PeanoCurve, Math::PlanePath::WunderlichSerpentine, Math::PlanePath::KochelCurve, Math::PlanePath::GrayCode, Math::PlanePath::SquareReplicate
examples/other/haferman-carpet-x11.pl draws the carpet interactively with X11::Protocol.
HOME PAGE
http://user42.tuxfamily.org/math-numseq/index.html
LICENSE
Copyright 2013, 2014, 2016, 2017, 2019, 2020 Kevin Ryde
Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.