Recently I saw number theory problem in which I need to find amount of pairs (x,y) that gives the solution for x^k + y^k = n, where k and n is given. The only solution I came with is the bruteforce all possible pairs of x,y and check if they equal to n. But I need to do it for big n and k, 1 <= n <= 10^18, 1<=k<=100. What is the most efficient way to do it ?
Asked
Active
Viewed 118 times
0
-
Many possible optimizations, but the first one: there's no need to brute force the *pairs*. For each candidate `x`, find `n - x^k` and figure out whether it's a kth power or not. (You'll want to special-case `k=1`, of course, and there are number-theoretic tricks available for `k=2`, too.) – Mark Dickinson Apr 07 '17 at 10:28
-
Shall `x` and `y` be *positive*? – Dmitry Bychenko Apr 07 '17 at 10:32
-
@DmitryBychenko yes, x and y are natural numbers – MRMKR Apr 07 '17 at 10:39
-
http://math.stackexchange.com/questions/93316/integer-solutions-to-x2y2-n – Dmitry Bychenko Apr 07 '17 at 10:45
1 Answers
3
One possible approach would be to use a hash table.
First, compute all values xk, for which the result is below n. Add each such value into a hash table, mapping xk -> x (and not the other way around, it will be clear in a moment why).
Afterwards, iterate through the keys xk from the hash set, and check whether the complement, i.e. n - xk is also a key in the hash set.
If n - xk is also a key, then the hash table would map it into the value y, such that n - xk = yk, and we identified a valid (x, y) pair.
Otherwise, if n - xk is not a key of the hash table, then there is no solution where x is one element.
There are improvements to the base idea above. For example, if a good pair (x, y) is found, then this means (y, x) is also a good pair. Using this, one could not test for x values above n/2, since this would result in pairs already enumerated.
EDIT
As Dmitry Bychenko noted in the comments section, there are situations where this approach uses a lot of memory, making it less feasible.
This issue is most evident for k = 2, because as k increases, there are significantly fewer x values for which xk < n.
For k = 2, the problem can be approached without using the hash table, but instead directly checking whether n - x2 is a perfect square. To check if a number is a perfect square, one can apply the sqrt function and check whether the result is an integer value.
Another approach, with O(1) space complexity for any k, is to use binary search for checking whether n - xk is the k'th power of an integer. This has a time complexity in the class O(n1/k * log(n))
danbanica
- 2,948
- 8
- 22
-
1if `n <= 10^18` and `k == 2` then we have to compute as many as *billion* items... – Dmitry Bychenko Apr 07 '17 at 11:45