Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
@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
1  
@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
1  
@Raheel: I'm not sure I understand your question correctly. A number can't be written as the sum of two powers of two in two different ways, or as the difference of two powers of two in two different ways, so every (major or minor) diagonal contains at most one pair of powers of two. Thus this can only occur if both tests succeed, i.e. there is a pair of powers of two both on a major and on a minor diagonal. If that's the case you're thinking of, I don't understand what the question is. Both tests succeed, so you know there's a hit on both diagonals. How is this not covered? –  joriki Aug 7 '12 at 14:41
1  
@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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.