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.

sub count_change($){
 my$n=pop/5,$b=n&1?-1:1,$c=26799+1425*$b+10*$n*($n*(476+$n*(38+$n))+15*$b),$m=$n%10;
 $c-=4224 if$m|1==1;
 $c+=576+480*$n if$m==2;
 $c-=384 if 1.6*($n-3)|8==8;
 $c-=1344+480*$n if$m==4;
 $c+=5376 if$m-5|1==1;
 $c+=7776+480*$n if$m==7;
 $c-=8544+480*$n if$m==9;
 return$c/24000}