A friend of mine once told me that his phone number, 6425616,
is easy to remember because it is made up of only powers of 2:
"64" + "256" + "16".
This made me wonder how many numbers of various lengths had this
property.
Given ints b and digits, write a method to
compute how many integers of the given number of digits can be formed by
concatenating various powers of the given base. Use only nonnegative
powers of the base (including b^{0}, which equals 1).
For example, given b = 12, and digits = 4, there are
8 such numbers:
1111: "1" + "1" + "1" + "1"
1112: "1" + "1" + "12"
1121: "1" + "12" + "1"
1144: "1" + "144"
1211: "12" + "1" + "1"
1212: "12" + "12"
1441: "144" + "1"
1728: "1728"
