1
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 13 '19 at 23:12
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I know the paragraph second to the last is a bit complicated. Please let me know if you need more explanation upon it. $\endgroup$ – narek Bojikian Nov 13 '19 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy