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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.