Ivan Pervushin was a 19th-century Russian amateur mathematician, employed as a cleric, who factored two Fermat numbers and discovered the ninth Mersenne prime \( 2^{61}-1 = 2305843009213693951 \). But despite these obvious reasons for fame, his Wikipedia article was in such bad shape (e.g. completely unsourced) that it was recently put up for a deletion discussion, which it survived.

While looking for more sources for this article, I ran across what Google numbers as page 140 of Ripley's Believe It or Not!: In Celebration... A special reissue of the original! (Simon and Schuster 2011), which seems to describe a different reason for Pervushin's number \( 2^{61}-1 \) to be interesting. It writes (in somewhat hyperbolic language) that this is the number of different ways of making change for $5, using U.S. currency ("cents, nickels, dimes, quarters, halves, and dollars"). Not convinced, I wrote a Python program based on a simple dynamic programming algorithm to compute the number of ways of making change for $5 (also allowing a $5 bill to be used itself, but that only changes the answer by one):

N = [0]*501
N[0] = 1

for c in [500,100,50,25,10,5,1]:
    for i in range(501-c):
        N[i+c] += N[i]

print N[500]

The output was \( 98412 \) (Tacoma), much smaller than the number in the book. (The problem is also briefly discussed here with essentially the same answer, \( 98411 \) if the $5 bill is not counted as a solution.) In retrospect, the small size of this number should not have been a surprise. To make change for n cents using a fixed set of \( c \) different coins, the number of possible solutions is asymptotically \( O(n^{c-1}) \): each solution can be represented as a \( c \)-dimensional vector of how many coins of each value to use, but the coefficient for the pennies is determined by all the other coefficients. And the leading constant in the \( O \)-notation is very small (much smaller than 1) because you can't use anywhere near \( n \) of the larger denomination coins. So a polynomial bound with a moderate exponent and a small constant shouldn't generate huge numbers.

But then I thought: maybe they have a different definition of what it means for two ways of making change to differ. It couldn't be that the coins of the same value are distinguishable (different years or mint marks, or different state-by-state obverse designs on the quarters) because then the answer wouldn't be well defined: it would depend on how many different coins of each type you happen to have and not merely on the value of the amount to be changed and the fixed system of coin values. But maybe the order in which I hand you the change matters: if I give you four dollar bills and then four quarters, it's a different way of making change than giving you the quarters first and then the dollars? To test this, I made a small modification to my program to calculate the number of distinct sequences of coins and bills (rather than the number of distinct multisets) that would add to the given amount:

N = [0]*501
N[0] = 1

for i in range(501):
    for c in [500,100,50,25,10,5,1]:
        if (i-c >= 0):
            N[i] += N[i-c]

print N[500]

But this time the output was much higher than the published amount: It was \( 1296142333713114950908964121341365887827473814688245139610006400624 \). Asymptotically the number of solutions is exponential (because what we are computing is just a linear recurrence) but even with a low base, exponentiating \( 500 \) produces big numbers. So this raises a puzzle: can anyone come up with a reasonable definition of the problem for which the Ripley answer is correct?

(G+)