Doubly Fractal Sequences
by Franklin T. Adams-Watters

Date: Mon, 28 Aug 2006 15:56:27 -0400

A fractal sequence is one where, when the first instance
of each number in the sequence is erased, the original
sequence remains.  A similar property, which we might
call an incremental fractal sequence, is that when all ones
are removed from the sequence, what remains is the
original sequence incremented.  (This has also been
described as decrementing the sequence, then removing
all 0's to get the original sequence.)

These two properties are closely linked via what I call
the ordinal transform.  The ordinal transform of a
sequence b is the sequence a where a(n) is the number
of values in b(1),...,b(n) which are equal to b(n).  A
sequence is fractal if and only if its ordinal transform is
incremental fractal.  (This is easy to prove.)  If the
original fractal sequence introduced the positive integers
in increasing order, applying the ordinal transform again
will reproduce the original fractal sequence.  (Otherwise
it produces a simple substitution in the fractal sequence.)

It is easy to create sequences that are fractal; start with
a(1) = 1, and for each n > 1, you have a choice of
a(n) = a(k) where k the smallest index not yet used in
this fashion, or a(n) = a value not previously occurring
in the sequence; wlog a(n) = max(a(1),...,a(n-1) + 1.
As long as you choose a previous value infinitely often,
this will produce a fractal sequence.  Thus there are
2^{n-1} initial segments of fractal sequences of length
n (that introduce the positive integers in order), and
uncountably many total.

A sequence that is both fractal and incremental fractal I
call doubly fractal.  An example of a doubly fractal
sequence is the "count up to n sequence" A002260;
its ordinal transform is A004736, the "count down from
n sequence".

It appears that every sequence which is both an initial
sequence of a fractal sequence and an initial sequence
of an incremental fractal sequence is, in fact, an initial
sequence of a doubly fractal sequence.  I think I can
prove this, given the equivalence between fractal
sequences and interspersions.[1]  A doubly fractal
sequence corresponds to an interspersion whose
transpose is also an interspersion.

This does not immediately prove that the number of
doubly fractal sequence is uncountable.  This is not
hard to prove, however.  The signature of a positive
irrational number R is the sequence of i values when
all numbers of the form i + j*R, with i and j positive i
ntegers, are arranged in increasing order.  The
signature sequence for any R is fractal; but its ordinal
transform is the signature sequence for 1/R, so it is
doubly fractal.

We can generalize the concept of a signature
sequence to rational R; each rational R has two
signature sequences.  One breaks ties in increasing
order of i values, and the other breaks ties in
decreasing order.  For example, for R = 1, the
increasing signature sequence gives A002260, and
the decreasing signature sequence gives A004736.
One way to think of this is that the increasing
signature is the signature for R + epsilon, where
epsilon is an infinitesimal, while the decreasing
signature is the signature for R - epsilon.  In
general, the increasing signature sequence for R
transforms to the decreasing signature for 1/R.

Conjecture: every doubly fractal sequence is
the generalized signature sequence of some
positive real number R.

[1] C. Kimberling, "Fractal sequences and interspersions,"
Ars Combinatoria 45 (1997) 157-168.  [I don't have
access to this article, but from the web sites
<http://faculty.evansville.edu/ck6/integer/fractals.html>
and
<http://faculty.evansville.edu/ck6/integer/intersp.html>
I'm sure it covers this.]