Thought Process

Suppose a number n has a twopal sequence x.

1. Suppose n is odd

   1. If the length of x is even, x can be written as (y, y) where y is half the twopal sequence, but then sum(y) + sum(y) = x is even, a contradiction. Therefore, the length of x must be odd.

   2. Now we know x = (y, z, y) where z is a single odd integer and y is the palindromic component of x. Furthermore, y must contain a 2.

2. Suppose n is even

   1. If length of x is even, x = (y, y) as above

   2. If length of x is odd, x = (y, z, y) as above, note that in this case z can be even (notably it can be 2)

Now I define 2 functions that count the number of palindromic components there are containing no 2's and containing at least one 2, I call them c1(n), c2(n). Importantly note that this palindromic components have no restriction on them, they simply need to sum to n.

1. To compute c1(n), simply pick an integer j and see how many sequences of n - j have no 2's. This is simply the sum from j = 1 to n of c1(n - j), but we have included the sum c1(n - 2) which is invalid since our palindromic component cannot have a 2, hence we have: c1(n) = sum from j = 1 to n of c1(n - j) - c1(n - 2)

2. We compute c2(n) similarly. c2(n) = sum from j = 1 to n c2(n - j) + c1(n - 2). We need to add c1(n - 2) since we may have removed the only 2 in y in which case c2(n - 2) does not include the y's with only one 2.

Now the problem is simple:

1. If n is odd: We are always working with x = (y, z, y) where 2 is an element of y, we we just need to find all y's such that sum(y) = 1 till sum(y) = (n - 1)/2, that is t(n) = sum from i = 1 to (n - 1)/2 c2(i)

2. If n is even: There are 2 possibilities. 

   1. If x = (y, z, y) then we know z must be even, hence sum(y) is from 1 to n/2 - 1,  which gives t(n) = sum from i = 1 to (n/2 - 1) c2(i), however if z = 2 we missed out the cases where y has no 2's, in this case sum(y) = n/2 - 1, so this is exactly c1(n/2 - 1)

   2. If x = (y, y), then it must be that sum(y) = n/2 and contains a 2, so this is exactly c2(n/2)

   3. In total this gives us: t(n) = sum from i = 1 to (n/2 - 1) c2(i) + c1(n/2 - 1) + c2(n/2) = sum from i = 1 to n/2 c2(i) + c1(n/2 - 1)