# Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$

For example $$46$$ is a perfect number , since $$4+6=10$$ . If $$n=1$$ , answer is $$19$$. If $$n=2$$ , answer is $$28$$. If $$n=3$$ , answer is $$37$$ and so on .We need to make a program which takes $$n$$ and outputs $$n'th$$ perfect number.

How to solve this problem for large $$n$$ , for example $$n$$ close to $$10^{18}$$ ? we can't use brute force method since input can be so large .Can we solve it using DP or binary search ?

Source of the problem : Perfect Number

Note: In given problem statement (in link) $$n$$ is not large and thus can be solved using brute force.But i am curious to solve it for large $$n$$.

• I'd just like to note that this is not the standard definition of "perfect number", which is one that is equal to the sum of its proper divisors. – David Richerby Nov 13 '19 at 23:12

I will describe a method running in $$O(|n|) = O(\log n)$$ where $$|n|$$ is the length of the number written in decimal representation. We will follow a dynamic programming scheme. For each $$k \in \{0, \dots 10\}$$ and each positive integer $$j \leq n$$ we will compute the number of integers of length $$k$$, whose sum of digits is equal to $$k$$. This can be computed using dynamic programming where $$C(k, j) = \sum\limits_{i\in\{0, \dots k\}}C(k-i, j-1),$$ since we can add $$i$$ to the left of a number of length $$j-1$$ and sum $$k-i$$ to construct a number of length $$j$$ and sum $$k$$.
Let $$P$$ be a prefix sum over $$C(10, j)$$ for $$j = 0, 1 \dots$$, clearly $$P(i)$$ tells how many integeres of length at most $$i$$ sum up to 10. Now the solution to you problem can be fond recursively by finding the greatest $$i$$ such that $$P(i) \leq n$$ and subtract it from $$n$$. This $$i$$ tells the lengths of your number. And the result of the subtraction is the order of your number among numbers of length $$i+1$$. Now you can find the left most digit of your number by trying to set the left most number to some value \$k \in {1 \dots 9} and checking how many ways you can construct the rest of the number.
I suspect the solution can be found in $$O(\log |n|) = O(\log\log n)$$ by only building $$C(k, 2^r)$$ for integers $$r$$ and binary search for the greatest value of $$r$$ where $$C(10, 2^r)$$ is at most $$n$$.