Am I the only one who read this and thought: hmm, for any number 32 or higher, the minimum cost would always be 5? Who cares about recursion when it's such a constrained problem? :)
You are not the only one who thought that; see the comments to my post. As I note in part two, the point of the article was to show the general method; there are of course many ways to solve the original problem more efficiently. The specific problem is trivial and unimportant.
It's not as simple as that -- compute the cost of 2^64, 2^64-1, and 2^64-64 to see some more interesting behavior... (I'm using ^ because HN eats double-asterisks; your python may vary)