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=0

When 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  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 81-long 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 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, 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.

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

$value = $seq->ith($i)

Return the $i'th value from the sequence.

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

                        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 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=0.

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=1.

If i contains no odd base-9 digits at all then the "no such digit" column is used. 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 is the difference between initial value 0 or 1.

This "position of lowest odd base-9 digit" can also be thought of as "count trailing even base-9 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^(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 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::NumSeq

Math::PlanePath::ZOrderCurve, Math::PlanePath::PeanoCurve, Math::PlanePath::WunderlichSerpentine, Math::PlanePath::KochelCurve, Math::PlanePath::GrayCode, Math::PlanePath::SquareReplicate

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2013 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/>.