[cousin_it]

Nice! Also your solution makes it easy to move on to a logarithmic time solution: going from (a,b,c) to (b,c,3a+2b+c) is a linear transformation which can be expressed as a 3x3 matrix, therefore iterating it n times is equivalent to raising that matrix to the nth power, which can be done in log(n) time using square and multiply [1]. Disregard programming, study math!

In fact the exact same reasoning can be used to derive the closed form expression for the Fibonacci numbers [2], which are defined by a recurrence relation similar to the one in the OP. You raise the corresponding 2x2 matrix to the nth power by going to the eigenbasis where the matrix becomes diagonal, raising the values on the diagonal (which turn out to be the golden ratio (phi) and -1/phi) to the nth power, then changing the basis back.

[1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[2] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

[BDFL_Xenu]

And conveniently enough for this discussion, this happens to be exercise 1.19 of SICP (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...).

[cousin_it]

Awesome! But actually I think my comment was inadvertently a bit more illuminating than the SICP exercise :-) Despite being on the web, SICP is a "traditional" textbook and doesn't bother to link to Wikipedia. Instead they use some sort of stone-age technology called "footnotes", stuffing all supplementary material right into the book as a couple lines of tiny text. So the student gets the feeling of following a twisty cluttered rabbit hole instead of exploring a new land.

[BDFL_Xenu]

Well, SICP was a printed book before being put on the web (as it is quite a few years older than it), and the version you see on the webpage is just a rendition of it in HTML. Still, I didn't know until today that you could link to individual figures and exercises, it will be even more fun to cite it in a quasi-religious, trollish way.

Also, you generalized the principle (and fused two exercises of the book in one :), or at least I'll have to believe you ;) I didn't form really much of an intuition on eigenvectors during the completely proper Linear Algebra course that I took, which is only my fault.

But I think that the exercise serves to reinforce the underlying theme that with enough attention, one can either supply or draw the insight to chip away yet one more part of the problem, to attack it from another angle, to pull it from just another direction that one had not seen before. It celebrates cleverness and knowledge, used to make complex things simple, to find the easy way out the hard way and end up better in the end, and that's partly why it's so cherished, but we all know that.

[prakashk]

> Instead they use some sort of stone-age technology called "footnotes", stuffing all supplementary material right into the book as a couple lines of tiny text.

A bit OT.

I got tired of clicking on the footnote links, and click to come back to text, and wrote a little Greasemonkey script that shows the footnotes on mouse hover. Makes reading the text a bit easier.

It's available at http://userscripts.org/scripts/show/109690 in case anyone's interested.

[danvet]

You've made my day. This is one of the tricks to I often forget about again but just smile upon reencountering.

Step 1: Transform to the eigenbasis of your operator. Step 2: Enjoy the beaty.