view release on metacpan or  search on metacpan

lib/Math/NumSeq/HafermanCarpet.pm  view on Meta::CPAN

    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 C<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
1E<lt>-E<gt>0 inverses 0,1,1 and 0,1,0 per the C<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.

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

X<Weinstein, Eric>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,

=over

L<http://mathworld.wolfram.com/HafermanCarpet.html>,
L<http://oeis.org/A118005>

=back

Each point expands

    0 -> 9 of 1s
    1 -> 4 of 1s plus 5 of 0s

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 S<(-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 0E<lt>-E<gt>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 odd

The term S<(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.

=head1 SEE ALSO

L<Math::NumSeq>

L<Math::PlanePath::ZOrderCurve>,
L<Math::PlanePath::PeanoCurve>,
L<Math::PlanePath::WunderlichSerpentine>,
L<Math::PlanePath::KochelCurve>,
L<Math::PlanePath::GrayCode>,
L<Math::PlanePath::SquareReplicate>

F<examples/other/haferman-carpet-x11.pl> draws the carpet interactively with
C<X11::Protocol>.

=head1 HOME PAGE

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

=head1 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/>.

=cut

# Local variables:
# compile-command: "math-image --wx --values=HafermanCarpet --path=ZOrderCurve,radix=3 --scale=5"
# End:
#