Arpeggio-Doubling Sequence

[David W. Wilson]

> -----Original Message-----
> From: Leroy Quet [mailto:q1qq2qqq3qqqq at yahoo.com]
> Sent: Sunday, March 16, 2008 11:37 AM
> To: seqfan at ext.jussieu.fr
> Cc: q1qq2qqq3qqqq at yahoo.com; qq-quet at mindspring.com
> Subject: Arpeggio-Doubling Sequence
> 
> Here is sequence A137293 in its raw unedited form:
>
> [sequence elided]
>
> The question is, is there a closed form (ie
> non-recursive) way of calculating any particular
> a(n) directly?

Let m be a function that maps nonnegative integers to finite sequences of
nonnegative integers. Let m(S) be the sequence gotten by replacing each
element of s of S with m(S).

For example, if m(n) = (1,2,...,n) and S = (1,2,3), then m(S) =
(1,1,2,1,2,3).

If we define m(n) = (1,2,...,2n), then your sequence A137293 is the unique
fixpoint of the function

    f(S) = (1, m(S))

For example, starting with S0 = () = empty sequence, we get

    S0         = ()
    S1 = f(S0) = (1)
    S2 = f(S1) = (1,1,2)
    S3 = f(S2) = (1,1,2,1,2,1,2,3,4)
    etc.

at each iteration getting a longer and longer prefix of your sequence.

Fixpoint sequences of this type are not uncommon. If we let m(n) = 1-n, and
define

    f(S) = (S, m(S))

and start with S0 = (0), we get iterations

    S0         = (0)
    S1 = f(S0) = (0, 1)
    S2 = f(S1) = (0, 1, 1, 0)
    S3 = f(S2) = (0, 1, 1, 0, 1, 0, 0, 1)
    etc.

which are prefixes of the Thue-Morse sequence A010060.

If instead we choose

    f(S) = (1^S(1), 2^S(2), 1^S(3), 2^S(4), ...)

and start sequence S(0) = (1, 2), we get the iterations

    S0         = (1, 2)
    S1 = f(S0) = (1, 2, 2)
    S2 = f(S1) = (1, 2, 2, 1, 1)
    S3 = f(S2) = (1, 2, 2, 1, 1, 2, 1)
    etc.

which are prefixes of the Kolakoski sequence A000002.

For the Thue-Morse sequence, the length of the prefix S_n is easily shown to
be 2^n. Not coincidentally, the Thue-Morse sequence has a simple definition
based on its binary representation, i.e., a(n) = parity of the number of 1
bits in the binary representation of n.

On the other hand, the lengths of the Kolakoski iterates for the sequence

    (2, 3, 5, 7, 10, 15, ...) = 1 + A042942

which does not appear to have a simple formula. Again, not coincidentally,
the Kolakoski sequence itself is famously intractable.

The lengths of the iterates of your function seem to grow as

    (0, 1, 3, 9, 35, 201, 1827, 27337, ...) = (0, A125792)

which is most assuredly superexponential, and doubtless has a very
complicated formula if any at all. The complexity of the iterate lengths
makes me leery of a simple formula.

> (Perhaps something involving the
> binary representation of n.)
> It seems that there should be.

The fact that the iterate lengths are not easily related to powers of 2
argues strongly against this.