Binary Palindrome

The first and last digit must be 1. There are no choices to be had there.

The second, third, and fourth digit can be either 0 or 1; each has 2 ways of occurring, for a total of $2 \times 2 \times 2 = 8$ ways.

The fifth, sixth, and seventh digit must match the second, third, and fourth, so there are no choices there either.

Therefore, there are a total of 8 binary numbers that are 8-digit palindromes (with no leading zeros).

I decided to find a general solution to this problem so that I could find the number of palindromes for any given binary number with n digits. In doing this, we will also find the solution P to this particular case.

I first manually solved how many palindromes there were for all binary numbers ranging from 1 to 6 digits in order to establish a pattern:

n=1: 1
n=2: 11
n=3: 101, 111
n=4: 1001, 1111
n=5: 10001, 10101, 11011, 11111
n=6: 1000001, 101101, 110011, 111111

As seen above, there is one solution for when n=1 and 2, two solutions for when n=3 and 4, and four solutions for when n=5 and 6.

The number of solutions increases by a factor of 2 after every even numbered digit added. When n=2, there is one solution, and when n=3, there are two solutions.

To account for this behavior, I made use of the ceiling function (Represented by [] since my phone does not have the proper symbol). Therefore, the general solution to the problem is:

P = 2^([n/2]-1)

Plugging in 8 for n, we get:

P = 2^([8/2]-1)
P = 2^(4-1)
P = 2^3 = 8