It can be done more efficiently than this. You shouldn't divide the work up evenly. Below are some special cases and the smallest solution sizes possible (I believe) for them.

If P is the number of pegs, D is the number of disks, and M is the minimum number of moves for which a solution exists, then:

for  P >= 3
if   D = P*(P-1)/2
then M = P*(P-2)*2+1

so

P=3, D=3,  M=7
P=4, D=6,  M=17
P=5, D=10, M=31
P=6, D=15, M=49
...
[download]

I may write up why this is so, but I suspect someone else is likely to beat me to that. And if you try to figure out why I picked these cases, you'll probably have a good hint for part of a good solution for the general problem. (: