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 ZOrder 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=0
When plotted in ZOrder 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 0
For 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,0
The 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 previous values are unchanged. If an odd number of expansions were done then for example the first bit flips 0<>1. The even number of expansions can also be expressed as each bit morphing into an 81long run.
0 > 0,1,0,1,0,1,0,1,0, # 9 times repeating
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 repeating
0,1,0,1,0,1,0,1,0, # alternating 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 base9 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 ZOrder 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 ZOrder curve (per for example Math::PlanePath::ZOrderCurve) numbers its subparts
++++
 6  7  8 
++++
 3  4  5 
++++
 0  1  2 
++++
This suits the sequence here because the numbering is alternately odd and even in adjacent subparts,
++++
 even  odd  even 
++++
 odd  even  odd 
++++
 even  odd  even 
++++
Any selfsimilar 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, 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 subparts allows just one image to be built up.
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_value
can 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 base9.
i lowest base9 digit 1,3,5,7
odd even no such
initial_value position position digit
   
0 1 0 0
1 1 0 1
Position counted from low end, least significant
digit is position=0 (so is an "even position").
For example i=609 is base9 "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=0.
Or i=357 is base9 "436" and its lowest odd digit is the "3" which is 1 digit from the low end and thus an "odd position" so value=1.
If i contains no odd base9 digits at all then the "no such digit" column is used. For example i=58 is base9 "64" which has no odd digits so value=0 in the default "initial_value=0".
These i with no odd base9 digit are the box fractal pattern shown above which is the difference between initial value 0 or 1.
This "position of lowest odd base9 digit" can also be thought of as "count trailing even base9 digits". In this case 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 in the three columns can each be 0 or 1 for a total 8 combinations. The two above and their 1,0 inverses per the inverse
option are the four intersting possibilities. The box fractal 0,0,1 and its inverse are two more (not generated by the code here). The final two would be 0,0,0 which is all zeros or 1,1,1 all ones.
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) = 
14
and for initial_value=1
9^(k+1)  (2*(1)^k  7) * 5^k
Seq1s_init1(k) = 
14
The difference between the two is 5^k,
Seq1s_init1 = Seq1s_init0 + 5^k
This 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.
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 1
1 > 4 of 1 plus 5 of 0
The 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^(k1)
+ 5^2 * 9^(k2)
...
 (5)^(k1) * 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 the initial value does not change, unlike the array alternating 0<>1. The sequence takes the array starting alternately 0 or 1 as k even or odd to ensure the first value is 0. So,
Seq1s_init0(k) = / Array1s_init0(k) if k even
\ Array1s_init1(k) if k odd
The term (2*(1)^k  7) seen above in Seq1s_init0() selects between 9 or 5 as the multiplier for (5)^k. That 9 or 5 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
HOME PAGE
http://user42.tuxfamily.org/mathnumseq/index.html
LICENSE
Copyright 2013 Kevin Ryde
MathNumSeq 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.
MathNumSeq 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 MathNumSeq. If not, see <http://www.gnu.org/licenses/>.