ways to make change - Printable Version +- 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)) // 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 ! 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 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