ways to make change

[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 !