2^x + 2^y = k

[Farooq Karimi Zadeh]

Hello
This problem suddenly appeared in my mind:
http://far.chickenkiller.com/en/2x-2y-k.html

[PFMLWorker]

Here is the problem statement quoted from the link shared in the original post:

2^x + 2^y = k where x, y and k are positive integers and k is a constant. The question's that for different values of k how many solution does our equation have? For any odd k there is no solution and for positive powers of 2 there is one. We want a general solution for this equation.

[Susam Pal]

We will take this fact for granted: Every positive integer can be uniquely expressed as the sum of distinct powers of 2. In other words, every positive integer has a unique binary representation.

Now consider the case where x = y. Let m = x = y. Then k = 2^m + 2^m = 2^(m+1). Further, if k = 2^(m+1) where m > 1, x = y = m is a solution. There cannot be a solution in which x != y because that would result in another binary representation of k apart from the existing representation of 2^(m+1) which would contradict the uniqueness of the binary representation of k. Therefore there must be exactly 1 solution when k is a positive power of 2.

Now consider the case where x != y. Let x = m and y = n. Then k = 2^m + 2^n = 2^n + 2^m. Thus both (x = m, y = n) and (x = n, y = m) are solutions. There cannot be a solution in which x = y because that would lead to k = 2^(x+1) which violates the uniqueness of the binary representation of k. Also, there cannot be another solution in which either x or y does not belong to {m, n} because that would too violate the uniqueness of the binary representation of k. We conclude that there must be exactly 2 solutions when k is a sum of two distinct positive powers of 2.

For any other positive integer k, no solutions are possible. We can show this by contradiction. Let k be such that it is neither a positive power of 2 nor a sum of two distinct positive powers of 2. If we assume that a solution exists for such k, then we have two positive integers x and y such that 2^x + 2^y = k. If x = y, it contradicts the fact that k is not a positive power of 2. If x != y, it contradicts the fact that k is a sum of two distinct positive powers of 2.

Thus, we can conclude that the equation has exactly 1 solution when k is a positive power of 2, 2 solutions when k is a sum of two distinct positive powers of 2, no solutions otherwise.

Thanks,

Susam

[Farooq Karimi Zadeh]

Thank you Susam Pal for paying attention and spending time on this.

This is obvious that when k is sum of two powers of 2, there is exactly 2 solutions and that when k is power of 2 there is exactly 1 solution to the equation. I knew this already but without proof and now you have provided a proof. Thank you spal!

There is another question: For any given positive integer, k, how can we know if it has solution or not or how many solution does it have?

Again thanks for replying :)

--
Website: https://projectfermat.org/
Slack: https://projectfermat.slack.com/
Join us on Slack: http://bit.ly/pf-slack-invite1
Freenode IRC: https://webchat.freenode.net/?channels=projectfermat
---
You received this message because you are subscribed to the Google Groups "Project Fermat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to projectferma...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/projectfermat/d71f0f08-3b15-406c-8724-e5fd328dc509%40googlegroups.com.

[Susam Pal]

I believe my earlier solution already answers this question. Here is a summary of that solution:

If k > 2 and k is even and k is a power of 2, then the equation has exactly 1 solution. If k > 2 and k is even and k is a sum of two different powers of 2, then k has exactly 2 solutions. Otherwise, there are no solutions.

A succinct way to describe the above conditions would be using the bitcount(k) function that represents the number of 1-bits in the binary representation of k. Here it is:

If k > 2 and k is even and bitcount(k) <= 2, then the equation has bitcount(k) solutions. Otherwise, there are no solutions.

Thanks,

Susam