Tower of Hanoi : Part 3 of 3

I tried to played with a modified version of Tower of Hanoi : instead of just having 3 Rods, what will happen when we have 4 rods instead ?

my naive first move (Caution : it is wrong)

If I know how to solve a n-disk puzzle, then I can solve a (n+1)-disk puzzle,

move n-1 disks to a temporary rod, move the largest disk, then move the n-1 disks again

so T{n} = 2T{n-1} + 1 as well

the least number of disk to use all 4 rods to solve the puzzle should be 3-disks, we will need

state 0 : [1,2,3][_,_,_][_,_,_][_,_,_]
state 1 : [_,2,3][_,_,1][_,_,_][_,_,_]
state 2 : [_,_,3][_,_,1][_,_,2][_,_,_]
state 3 : [_,_,_][_,_,1][_,_,2][_,_,3]
state 4 : [_,_,_][_,_,1][_,_,_][_,2,3]
state 5 : [_,_,_][_,_,_][_,_,_][1,2,3]

so I knew that T{3} = 5

and I have used the same approach and I ended up with:

T{n} = 2^(n-2)*6 - 1 = 2^(n-1)*3 - 1

which is TECHNICALLY doable, but wrong

this formula will only work ONLY if I will use all the 4 rods for the (n-1) disks and treat the whole stack as a 3-rod puzzle.

I thought that T{7} = 2^(7-1)*3 - 1 = 2^6*3-1 = 64*3-1=192-1= 191

but turns out one of the ways to do it can be:

state 00 : [1,2,3,4,5,6,7][_,_,_,_,_,_,_][_,_,_,_,_,_,_][_,_,_,_,_,_,_]
5 steps to move 1,2,3 from rodA to rodB by using 4 rods
state 05 : [_,_,_,4,5,6,7][_,_,_,_,1,2,3][_,_,_,_,_,_,_][_,_,_,_,_,_,_]
15 steps to move 4,5,6,7 from rodA to rodD by only using rodA,CandD
state 20 : [_,_,_,_,_,_,_][_,_,_,_,1,2,3][_,_,_,_,_,_,_][_,_,_,4,5,6,7]
5 steps again by using all 4 rods
state 25 : [_,_,_,_,_,_,_][_,_,_,_,_,_,_][_,_,_,_,_,_,_][1,2,3,4,5,6,7]

obvious enough 25 < 191

my second guess:

my new strategy would be:

divide the pile into 3 groups, say Alpha, Beta and Gamma

note that Alpha.AnyDiameter < Beta.AnyDiameter < Gamma.AnyDiameter

if n is odd

step 1: move Alpha from rodA to rodB, since Alpha has the smallest diameters, it is free to use all 4 rods

step 2: move Beta from rodA to rodC, but rodB cannot be used, so it is actually a 3rod puzzle

step 3: move Gamma from rodA to rodD, not that Qty(Gamma) = 0 or 1

if n is even

step 1: move Alpha from rodA to rodB by using all 4 rods.

step 2: move Beta from rodA to rodD by not using rodB (3rods).

but how are the groups are going to get their disks ?

if n is odd

Alpha : 1st ~ [(n-1)/2]th

Beta : [(n-1)/2+1]the ~ [n-1]th

Gamma : [nth]

for T{n}  : Alpha and Beta  and Gamma

for T{7}  : 1,2,3 and 4,5,6 and 7
for T{9}  : 1,2,3,4 and 5,6,7,8 and 9
for T{11} : 1,2,3,4,5 and 6,7,8,9,10 and 11
and so on
for T{2z+1} : z and z and 1 

if n is even

Alpha: 1st ~ [n/2]th

Beta: [n/2+1]the ~ [n]th

Gamma : none

for T{14} = 1,2,3,4,5,6,7 and 8,9,10,11,12,13,14 and none

so for the example T{7}, the solving process would be like

pile = {1,2,3,4,5,6,7}

alpha = {1,2,3}
beta  = {4,5,6}
gamma = {7}

state 00 : [alpha,beta,gamma][][][]
//use 5 steps to move alpha from rodA to rodB
state 05 : [beta,gamma][alpha][][]
//use 7 steps to move beta from rodA to rodC, 3 rods available
state 12 : [gamma][alpha][beta][]
//use 1 step to move the only disk (gamma) from rodA to rodD
state 13 : [][alpha][beta][gamma]
//use 7 steps to move beta from rodC to rodD, 3 rods available
state 20 : [][alpha][][beta,gamma]
//use 5 steps to move alpha from rodB to rodD
state 25 : [][][][alpha,beta,gamma]

so we have T{7} = 25 

since we are now having 2 systems (3rod and 4rod), let's redefine the syntax as

T{p,d} = least number of steps required to solve a d-disks p-rod Tower of Hanoi puzzle

from the examples, we know that:

if d is odd

T{4,d} = 2T{4,(d-1)/2} + 2T{3,(d-1)/2} + T(1,1)

if d is even

T{4,d} = 2T{4,d/2} + 2T{3,d/2} + T(1,0)

PS:

T{3,d} = 2^d - 1

this is an exploration of craziness, I will pause here... for now

by the way, here is a link to a video : https://www.youtube.com/watch?v=OduzmO7IcLs&t=769s&pp=ygUTbWVtbzIwMDd1bHRyYSBoYW5vaQ%3D%3D