[seqfan] Re: Formulas for two sequences, A060574 and A067498 ?
hv at crypt.org
hv at crypt.org
Tue Mar 29 04:17:07 CEST 2022
Earlier I wrote:
:Antti Karttunen <antti.karttunen at gmail.com> wrote:
::Does anybody know formulas for these two sequences?
::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
:Here's a partial solution:
:Let p be the highest power of 2 that divides n, and k = n/2^p.
Oops, you need to shift that 1-bit off as well, so it needs
k = (n/2^p - 1) / 2, and the results below shift by one.
: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.
This should be: if p even, k == 0 (mod 3), or p odd, k == 1 (mod 3).
: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).
This should be: if p even, k == 2 (mod 3), or p odd, k == 0 (mod 3).
: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.
I see others posted solutions just before mine, but it wasn't clear
to me from reading those what the missing piece here should be.
More information about the SeqFan