# Calculating powers of 2 on a 2D grid without factoring.

Consider the following 2D infinitely large grid where the dots represent infinity:

 1   2   3   4   5   6   7   8   9  10 ...
2   4   6   8  10  12  14  16  18  20 ...
3   6   9  12  15  18  21  24  27  30 ...
4   8  12  16  20  24  28  32  36  40 ...
5  10  15  20  25  30  35  40  45  50 ...
6  12  18  24  30  36  42  48  54  60 ...
7  14  21  28  35  42  49  56  63  70 ...
8  16  24  32  40  48  56  64  72  80 ...
9  18  27  36  45  54  63  72  81  90 ...
10  20  30  40  50  60  70  80  90 100 ...
.. ... ... ... ... ... ... ... ... ... ...

• Column and row numbers start at 1 and continue on to infinity.
• The value at each cell is the product of x and y: (x, y) = (x * y)

Now consider all the numbers on this grid that are a power of 2 e.g. 2, 4, 8, etc. Each number appears more than once depending on how many factors it has e.g. 16 = (1, 16), (16, 1), (2, 8), (8, 2), (4, 4).

I am not sure if the answer to my question lies in number or graph theories but here is the pattern I am looking for:

Given some random (x, y) coordinate, where both x and y are extremely large integers, I want to find out if a power of 2 exists on any diagonal cell of (x, y) where a diagonal cell if any (x +/-k, y +/-k) for all integers k.

Since the grid is infinite in size, I cannot loop through each value on the diagonal.

The image below highlights all powers of 2 in yellow and highlights diagonal cells in gray. Note: You can zoom into the image by saving it or opening in a new tab.

-
What do you mean by "any diagonal cell of $(x,y)$"? – Gerry Myerson Aug 5 '12 at 10:45
My guess is cells of the form $(x\pm k, y\pm k)$ for all integers $k$. – marty cohen Aug 5 '12 at 14:05
@GerryMyerson: Marty's comment is correct. When you lay out all integers in the illustrated configuration, I am trying to find out whether there is a specific correlation between (x, y) and all (x+-k, y+-k). I have added an image to the question to better illustrate. – Raheel Khan Aug 5 '12 at 14:24

There is a diagonal cell for $(x,y)$ if and only if the binary representation of $|x-y|$ consists of any number of $1$s (could be none) followed by any number of $0$s or the binary representation of $x+y$ contains at most two $1$s.
For the main diagonals $(x+k,y+k)$ with $k\in\mathbb Z$, we want $(x+k)(y+k)=2^n$ with $n\in\mathbb N_0$, which implies that $x+k=2^{n_x}$ and $y+k=2^{n_y}$ with $n_x,n_y\in\mathbb N_0$. Without loss of generality assume $x\ge y$. Subtracting the two equations yields $x-y=2^{n_x}-2^{n_y}$. Thus $x-y$ is the difference of two powers of two; its binary representation consists of $n_x-n_y$ $1s$ followed by $n_y$ $0$s.
For the minor diagonals $(x+k,y-k)$ with $k\in\mathbb Z$, we want $(x+k)(y-k)=2^n$ with $n\in\mathbb N_0$, which implies that $x+k=2^{n_x}$ and $y-k=2^{n_y}$ with $n_x,n_y\in\mathbb N_0$. Adding the two equations yields $x+y=2^{n_x}+2^{n_y}$. Thus $x+y$ is the sum of two powers of two; its binary representation either has one $1$, if $n_x=n_y$, or otherwise two $1$s in the $n_x$-th and $n_y$-th digits.
@Raheel: I'm not sure what you mean by "in a linear way". You can do this with any prime base $p$ instead of $2$; but note that while for $x+y$ you'll still have at most two $1s$ and $0$s in the remaining digits, for $|x-y|$ you'll have any number of digits $p-1$, not $1$s, followed by any number of $0$s. It doesn't work with composite bases $b$ since in that case you can't conclude from $rs=b^n$ that both $r$ and $s$ are also powers of $b$. – joriki Aug 5 '12 at 15:21
@Raheel: Yes, except you forgot to take the absolute value between subtracting and converting. Also, that's just one of two alternatives, for the minor diagonals; the other one, for the main diagonals, is that the binary representation of $x+y$ contains at most two $1$s. – joriki Aug 6 '12 at 15:30
@Raheel: Well, that's not too surprising, since you immediately return false when you encounter a byte $24$ :-) You didn't consider any of the cases with a string of $1$s in the middle of the byte. Also, why are you returning false for odd numbers? Odd numbers can be the difference between a power of two and $2^0=1$ -- or are you not counting that as a power of two? If you aren't, you'd have to change the function for the minor diagonal accordingly, since it's currently counting bits in the $2^0$ digit. – joriki Aug 7 '12 at 16:09
@Raheel: In line 58, after checking for all patterns that have $0$s on one side and $1$s on the other, you return false. Since $24$ isn't of that form, this line will be reached. By the way, your nice image with the spreadsheet calculation of the diagonals seems to have gotten broken somehow -- it's no longer being shown; I only see the text "Figure 1" where it used to be. – joriki Aug 7 '12 at 23:25