A338089 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg three steps away.

3, 10, 21, 40, 75, 134, 233, 400, 683, 1166, 1981, 3364, 5711, 9690, 16433, 27872, 47267, 80150, 135909, 230460, 390775

Offset: 1

Author

Paul Zimmermann, Oct 09 2020

Keywords

• nonn
• more
• changed

Examples

			For n=2, assume the two disks are on North initially, first move the smallest one to South in 2 moves, then the largest one to East in 1 move, the smallest one back to North in 2 moves, the largest one to West in 2 moves, and finally the smallest one to West in 3 moves, with a total of 10 moves. Each disk has a number of moves which is 3 mod 4, thus a(n) == 3*n (mod 4).
		

Links

• Martin Ehrenstein, (C++) Program for A338024 (computes terms of this sequence, too)

Crossrefs

Cf. A292764, A338024.

Formula

Conjecture: a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-5) for n > 9 (the same recurrence as conjectured in A292764 and A338024). - Pontus von Brömssen, Oct 12 2020

a(n) ~ k*r^n, k = (725 + (310451786 - 3203949*sqrt(87))^(1/3) + (310451786 + 3203949*sqrt(87))^(1/3))/348, r=constant of A289265 (closed-form by Amiram Eldar via von Brömssen conjecture). - Bill McEachen, Aug 19 2025

Extensions

a(17)-a(21) from Martin Ehrenstein, Oct 26 2020