# http://projecteuler.net/problem=145
#
# 20 reversible numbers with 2 digits
# 100 reversible numbers with 3 digits
# 600 reversible numbers with 4 digits
# 0 reversible numbers with 5 digits
# 18000 reversible numbers with 6 digits
# 50000 reversible numbers with 7 digits
# 540000 reversible numbers with 8 digits
# 608720 total reversible numbers

# 14s

def rev(num, base):
    'Returns num reversed, where base is 10**(num_digits-1)'
    rev = 0
    while num:
        rev += (num % 10) * base
        num /= 10
        base /= 10
    return rev

def all_odd(num):
    'Returns 1 if all digits of num are odd, else 0'
    while num:
        if num % 2 == 0:
            return 0
        num /= 10
    return 1

def count_reversibles(ndig):
    '''Counts number of reversible numbers are in the range [ 10^ndig-1 , 10^ndig ), ndig >= 2

       Optimizations:
       - A candidate number must have an odd digit in the leftmost place and an even digit in the rightmost,
         or vice versa.  odd/odd or even/even would produce an even digit in the ones column of the sum.
       - You only have to check half of the candidate space, because of symmetry.  Consider only candidates
         with an odd digit in the leftmost place and even in the rightmost, and then double the count.
       - You don't have to bother checking candidates with 0 in the ones place, because that would result
         in a reversed number with a leading zero, which per the rules is to be ignored.
       - Incrementing the ones digit results in the sum increasing by 1 + base, e.g.
           1001 + 1001 = 2002
           1002 + 2001 = 3003 = 2002 + 1 + 1000
         This allows computing the reverse once for each group of 10, and then adding. This can be unrolled
         for speed.
    '''
    count = 0
    base = 10**(ndig-1)
    incr = base * 2 + 2

    for leftmost_digit in (1, 3, 5, 7, 9):
        i = base * leftmost_digit + 2       # rightmost digit = 2
        stop = base * (leftmost_digit + 1)
        while i < stop:
            sum = i + rev(i, base)

            count += all_odd(sum)           # 2
            sum += incr
            count += all_odd(sum)           # 4
            sum += incr
            count += all_odd(sum)           # 6
            sum += incr
            count += all_odd(sum)           # 8

            i += 10

    return count * 2

total = 0
for ndig in range(2, 9):
    c = count_reversibles(ndig)
    total += c
    print c, "reversible numbers with", ndig, "digits"

print total, "total reversible numbers"