Tag Archives: factorial

Euler 113 – Bouncy Numbers


This one has to do with combinatorics and we use the good old fashion binomial coefficient identity (built from factorials or Bang!). Any increasing number can be represented using binary strings. For example, all 3-digit increasing numbers using 0, 1, 2 can be represented with 5-digit binary numbers:

11100 = 000
11010 = 001
11001 = 002
10110 = 011
10101 = 012
10011 = 022
01110 = 111
01101 = 112
01011 = 122
00111 = 222

Which means that there are (5 choose 3) - 1 = 9 of these numbers. The reason for subtracting 1 is that we don’t want to count the number “000”. By extension, all 3-digit increasing numbers with the digits 0-9 requires a binary string containing 3 ones and 9 zeroes and so on. The same can be extended to 10^100.

For decreasing numbers, the only difference is that we might have a zero in the front and end of the string. Note the following pattern of zeros.

111000 = 000
110100 = 002
110010 = 001
110001 = 000 *
101100 = 022
101010 = 021
101001 = 020
100110 = 011
100101 = 010
100011 = 000 *
011100 = 222
011010 = 221
011001 = 220
010110 = 211
010101 = 210
010011 = 200
001110 = 111
001101 = 110
001011 = 100
000111 = 000 *

You can see for 3-digit numbers that “000” will be repeated 3 times after the initial time. For an n-digit number the pattern repeats n times. This gives us (n+10 choose 10) -1 -n. Additionally, numbers like 222 and 11 have both properties. Since we have counted them twice, they need to be removed. There are 9*100 of these numbers which are counted twice.

So this gives us:

Here's the Python code. Its pretty short since we've simplified everything down to a couple binomial calculations.

def bang (x):
    return x > 1 and x * bang (x - 1) or 1

def choose (n, k):
    return bang (n) / (bang (k) * bang (n-k))

if __name__ == "__main__":
    print (int (choose (110, 10) + choose (109, 9) - 1002))

Euler Problem 74

Just iterate, create a list for each, test for replication and increment if 60.

#Euler74
class Algorithms:
    def sumBang(self, strStart):
        sum = 0
        for digit in range(0, len(strStart)):
            bang = 1
            for n in range (2,int(strStart[digit])+1):
                bang *= n
            sum += bang
        return sum
class Problem74:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range (78, self.limit+1):
            result = 0
            L = [n]
            while result != n:
                if len(L) == 1:
                    result = self.Euler.sumBang(str(n))
                else:
                    result = self.Euler.sumBang(str(result))
                if result in L:
                    L.append(result)
                    break
                else:
                    L.append(result)
            if len(L)-1 == 60:
                count += 1
            if n % 10000 == 0:
                print n, count
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem74(1000000)
    print P.Solution()