SICP - counting change

In section 1.2.2, SICP gives an incredibly inefficient recursive procedure for counting change and then later leaves it up to the reader to come up with a better one.

Here's what I was able to come up with (in Python because I like it better than Scheme):


def count_change(n):
    n /= 5
    if n%2:
        b = -1
    else:
        b = 1
    c = 1425*b + 26799 + n*(150*b + 21850 + n*(4760 + n*(380 + 10*n)))
    m = n%10
    if m==0 or m==1:
        c -= 4224
    elif m==2:
        c += (576+480*n)
    elif m==3 or m==8:
        c -= 384
    elif m==4:
        c -= (1344+480*n)
    elif m==5 or m==6:
        c += 5376
    elif m==7:
        c += (7776 + 480*n)
    elif m==9:
        c -= (8544 + 480*n)
    c /= 24000
    return c

I attempted to solve the recurrence relation exactly (lots of complicated sums involving roots of unity to simplify). I haven't proven that the above is indeed correct, but it seems to work well for all the values I've tested.

O(1) for the win.

Hi, Do you like lisp? When I first stumbled into Lisp advocacy on various corners of the web I was already an EXPERT PROGRAMMER. At that point I had grokked what seemed at the time a wide range of programming languages. I was proud to have under my belt (Java, C, C++, C#, C-, FORTRAN, BBCODE, etc.) I was under impression that I knew EVERYTHING there is to know about programming languages, I had written HUGE PROGRAMS you couldn't even COMPREHEND at age 12. I couldn't have possibly been more wrong. My initial attempt to learn Lisp came to a crashing halt as soon as I saw some sample code. I suppose the same thought ran through my mind that ran through thousands of other minds who were ever in my shoes: "OMG WTF LOOKS SHIT WTF IS UP WITH THAT ())()))))(((() FUCK!!!!11111" I couldn't be bothered to learn a language if its creators couldn't be bothered to give it a BBCode like syntax. After all, I was almost blinded by the infamous suave space toad Lisp! For many months the Lisp advocates pressed on. I was baffled. Many extremely intelligent people I knew and had much respect for were praising Lisp with almost religious dedication. There had to be something there, something I couldn't afford not to get my hands on! Eventually my thirst for knowledge won me over. I took the plunge, bit the bullet, got my hands dirty, and began months of mind blending exercises. It was a journey on an endless lake of frustration, I am stupid fuck. I turned my mind inside out, rinsed it, and put it back in place. I went through seven rings of hell and came back. And then I got it. I KNOW LISP. I AM SO SMART. I AM SO EXPERT, NOW I KNOW EVERYTHING ABOUT PROGRAMMMING, I DONT HAVE TO LEARN ANY OTHER LANGUAGE EVER.