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, 1431655797, 2863311563, 5726623095, 11453246157

Offset

0,3

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

Table of n, a(n) for n=0..35.

Woosuk Kwak, 1+3 Towers of Hanoi, Puzzling Stack Exchange.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

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)

From Elmo R. Oliveira, Apr 10 2026: (Start)

a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + 2*a(n-4).

a(n) = [x^n] x*(1 - 3*x^2)/((1 - x)^2*(1 - 2*x)*(1 + x)). (End)

E.g.f.: (cosh(2*x) + (3*x - 2)*sinh(x) + cosh(x)*(2*sinh(x) + 3*x - 1))/3. - Stefano Spezia, Apr 10 2026

Mathematica

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

Crossrefs

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

Sequence in context: A390318 A307677 A140428 * A027154 A217350 A210844

Adjacent sequences: A340846 A340847 A340848 * A340850 A340851 A340852

Keyword

nonn,easy

Author

Paul Curtz, Jan 24 2021

Extensions

More terms from Elmo R. Oliveira, Apr 10 2026

Status

approved