## Zip Codes

#### Problem

In America they make use of ZIP (Zoning Improvement Plan) codes to help direct mail. Each city/town makes use of a 5-digit code (we shall ignore ZIP+4 codes); for example, Hillsgrove, Pennslyvania, is 18619.

However, due to rotational symmetry certain codes, like the one used for Hillsgrove are detour-prone, as they could be read as a different code upside down. As a result, 61981 (Hillsgrove's ZIP code read upside down) is not used.

How many 5-digit ZIP codes are detour-prone?

#### Solution

We shall consider 18619 and 61981 (its rotational partner) as two separate detour-prone codes.

All detour prone ZIP codes will exclusively contain the digits 0, 1, 6, 8, and 9; that is, 5^{5} = 3125 5-digit numbers.

However, codes like, 66899, are not detour prone, as it reads the same upside down. In fact, any ZIP code with the following criteria will not be detour prone:

- 0, 1, or 8, as middle digit.
- First/second digit is 0, 1, 6, 8, or 9 (with corresponding last/fourth digit will being 0, 1, 9, 8, and 6, respectively.)

This accounts for 5 5 3 = 75.

Hence there are 3125 75 = 3050 detour prone 5-digit ZIP codes.

How many `n`-digit detour-prone ZIP codes are there?