Sunday, August 04, 2013

I keep going back to concrete math, but this time I went with a tool

Of late, I seem to be stuck in a loop with books. I read parts of them and then seem to come back to the very beginning of the same book and discover something new. I am stuck in a partial loop in an "open form". Of late that has happened with Concrete Mathematics. I started with the first chapter on Recurrent problems - you seen the irony :)

Anyway, one of the problems is Towers of Hanoi with limitation. Don't go to the intermediate peg directly, go to the destination peg and then go to the intermediate peg. I remember reading somewhere that Knuth used Macsyma for a bunch of verification on Metafont (I could be wrong). I decided to use Maxima. I used the solve_rec procedure

load(solve_rec);

The recurrence equation is


solve_rec(a[n] = 3*a[n-1] + 1, a[n]));


and Maxima was quick to respond with the answer

I wonder if Knuth is right, in the future most of the burden of mathematical complexity of finding a solution will be delegated to computers.
Post a Comment