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.

If you decide to change denominations though, all those numbers will change.