0
$\begingroup$

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.

Figure 1

  • 0
    @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.2012-08-05

1 Answers 1

3

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.

  • 0
    joriki, I'm not sure if it is appropriate to solicit professional consultation here. If so, I would highly appreciate a private discussion to see if this would be of any interest to you. The context is, of course, related to the question you have answered. By the way, I have posted a related question [here](http://math.stackexchange.com/q/190998/31055).2012-09-04