The number prodigy : reverse sum of pattern

by

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.

More Related Contents:

  1. Calculate distance between two latitude-longitude points? (Haversine formula)
  2. Unique (non-repeating) random numbers in O(1)?
  3. Circle line-segment collision detection algorithm?
  4. How do I calculate a point on a circle’s circumference?
  5. Fast permutation -> number -> permutation mapping algorithms
  6. Algorithm to detect intersection of two rectangles?
  7. Sort points in clockwise order?
  8. How do you calculate the average of a set of circular data? [closed]
  9. How do Trigonometric functions work? [closed]
  10. Precise subpixel line drawing algorithm (rasterization algorithm)
  11. Finding out nth fibonacci number for very large ‘n’
  12. Algorithm for finding similar images
  13. Why does this simple shuffle algorithm produce biased results?
  14. Mapping N-dimensional value to a point on Hilbert curve
  15. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  16. Floating Point Divider Hardware Implementation Details
  17. nᵗʰ ugly number
  18. Unsupervised clustering with unknown number of clusters
  19. Calculate largest inscribed rectangle in a rotated rectangle
  20. Two Rectangles intersection
  21. Circle-circle intersection points
  22. How do I find a factorial? [closed]
  23. Calculating the position of points in a circle
  24. Strategies for simplifying math expressions
  25. How to express tetration function, for complex numbers
  26. How to check if an integer is a power of 3?
  27. “Rounding” colour values to the nearest of a small set of colours
  28. How to generate a power set of a given set?
  29. determine if a point sits inside an arbitrary shape?
  30. Location of highest density on a sphere

Leave a Comment