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[0] 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[0], then setting (one option) the last number so N[X-1] = 9 - N[0], and invoke the recursive call without restrictions. Note neither N[0] 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.

Browse More Popular Posts

Leave a Comment