+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not remotely HP Calculators (/forum-9.html)
+--- Thread: ways to make change (/thread-12541.html)
ways to make change - Albert Chan - 03-02-2019 05:37 PM
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 !
RE: ways to make change - Albert Chan - 03-02-2019 06:58 PM
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)
RE: ways to make change - Albert Chan - 03-02-2019 10:33 PM
(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
RE: ways to make change - Albert Chan - 03-03-2019 06:05 PM
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
RE: ways to make change - Albert Chan - 03-04-2019 04:31 PM
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)) // 24Correction 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) // 24this optimized version match my PNDQ function (build from PNDH), but at 2.5X speed !
RE: ways to make change - Albert Chan - 03-05-2019 10:17 PM
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
1600PNDQH 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