by dalkeon 3/8/2015, 1:42:58 PM

I didn't understand the title. I thought it would be a math trick to determine if a number was divisible by 14, in your head. (Eg, check if the number is even, and use the technique for testing for divisibility by 7.)

Instead, it counts the number of numbers in a range which have a "14" in the base-10 expression, using Python code like:

   len(["14" in str(i) for i in range(10**n)])

Followed by a more clever recursive solution:

    def counting(n):
        if n == 2:
            return 1
        elif n < 2:
            return 0
        return 10 * counting(n-1) - counting(n-2) + 10**(n-2)

It ended there, but I'll continue a bit further. As with the recursive Fibonacci implementation, this takes exponential time in n - try counting(100). A linear rewrite gives:

    def counting2(n):
        if n < 2:
            return 0
        prev = 0
        curr = 1
        for i in range(3, n+1):
            prev, curr = curr, 10*curr - prev + 10**(i-2)
        return curr

where counting2(100) = 6339...7499