A Permutation Defining Itself

[Leroy Quet]

By the way, Keith Ramsay has submitted the following to sci.math.
Leroy


>In article <1103652059.284646.146... at c13g2000cwb.googlegroups.com>, "Leroy
> Quet" <qqq... at mindspring.com> writes:
> |>%
> S A000001 1,2,1,4,1,3,1,8,1,5,1,9,1,6,1,16,1,7,1,14,1,10,1,21,1,11,1
> |>%N A000001 a(2n-1) = 1;
> |>a(2n) = a(n)th lowest positive integer not among the earlier terms of
> the
> |>sequence
>
> .
>
> I've noticed just a few simple things so far. At the term a(2n), there
> have been n distinct terms so far (a(1)=1, and a(2), a(4),...,a(2n-2)),
> so a(2n)<=a(n)+n. By induction, one can then show that a(n)<=n
> with equality if and only if n is a power of 2. If n=2^k, k>0, there have
> been 2^{k-1} distinct terms so far, each <2^k, and a(n/2)=2^{k-1}, so
> a(n) is the 2^{k-1}-st positive integer not to appear so far, 2^k.
>
> On the other hand, the terms of the form a(4k+2) are equal to the
> smallest positive integer not yet appearing, so the terms a(1),...,
> a(4k+2) have to include among them all the integers 1,...,k+2.
> Thus for even n, a(n)>=[(n+6)/4] where [] is the greatest integer
> function.
>
> I'm unsure whether to expect there to be a really easy way to
> compute the n-th term, but it seems like there should be more
> patterns in the terms. For each k>0, the subsequence
> a(2^k(2n+1)) is increasing, as one can show by induction on k,
> using the observation that if n<m and a(n)<a(m), then
> a(2n)<a(2m); indeed a(2m)-a(2n)>=a(m)-a(n).
>
> Keith Ramsay