A340849 a(n) = A001045(n) + A052928(n).

0, 1, 3, 5, 9, 15, 27, 49, 93, 179, 351, 693, 1377, 2743, 5475, 10937, 21861, 43707, 87399, 174781, 349545, 699071, 1398123, 2796225, 5592429, 11184835, 22369647, 44739269, 89478513, 178956999, 357913971, 715827913

Offset: 0

Author

Paul Curtz, Jan 24 2021

Keywords

• nonn

Comments

a(2*n) is divisible by 3.

a(3*n+2) is divisible by 3.

a(n) is the minimum number of moves to solve a Towers of Hanoi puzzle with 4 pegs and n disks where a disk cannot move away from the destination peg (or symmetrically, a disk cannot return to the initial peg). - Woosuk Kwak, Jan 25 2024

Links

• Woosuk Kwak, 1+3 Towers of Hanoi, Puzzling Stack Exchange.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Crossrefs

Cf. A001045, A052928, A100314, A109613, A128209.

Programs

Mathematica

LinearRecurrence[{3, -1, -3, 2}, {0, 1, 3, 5}, 32] (* Robert P. P. McKone, Jan 28 2021 *)

Formula

a(n+1) - 2*a(n) = -A109613(n-2), for a(0)=0, a(1)=1. a(n) + a(n+1) = A100314(n).

a(n+1) - a(n) = A128209(n) for n >= 0.

a(n+2) = 1 + 2*A086445(n). - Hugo Pfoertner, Jan 24 2021

From Woosuk Kwak, Jan 25 2024: (Start)

a(n) = n + floor(2^n/3).

a(n) = n + A000975(n-1) for n >= 1. (End)