ways to make change

[Albert Chan]

Extend with the *rare* dollar coin, lets call this a buck (B):
Re-use previous f5 helper function by adding B, 1 at a time, upto b = floor(x/100):

f5 = Sum[(1 + k) * ((1+d) - 5k) * ((1+n-d) - 5k), {k, 0, h}];
f6 = Sum[f5 /. {n -> n-20k, d -> d-10k, h -> h-2k}, {k, 0, b}];

After simplication, this is final result:

Code:

def f6(x):
    n, d, h, b = x//5, x//10, x//50, x//100
    c = (1+d)*(1+n-d)
    t = 80*b - 20*n - 120
    t = t*b + 20*(n+1) + 8*c
    t = t*b + ((-100*h + 30*n - 90)*h - 12*c + 30*n + 10)*h - 14*c + 20
    t = t*b + (h+1)*(h+2)*((75*h - 20*n - 15)*h + 6*c)
    return t * (b+1) // 12
    
def PNDQHB(x): return f6(x) + f6(x-25)

>>> PNDQHB(100) # calculated as PNDQH(100) + PNDQH(0) = 292 + 1 = 293
293

>>> PNDQHB(100000) # how about 1000 dollar ?
13398445413854501L

>>> PNDQHB(int(1e11)) # Billion dollar ? this match internet result!
13333333398333333445333333413833333354500000001L