[seqfan] Re: Formulas for two sequences, A060574 and A067498 ?

[hv at crypt.org]

Antti Karttunen <antti.karttunen at gmail.com> wrote:
:Cheers,
:
:Does anybody know formulas for these two sequences?
:
:https://oeis.org/A060574
:Tower of Hanoi: using the optimal way to move an even number of disks
:from peg 0 to peg 2 or an odd number from peg 0 to peg 1, a(n) is the
:smallest disk on peg 1 after n moves (or 0 if there are no disks on
:peg 1).

Here's a partial solution:

Let p be the highest power of 2 that divides n, and k = n/2^p.
Then at move n we will move disk p+1 (per A001511).
Odd-numbered disks always move in the trajectory 0 -> 1 -> 2 -> 0;
even-numbered ones always move in the trajectory 0 -> 2 -> 1 -> 0.
(I think this is half-implied by the PARI program for A060572,
but does not seem to be spelled out in A060572 or A060571.)

So if p even, k == 1 (mod 3), or p odd, k == 2 (mod 3) we will
move disk p+1 to column 1, so A060574(n) = p+1.

If p even, k == 0 (mod 3), or p odd, k == 1 (mod 3) we will not
change the disk on column 1, so A060574(n) = A060574(n-1).

For the remaining 2 cases, we will move the current disk _off_ column 1
revealing a larger disk (or no disk at all), so A060574(n) = 0 or
A060574(n) > A060574(n-1).

Now just need to work out what is revealed in those last two cases.
I'll have a think about that, but I expect it to get harder here.

Hugo