Transform involving permutations

[Jeffrey Shallit]

> From: David Wasserman <dwasserm at earthlink.com>
> Subject: Re: Transform involving permutations
> 
> The "Quet transform" of A006519 is
> 1,2,1,2,3,2,1,2,3,2,3,4,3,2,1,2,3,2,3,4,3,2,3,4,3,4,5,4,3,2,1...
> which is constructed as follows: 
> Start with a subsequence consisting of a single 1, and repeatedly apply the operation S -> S,1+S,1
> thus
> 1
> 1,2,1
> 1,2,1,2,3,2,1
> 1,2,1,2,3,2,1,2,3,2,3,4,3,2,1
> etc.
> This appears to be 1 + A080468.
> 
> %I A006519 M0162
> %S A006519 1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,32,1,2,
> %T A006519 1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,64,1,2,1,4,
> %U A006519 1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,32,1,2,1,4,1,2
> %N A006519 Highest power of 2 dividing n.
> 
> %I A080468
> %S A080468 0,1,0,1,2,1,0,1,2,1,2,3,2,1,0,1,2,1,2,3,2,1,2,3,2,3,4,3,2,1,0,1,2,1,2,
> %T A080468 3,2,1,2,3,2,3,4,3,2,1,2,3,2,3,4,3,2,3,4,3,4,5,4,3,2,1,0,1,2,1,2,3,2,1,
> %U A080468 2,3,2,3,4,3,2,1,2,3,2,3,4,3,2,3,4,3,4,5,4,3,2,1,2,3,2,3,4,3,2,3,4,3,4
> %N A080468 a(n) = A080578(n)-2n.
> %C A080468 Terms between 2^n and 2^(n+1) as n goes to infinity tend to the sequence : 0,1,2,1,2,3,2,1,2,3,2,3,4,3,2,1,2\
>   ,3,2,3,4,3,2,3,4,3,4,5,4,3,2,1,....


Your sequence 1,2,1,2,3,2,1,2,3,2,3,4,3,2,1, ....
is very interesting!  

Consider representing an integer n as a sum of elements of 1,3,7,15,31,63, ... (one less
than a power of 2) using the greedy algorithm.  Thus, for example,
	27 = 15 + 7 + 3 + 1 + 1
        30 = 15 + 15

Then your sequence counts the number of summands needed.

Jeffrey Shallit