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