project euler problem 113 https projecteuler netproblem113 working from lefttoright if no digit is exceeded by the digit to its left it is called an increasing number for example 134468 similarly if no digit is exceeded by the digit to its right it is called a decreasing number for example 66420 we shall call a positive integer that is neither increasing nor decreasing a bouncy number for example 155349 as n increases the proportion of bouncy numbers below n increases such that there are only 12951 numbers below onemillion that are not bouncy and only 277032 nonbouncy numbers below 1010 how many numbers below a googol 10100 are not bouncy calculate the binomial coefficient cn r using the multiplicative formula choose4 2 6 choose5 3 10 choose20 6 38760 calculate the number of nonbouncy numbers with at most n digits nonbouncyexact1 9 nonbouncyexact6 7998 nonbouncyexact10 136126 calculate the number of nonbouncy numbers with at most n digits nonbouncyupto1 9 nonbouncyupto6 12951 nonbouncyupto10 277032 calculate the number of nonbouncy numbers less than a googol solution6 12951 solution10 277032 calculate the binomial coefficient c n r using the multiplicative formula choose 4 2 6 choose 5 3 10 choose 20 6 38760 calculate the number of non bouncy numbers with at most n digits non_bouncy_exact 1 9 non_bouncy_exact 6 7998 non_bouncy_exact 10 136126 calculate the number of non bouncy numbers with at most n digits non_bouncy_upto 1 9 non_bouncy_upto 6 12951 non_bouncy_upto 10 277032 calculate the number of non bouncy numbers less than a googol solution 6 12951 solution 10 277032
def choose(n: int, r: int) -> int:
    
    ret = 1.0
    for i in range(1, r + 1):
        ret *= (n + 1 - i) / i
    return round(ret)


def non_bouncy_exact(n: int) -> int:
    
    return choose(8 + n, n) + choose(9 + n, n) - 10


def non_bouncy_upto(n: int) -> int:
    
    return sum(non_bouncy_exact(i) for i in range(1, n + 1))


def solution(num_digits: int = 100) -> int:
    
    return non_bouncy_upto(num_digits)


if __name__ == "__main__":
    print(f"{solution() = }")