[seqfan] Identifying a group of fractal sequences in the OEIS

[Joe Slater]

There are a number of sequences in the OEIS that should be marked as being
fractal, in that the original sequence reappears after striking out the
first appearance of each value. I've identified a run of eight by Clark
Kimberling from A124912 to A124919 but of course there may be others.

Here's a description and proof for the first of these sequences I stumbled
across, A124915,  but similar logic applies to the similar sequences that
can be produced by any pair of natural numbers that are not multiples of
each other. I do not propose that every such sequence be included in the
OEIS, at present.

Description of the sequence A124915:

Take the binary sequence of digits produced by the reciprocals of 3^k,
without the leading zeroes:
The first few are:
1/3^0 = 100000
1/3^1 = 101010...
1/3^2 = 111000...
1/3^3 = 100101 [&c]
1/3^4 = 110010 [&c]
1/3^5 = 100001 [&c]

For each n, a(n) equals the least k such that the binary expression of n is
similar to the first digits of 1/3^k. For instance, a(6)=4 because the
binary value of 6 is 110 which is to be found at the beginning of 1/3^4.

Note: the author of this series defined it for n>0, but I wonder if it
could not be defined for n>=0 on the theory that 0 in this context has a
length of zero and is therefore identified with the zero-length number
produced by 3^0.

Proof that the sequence A124915 is fractal:

Let us call the first appearance of any  value in a sequence a *novel *value
and call a sequence *fractal *if, when we delete all the novel values, the
remaining values form the original sequence.

For a natural number n consisting of k binary digits we define the value
a(n) as the least natural number such that (after truncating the leading
zeroes) the first k digits of the binary fraction 1/3^a(n) are equal to n.

Recall that n is k binary digits long. Consequently, the numbers 2n and
2n+1 will be k+1 digits long and have the same binary representation as n
but with a 0 or 1 appended, respectively.

Now, the k+1th digit of 1/3^a(n) must be either 0 or 1. If it is a 0 then
a(2n)  = a(n) and a(2n+1) is a novel value; if it is a 1 then the opposite
is true.

This applies to any pair of values a(2n) and a(2n+1): one must be novel,
one must be the same as a(n). Consequently, if we eliminate the novel
values from a subsequence (a(2n) ... a(2n+2k)) we will have the
subsequence (a(n) ... a(n+k)).

QED.

Note: the values of a(n) in a series generated by two numbers p and q can
be produced by this PARI/GP program:

a(n,p,q)={
    if(n==0||n==p^valuation(n,p),return(0));
    my(k=0);
    my(d=#digits(n,p));
    while(n<>floor(p^(d-frac(k*log(q)/log(p)))),
        k++);
    return(k)
    }

Yours,
Joe Slater