ways to make change

[Albert Chan]

Come across a funny video on ways to change for a dollar.
What make this even funnier is he spend 2 videos to count cases, but got it wrong !

[Albert Chan]

There is no need to count it all, case by case:
Lets use shorthand, P = penny, N = nickel, D = dime, Q = quarter, H = half-dollar.

Code:

def PN(x): return 1 + x//5

def PND(x): return (1 + x//10) * (1 + x//5 - x//10)

def PNDH(x):
    'Ways with only pennies, nickels, dimes, and half-dollar'
    n, d, h = x//5, x//10, x//50
    return ((50*h-15*n-5)*h + 6*(1+d)*(1+n-d)) * (h+1) // 6

def PNDQ(x): return PNDH(x) + PNDH(x-25)

>>> PNDQ(100) # ways to add to 1 dollar, with pennies, nickels, dimes, quarter
242

>>> PNDQ(100000) # how about 1000 dollars ?
133423351001L

Explanation:
Let x in cents, and n, d, h = floor(x/5), floor(x/10), floor(x/50)

PN ways = Σ (1, k=0 to n) = 1 + n
PND ways = Σ (1 + (n - 2k), k=0 to d) = (1 + d) (1 + n - d)

Adding quarter directly is complicated, since quarter cannot split evenly to dimes.
So, "borrow" a half-dollar, 1 half-dollar = 2 quarters = 5 dimes = 10 nickels.

PNDH ways
= Σ((1 + (d-5k)) * (1 + (n-10k) - (d-5k)), k=0 to h)
= Σ(((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h)
= Σ((1+d)(1+n-d) - 5k*(2+n), k=0 to h) + 25 * Σ(k^2, k=0 to h)
= (h+1) * ((1+d)(1+n-d) - (5h/2)(2+n)) + 25 * h*(h+1)*(2h+1) / 6
= ((50*h-15*n-5)*h + 6*(1+d)*(1+n-d)) * (h+1) / 6

Above formula returns 0 ways for x = range(-65, 0).
To fill the missing counts, PNDQ(x) = PNDH(x) + PNDH(x-25)

[Albert Chan]

(03-02-2019 06:58 PM)Albert Chan Wrote:  PNDH ways = Σ( ((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h )

Extending with all 5 coins (penny, nickel, dime, quarter, half-dollar) is now easy.
Just add quarters to PNDH ways, replacing half-dollar with quarters, 1 at a time.
Let this 5 coins helper function be f5:

f5 ways = Σ( (1+k) * ((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h )

After simplication, this is final result:

Code:

def f5(x):
    n, d, h = x//5, x//10, x//50
    return ((75*h-20*n-15)*h + 6*(1+d)*(1+n-d)) * (h+1)*(h+2) // 12

def PNDQH(x): return f5(x) + f5(x-25)

>>> PNDQH(100) # ways to add to 1 dollar, with pennies, nickels, dimes, quarter, half-dollar
292

>>> PNDQH(100000) # how about 1000 dollars ?
66793412685001L

[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

[Albert Chan]

Found a faster PNDQ change formula: How many ways can you make change, some easy proofs

However, there are many typos on the formula. (see corollary 4.5)
(8530M) should be (85 + 30M), + correcton should be - correction.

Let N = M+2, and simplified all the (-1)^powers, we get:

Code:

def PNDQ(x):
    L, N = x//25, (x%25)//5 + 2
    t = (50*L + 30*N + 25)*L + 6*N*N
    c = (L&1) or (N&1)*2
    return (t*(L+1) - 3*(L+c)) // 24

Correction 3c/24 only contribute at most 6/24 = ¼ ways, thus can be eliminated:

Code:

def PNDQ(x): # revised without correction
    L, N = x//25, (x%25)//5 + 2
    t = (50*L + 30*N + 25)*L + 6*N*N
    return ((t-3)*L + t) // 24

this optimized version match my PNDQ function (build from PNDH), but at 2.5X speed !

[Albert Chan]

We could also build ways formula from 5 points: x%100, x%100 + 1, ... x%100 + 4
Formula is good for cents = n * 100 + x%100

Example, if x%100 = 0, we have dollars ways formula

Code:

1    292  2435 9590  26517 ; forward diff = 5 coins ways, 0 to 4 dollars
291  2143 7155 16927
1852 5012 9772
3160 4760
1600

PNDQH ways   = \(1\binom{n}{0}+291\binom{n}{1}+1852\binom{n}{2}+3160\binom{n}{3}+
1600\binom{n}{4}\)
PNDQHB ways = \(1\binom{n+1}{1}+291\binom{n+1}{2}+1852\binom{n+1}{3}+3160\binom{n+1}{4}+
1600\binom{n+1}{5}\)

Or, use Horner's rule:
PNDQH ways   = ((((200n + 380)n + 238)n + 55)n + 3) / 3
PNDQHB ways = (((((80n + 390)n + 672)n + 483)n + 127)n + 6) / 6

Example, using either set of formulas, for n = 1000 dollars:

PNDQH ways   = 66 793412 685001
PNDQHB ways = 13398 445413 854501