Changing Money

Andrew Neitsch, January 2005

How many ways can you make change for 1 dollar, using 1-, 5-, 10-, 25-, 50-, and 100-cent coins?

In this section, a={1,5,10,25,50,100} is the list of coin denominations.

If we try to solve this with a recurrence relation, we could reason that the number of ways f(n) of making change for n cents is the sum, over all coins we could subtract from n, of the number of ways of making the smaller amount, i.e.

f(k)={({{0,, k<0}, {1,, k=0}, {(∑_(i=1)^(|a|))f(k-(Subscript[a, i])),, k>0}})

Unfortunately, this gives 8,577,874,824,929 ways to make change for a dollar, which cannot be correct as there are only 444,793 integer partitions of 100.

The error in reasoning should be found with the first incorrect result.

({{k, f(k)}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 2}, {6, 3}})

There are only two ways to make change for 6 cents, but f(6)=3. f gives the number of ways of making 5 cents and adding a penny, plus the number of ways of making 1 cent and adding a nickel. When changing money, we would like “1 penny, 1 nickel” and “1 nickel, 1 penny” to be considered as just one way of making change for 6 cents.

We can fix this by adding each type of coin in turn; we will not be able to count different orderings twice if there are no different orderings.

By increasing the dimension of the recurrence relation, we keep track of enough information to actually solve the problem. Let f(n,k) be the number of ways of making change for n cents, using only the first k types of coin.

f(n,k)={({{0,, k<1 or  n<0 }, {1,, n=0}, {f(n,k-1)+f(n-(Subscript[a, k]),k),, else}})

The boundary cases assert that there is exactly one way to make change for 0 cents using a positive number of coins, but there are no ways to make change for negative amounts, or using no coins.

In the non-boundary case, the number of ways of making change using the first k types of coin is the number of ways that don't use that coin, f(n,k-1), together with the number of ways that do, f(n-(Subscript[a, k]),k).

The purpose of describing this, is to give a method to solve this problem by hand. The previous recurrence relation is still too awkward for direct computation, so we present two tricks.

First, the number of ways of making change using only the first type of coin, (which is always assumed to be 1 in this sort of problem so that change can be made for any integral amount), is always exactly 1. Therefore we consider only multiples of 5, which reduces the number of relevant values for n to 21, which is managable by hand.

The following table shows that there are 293 ways to make change for a dollar.

({{n, f(n,1), f(n,2), f(n,3), f(n,4), f(n,5), f(n,6)}, {0, 1, 1, 1, 1, 1, 1}, {5, 1, 2, 2, 2, 2, 2}, {10, 1, 3, 4, 4, 4, 4}, {15, 1, 4, 6, 6, 6, 6}, {20, 1, 5, 9, 9, 9, 9}, {25, 1, 6, 12, 13, 13, 13}, {30, 1, 7, 16, 18, 18, 18}, {35, 1, 8, 20, 24, 24, 24}, {40, 1, 9, 25, 31, 31, 31}, {45, 1, 10, 30, 39, 39, 39}, {50, 1, 11, 36, 49, 50, 50}, {55, 1, 12, 42, 60, 62, 62}, {60, 1, 13, 49, 73, 77, 77}, {65, 1, 14, 56, 87, 93, 93}, {70, 1, 15, 64, 103, 112, 112}, {75, 1, 16, 72, 121, 134, 134}, {80, 1, 17, 81, 141, 159, 159}, {85, 1, 18, 90, 163, 187, 187}, {90, 1, 19, 100, 187, 218, 218}, {95, 1, 20, 110, 213, 252, 252}, {100, 1, 21, 121, 242, 292, 293}})

The rule for updating is that given by the recurrence; for example, 187=f(90,4)=f(90,3)+f(65,4). This table is still too awkward for hand computation, so we present a second trick.

By using the equivalent recurrence relation

f(n,k)={({{0,, k>|a| or  n<0 }, {1,, n=0}, {f(n,k+1)+f(n-(Subscript[a, k]),k),, else}})

the resulting table is sparse, and the numbers are smaller.

({{n, f(n,1), f(n,2), f(n,3), f(n,4), f(n,5), f(n,6)}, {0, 1, 1, 1, 1, 1, 1}, {5, 2, 1,  ,  ,  ,  }, {10, 4, 2, 1,  ,  ,  }, {15, 6, 2,  ,  ,  ,  }, {20, 9, 3, 1,  ,  ,  }, {25, 13, 4, 1, 1,  ,  }, {30, 18, 5, 1,  ,  ,  }, {35, 24, 6, 1,  ,  ,  }, {40, 31, 7, 1,  ,  ,  }, {45, 39, 8, 1,  ,  ,  }, {50, 50, 11, 3, 2, 1,  }, {55, 62, 12, 1,  ,  ,  }, {60, 77, 15, 3,  ,  ,  }, {65, 93, 16, 1,  ,  ,  }, {70, 112, 19, 3,  ,  ,  }, {75, 134, 22, 3, 2,  ,  }, {80, 159, 25, 3,  ,  ,  }, {85, 187, 28, 3,  ,  ,  }, {90, 218, 31, 3,  ,  ,  }, {95, 252, 34, 3,  ,  ,  }, {100, 293, 41, 7, 4, 2, 1}})

Dynamic Programming

This is a specific instance of a more general technique known as dynamic programming, which is often effective in attacking combinatorial problems. It works best with a computer, but with a few tricks, it can be employed by hand.

The general idea of solving a problem this way is to find a recursive solution in which many subcases overlap. The answers to these subproblems can be stored in a table, so that they are never solved more than once.

For example, the coin-changing problem has a great deal of overlap, since we add different coins to the same total many times. In fact, a straightforward computer implementation of the recurrence relation requires 26,905 function calls to f(n,k) in order to find the number of ways to make change for a dollar. But the answer above was found with only 68 computations.

The standard example is the computation of the Fibonacci numbers,

f(0)=f(1)=1
f(n)=f(n-1)+f(n-2)

A straightforward C program to compute f(50),

f(n) {return n<3?1:f(n-1)+f(n-2);}
main(void) {printf("%d\n",f(50));}

makes 25,172,538,049 calls to f(n); only 50 are necessary.

Coin change revisited

The dynamic programming approach to this problem does not work for very large values. By throwing some analytic stuff at it, we overcome this problem. This section follows the relevant part of Graham, Knuth, and Patashnik's Concrete Mathematics.

The generating function for the problem is F(x)=(1/(1-x))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^25)))(1/(1-(x^50)))(1/(1-(x^100))). First we would like to simplify by considering only multiples of 5.

({{F(x)=((1+x+(x^2)+(x^3)+(x^4))/(1-(x^5)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^25)))(1/(1-(x^50)))(1/(1-(x^100)))}, {=(1+x+(x^2)+(x^3)+(x^4))((1/(((1-(x^5)))^2))(1/(1-(x^10)))(1/(1-(x^25)))(1/(1-(x^50)))(1/(1-(x^100))))}, {=(1+x+(x^2)+(x^3)+(x^4))G((x^5))}, {G(x)=(1/(((1-x))^2))(1/(1-(x^2)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^20)))}})

The nth coefficient of the power series of F(x) is the ⌊n/5⌋th coefficient of G(x). G(x) is  (((1-(x^20)))^(-6)) (which has a nice power series) times a polynomial, A(x).

({{G(x)=((A(x))/(((1-(x^20)))^6))}, {A(x)=((((1-(x^20)))^6)/((((1-x))^2) (1-(x^2)) (1-(x^5)) (1-(x^10)) (1-(x^20))))}, {=(((1+x+(x^2)+⋯+(x^19)))^2)(1+(x^2)+⋯+(x^18))(1+(x^5)+(x^10)+(x^15))(1+(x^10))}, {=1+2 x+4 (x^2)+6 (x^3)+9 (x^4)+⋯+24 (x^74)+18 (x^75)+13 (x^76)+9 (x^77)+6 (x^78)+4 (x^79)+2 (x^80)+(x^81)}})

The coefficients of A(x) are

1,2,4,6,9,13,18,24,31,39,50,62,77,93,112,134,159,187,218,252,287,325,364,406,449,493,538,584,631,679,722,766,805,845,880,910,935,955,970,980,985,985,980,970,955,935,910,880,845,805,766,722,679,631,584,538,493,449,406,364,325,287,252,218,187,159,134,112,93,77,62,50,39,31,24,18,13,9,6,4,2,1

Now

G(x)=A(x)(1/(((1-(x^20)))^6))=A(x)(∑_(k=0)^∞)(({{k+5}, {5}}))(x^(20 k))

If G(x)=(∑_(k=0)^∞)(Subscript[g, k])(x^k), and A(x)=(∑_(k=0)^81)(Subscript[A, k])(x^k), then

(Subscript[g, 20q+r])=(∑_({{j,k=0}, {20q+r=20k+j}})^∞)(Subscript[A, j])(({{k+5}, {5}}))

which is essentially a closed form, as for any given n=20q+r, there are at most 5 non-zero terms. This is a Mathematica program to compute the number of ways, f(n), of making change for n cents using pennies, nickels, dimes, quarters, half-dollars, and dollar coins.

a[j_]:=Coefficient[Apart[((((1-(x^20)))^5)/((((1-x))^2) (1-(x^2)) (1-(x^5)) (1-(x^10))))],x,j];
f[n_]:=Block[{v=⌊n/5⌋,q=⌊v/20⌋,r=v~Mod~20},
(∑_(j=0)^4)a[r+20j]Binomial[q+5-j,5]]

Here is the code at work.

Timing[{f[100],f[(10^102)],Short[f[(10^10002)]],Short[f[(10^100002)]]}]

In 2.641 seconds, we computed the number of ways to make change for a dollar (293, just as before), the number of ways to make change for 10 duotrigintillion dollars, as well as for (10^10000) and (10^100000) dollars. The last two are not shown in full, as they are very long; the number of ways to make change for (10^100000) dollars is an integer with 500,002 digits.

The number of ways to make change for (10^(1,000,000)) dollars is an integer 5,000,002 digits long.

Solving Recurrence Relations

There are strong connections between differential equations and difference equations. As with differential equations, recurrence relations can not usually be solved explicity when they are defined by non-linear equations.

Recurrence relations have intriguing properties. The following, up to and including the statement of Sarkovskii's theorem, is taken mostly verbatim from Bendixson Criteria for Difference Equations by C. Connell McCluskey. The proof is referenced to page 63 in An Introduction to Chaotic Dynamical Systems by R. L. Devaney.

Sarkovskii's ordering: the order of the odd integers greater than 1 is reversed, i.e. 3⊳5⊳7⊳⋯. Even multiples are added to the order by (2^n)3⊳(2^n)5⊳⋯, and (2^n)(2i+1)⊳(2^m)(2j+1), if m>n and i,j>0. Powers of 2 are added in decreasing order so that

3⊳5⊳⋯⊳2·3⊳2·5⊳⋯⊳(2^2)·3⊳(2^2)·5⊳⋯⊳(2^n)·3⊳⋯⊳(2^3)⊳(2^2)⊳2⊳1

Theorem (Sarkovskii). If f:ℝ->ℝ is continuous, and has a periodic point of least period k, then if k⊳l, f also has a point of least period l.

In particular, if the recurrence relation (Subscript[a, 0])=(Subscript[a, 0]), (Subscript[a, n+1])=f((Subscript[a, n])) has any periodic orbit, then it must have an orbit of period 2.

If we allow random recurrence relations, i.e. (Subscript[a, n+1])=f((Subscript[a, n])), where f(x)=(Subscript[g, i])(x), where each (Subscript[g, i]) is chosen with probability (Subscript[p, i]), then the result is a fractal if the (Subscript[g, i]) and (Subscript[p, i]) are chosen appropriately.

There are a number of techniques for solving recurrence relations. Generating functions usually work in simple cases. They may remind you of power-series techniques for solving differential equations.

Define the generating function G(x)=(∑_(n=1)^∞)f(n)(x^n), where f(n) is the nth Fibonacci number. We completely ignore questions of convergence; they may get in the way of solving the problem.

({{(∑_(n=1)^∞)f(n)(x^n)=(∑_(n=1)^∞)(f(n-1)+f(n-2))(x^n)}, {=(∑_(n=1)^∞)f(n-1)(x^n)+(∑_(n=2)^∞)f(n-2)(x^n)}, {=x(∑_(n=0)^∞)f(n)(x^n)+(x^2)(∑_(n=0)^∞)f(n)(x^n)}, {-1+G(x)=(x+(x^2))G(x)}, {-1=((x^2)+x-1)G(x)}})

So that G(x)=-1/((x^2)+x-1). Applying the method of partial fractions,

({{G(x)=((-1)/((x^2)+x-1))=(1/((x-((1+(Sqrt[5]))/2))(x-((1-(Sqrt[5]))/2))))}, {=(1/(Sqrt[5]))((1/(x-((1+(Sqrt[5]))/2)))-(1/(x-((1-(Sqrt[5]))/2))))}, {(∑_(n=1)^∞)f(n)(x^n)=(1/(Sqrt[5]))((∑_(n=1)^∞)(((((1+(Sqrt[5]))/2)))^n)-(∑_(n=1)^∞)(((((1-(Sqrt[5]))/2)))^n))}})

Since the two power series are equal, their coefficients must be the same;

f(n)=(1/(Sqrt[5]))((((((1+(Sqrt[5]))/2)))^n)-(((((1-(Sqrt[5]))/2)))^n))

Since ((1-(Sqrt[5]))/2) is small, (1/(Sqrt[5]))(((((1+(Sqrt[5]))/2)))^n) rounded to the nearest integer is equal to f(n).

(1/(Sqrt[5]))((((((1+(Sqrt[5]))/2)))^n))/.n->(-1+Range[20])//N

(1/(Sqrt[5]))((((((1+(Sqrt[5]))/2)))^n)-(((((1-(Sqrt[5]))/2)))^n))/.n->(-1+Range[20])//N

((1-(Sqrt[5]))/2)//N

Fibonacci/@Range[10]

((1/(Sqrt[5]))(((((1+(Sqrt[5]))/2)))^(#)))&/@Range[10]//N

({{G(x)=((-1)/((x^2)+x-1))=((-1)/((x-(1/2) (-1-(Sqrt[5])))(x-(1/2) (-1+(Sqrt[5])))))}, {=}})

(1/(Sqrt[5]))((1/(x-(1/2)(-1-(Sqrt[5]))))-(1/(x-(1/2)((Sqrt[5])-1))))//FullSimplify

Apart[(1/((x^2)+x-1))]

Apart[(1/((x-(1/2) (-1-(Sqrt[5])))(x-(1/2) (-1+(Sqrt[5])))))]

a=(x-(1/2) (-1-(Sqrt[5])));
b=(x-(1/2) (-1+(Sqrt[5])));

((A/a)+(B/b))a b//FullSimplify

Solve[{A+B==0,((A-(Sqrt[5])A+B+(Sqrt[5])B)/2)==1},{A,B}]

((A/a)+(B/b))/.{A->((-1)/(Sqrt[5])),B->(1/(Sqrt[5]))}//FullSimplify

(2/((-1+(Sqrt[5])-2 x) (1+2 x)))//FullSimplify

(-1+(Sqrt[5])-2 x) (1+2 x)//Expand

(1+2 x) (1+(Sqrt[5])+2 x)//Expand

(x-(1/2) (-1-(Sqrt[5])))(x-(1/2) (-1+(Sqrt[5])))//FullSimplify

Solve[(x^2)+x-1==0,x]

3672623805 calls

47: 5942430145 calls
50: 25172538049 calls

25172538050/50

800+250

Fibonacci[5]

Fibonacci[6]

Fibonacci[0]

Fibonacci[1]

Fibonacci[2]

(2^45)

Fibonacci/@(40+Range[10])

Remove[f,g,coins];
coins={1,5,10,25,50,100};
c=0;
f[n_,m_]:=0/;n<0;
f[0,m_]:=1;
f[n_,m_]:=0/;m>Length[coins];
f[n_,m_]:=(c++;f[n,m+1]+f[n-coins[[m]],m]);
f[100,1];
c

f[100,1]

Remove[f,g,coins];
coins={1,5,10,25,50,100};
f[n_,m_]:=0/;n<0||m<1;
f[0,m_]:=1;
f[n_,m_]:=(f[n,m]=f[n,m-1]+f[n-coins[[m]],m]);
Table[If[j==0,i,f[i,j]],{i,0,100,5},{j,0,6}]//MatrixForm

f[0,0]

f[k_]:=0/;k<0;
f[k_]:=(f[k]=f[k-1]+f[k-5]+f[k-10]+f[k-25]+f[k-50]+f[k-100]);
f[0]=1;
{#,f[#]}&/@Range[6]//TableForm

However, this gives the wrong answer for k=6; there are only two ways — all pennies or a nickel and pennies — but this formula will give the answer 3, as

8577828731902

?PartitionsQ

PartitionsQ[100]

Remove[f]

f[k_]:=0/;k<0;
f[k_]:=(f[k]=f[k-1]+f[k-5]+f[k-10]+f[k-25]+f[k-50]+f[k-100]);
f[0]=1

Table[f/@Range[100]]//MatrixForm

#define NUM_COINS 6

int T[101][NUM_COINS];
int coin[NUM_COINS]={1,5,10,25,50,100};

int f(int n,int m) {
	int i;

	if(T[n][m]>0) return T[n][m];
	for(i=m;i<NUM_COINS;i++)
		if(n-coin[i]>=0) T[n][m]+=f(n-coin[i],i);
	return T[n][m];
}

int main() {
	int n;

	for(n=0;n<NUM_COINS;n++) T[0][n]=1;
	printf("%d\n",f(100,0));
	return 0;
}

Prints 293.

?Sum

f[1,1]

f[2,2]

Table[f[i,j],{i,0,10},{j,0,10}]

f(n,k) is the number of ways of making change for n cents using only coins numbered k or higher;

coins={1,5,10,25,50,100};
f[n_,m_]:=0/;n<0;
f[0,m_]:=1;
f[n_,m_]:=Block[{r=0,i},
For[i=m,i≤Length[coins],i++,
r+=f[n-coins[[i]],i]];
f[n,m]=r];

Trace[f[16,0]]

?f

f[2,1]

f[16,0]

f[25,1]

?f

f[25,1]

f[50,1]

coins={1,5,10,25,50,100};
f[n_,m_]:=0/;n<0;
f[0,m_]:=1;
f[n_,m_]:=Block[{r=0,i},
For[i=m,i≤Length[coins],i++,
r+=f[n-coins[[i]],i]];
f[n,m]=r];

g[i_,0]:=i;g[i_,j_]:=f[i,j];
Table[g[i,j],{i,0,100,5},{j,0,6}]//MatrixForm

Remove[f,g,coins];
coins={1,5,10,25,50,100};
f[n_,m_]:=0/;n<0;
f[0,m_]:=1;
f[n_,m_]:=0/;m>Length[coins];
f[n_,m_]:=(f[n,m]=f[n,m+1]+f[n-coins[[m]],m]);
Table[If[j==0,i,f[i,j]],{i,0,100,5},{j,0,6}]//MatrixForm

Remove[f,g,coins];
coins={1,5,10,25,50,100};
f[n_,m_]:=0/;n<0||m<1;
f[0,m_]:=1;
f[n_,m_]:=(f[n,m]=f[n,m-1]+f[n-coins[[m]],m]);
Table[If[j==0,i,f[i,j]],{i,0,100,5},{j,0,6}]//MatrixForm

?f

252+41

218+34

How many ways can you make change for 1 dollar, using 1-, 10-, 25-, 50-, and 100-cent coins?
Since less than 5 cents can only be made up with pennies, we can deal with just multiples of 5.
We make a table with entries giving the number of ways of making change. The row is labelled with the amount we are making change for. The column is headed with the value of the smallest coin we can use.

({{ , 1, 5, 10, 25, 50, 100}, {0, 1, 1, 1, 1, 1, 1}, {5, 2, 1,  ,  ,  ,  }, {10, 4, 2, 1,  ,  ,  }, {15, 6, 2,  ,  ,  ,  }, {20, 9, 3, 1,  ,  ,  }, {25, 13, 4, 1, 1,  ,  }, {30, 18, 5, 1,  ,  ,  }, {35, 24, 6, 1,  ,  ,  }, {40, 31, 7, 1,  ,  ,  }, {45, 39, 8, 1,  ,  ,  }, {50, 50, 11, 3, 2, 1,  }, {55, 62, 12, 1,  ,  ,  }, {60, 77, 15, 3,  ,  ,  }, {65, 93, 16, 1,  ,  ,  }, {70, 112, 19, 3,  ,  ,  }, {75, 134, 22, 3, 2,  ,  }, {80, 159, 25, 3,  ,  ,  }, {85, 187, 28, 3,  ,  ,  }, {90, 218, 31, 3,  ,  ,  }, {95, 252, 34,  ,  ,  ,  }, {100, 293,  ,  ,  ,  ,  }})

coins[3]

Remove[f]

?f

Remove[coins]

coins/@{0,1,2,3,4,5}

?f

f[10,0]

f[100,0]

?f

Remove[f]

?f

?f

f[100,0]

?f

1+1+13+2*13+3*13

Length[IntegerDigits[f[(10^100002)]]]

Length[IntegerDigits[f[(10^1000002)]]]

a1=(((1+x+(x^2)+(x^3)+(x^4)+(x^5)+(x^6)+(x^7)+(x^8)+(x^9)+(x^10)+(x^11)+(x^12)+(x^13)+(x^14)+(x^15)+(x^16)+(x^17)+(x^18)+(x^19)))^2)(1+(x^2)+(x^4)+(x^6)+(x^8)+(x^10)+(x^12)+(x^14)+(x^16)+(x^18))(1+(x^5)+(x^10)+(x^15))(1+(x^10))//Expand

Coefficient[x^81 + 2*x^80 + 4*x^79 + 6*x^78 + 9*x^77 + 
  13*x^76 + 18*x^75 + 24*x^74 + 31*x^73 + 
  39*x^72 + 50*x^71 + 62*x^70 + 77*x^69 + 
  93*x^68 + 112*x^67 + 134*x^66 + 
  159*x^65 + 187*x^64 + 218*x^63 + 
  252*x^62 + 287*x^61 + 325*x^60 + 
  364*x^59 + 406*x^58 + 449*x^57 + 
  493*x^56 + 538*x^55 + 584*x^54 + 
  631*x^53 + 679*x^52 + 722*x^51 + 
  766*x^50 + 805*x^49 + 845*x^48 + 
  880*x^47 + 910*x^46 + 935*x^45 + 
  955*x^44 + 970*x^43 + 980*x^42 + 
  985*x^41 + 985*x^40 + 980*x^39 + 
  970*x^38 + 955*x^37 + 935*x^36 + 
  910*x^35 + 880*x^34 + 845*x^33 + 
  805*x^32 + 766*x^31 + 722*x^30 + 
  679*x^29 + 631*x^28 + 584*x^27 + 
  538*x^26 + 493*x^25 + 449*x^24 + 
  406*x^23 + 364*x^22 + 325*x^21 + 
  287*x^20 + 252*x^19 + 218*x^18 + 
  187*x^17 + 159*x^16 + 134*x^15 + 
  112*x^14 + 93*x^13 + 77*x^12 + 62*x^11 + 
  50*x^10 + 39*x^9 + 31*x^8 + 24*x^7 + 
  18*x^6 + 13*x^5 + 9*x^4 + 6*x^3 + 4*x^2 + 
  2*x + 1,x,#]&/@(Range[82]-1)

a2=(((1-(x^20)))^6)((1/(((1-x))^2))(1/(1-(x^2)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^20))))//Apart

Coefficient[Apart[(((1-(x^20)))^6)((1/(((1-x))^2))(1/(1-(x^2)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^20))))],x,9]

(((1-(x^20)))^6)((1/(((1-x))^2))(1/(1-(x^2)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^20))))

c[q_,r_]:=Sum[aj[r+20j]Binomial[q+5-j,5],{j,0,4}]

a[j_]:=Coefficient[Apart[((((1-(x^20)))^5)/((((1-x))^2) (1-(x^2)) (1-(x^5)) (1-(x^10))))],x,j];
f[n_]:=Block[{v=⌊n/5⌋,q=⌊v/20⌋,r=v-20⌊v/20⌋},
(∑_(j=0)^4)a[r+20j]Binomial[q+5-j,5]]

f[200]

f[100]

a/@(Range[82]-1)

Remove[f]

⌊x⌋

a1 -a2

((1/(((1-x))^2))(1/(1-(x^2)))(1/(1-(x^5)))(1/(1-(x^10)))(1/(1-(x^20))))

Length[IntegerDigits[f[(10^102)]]]