# The number prodigy : reverse sum of pattern

Denote `A[i]` – the i’th digit of `A`.

We first need to understand that to get `N+M=10^X-1`, we need `N[i]+M[i]=9` for all `i`. Since `M[i]=N[X-i]`, it means we need `N[i] + N[X-i] = 9`. This means, once `N[i]` is set, also `N[X-i]`.

We can now derive a recursive formula:

``````F(X) = 10*F(X-2)
``````

The idea is – we look at the first digit of `X`, we have 10 possibilities for it, and for each possibility, we set `N` and `N[X-1]`.

However, this allows leading and trailing zeros, which we don’t want. The first and last number can be anything by 0.

``````G(X) = 8*F(X-2)
``````

The above is chosing one of 1,2,…,8 as `N`, then setting (one option) the last number so `N[X-1] = 9 - N`, and invoke the recursive call without restrictions. Note neither `N` nor `N[X-1]` can be zero.

Base clauses:

``````F(0) = 1
F(1) = 0
``````

`F(1)=0` because there is no natural number `n` such that `n+n=9`.

All in all, we found a recursive formula to compute the total number of elements. This recursive formula can be transformed into a close one with some basic algebra. I leave this part for you.