I'd suggest revisiting your analysis of how good 4 pegs are. With your program I see:

10 disks with 4 pegs: Solved in 57 moves
20 disks with 4 pegs: Solved in 1137 moves
30 disks with 4 pegs: Solved in 33377 moves
40 disks with 4 pegs: Solved in 1050849 moves
[download]

That doesn't look like O(n*log(n)) to me!

Does anyone else think that they can do better?