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

  • 2
    What do you mean by "any diagonal cell of $(x,y)$"?2012-08-05
  • 0
    My guess is cells of the form $(x\pm k, y\pm k)$ for all integers $k$.2012-08-05
  • 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
    Thank you. Is binary representation only possible in a linear way since we are dealing with powers of 2 or can this be extended to any exponent?2012-08-05
  • 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$.2012-08-05
  • 0
    Thanks. By linear, I simply meant compute as a single function instead of iterations since the space is infinite. I will give this a try and revert back shortly.2012-08-05
  • 0
    Please excuse my lack of exposure to mathematical notation. Have I understood you correctly as follows: For any given (x, y), subtract y from x, convert to binary and check to see if it starts with zero or more consecutive 1's and is followed by all 0's.2012-08-05
  • 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.2012-08-06
  • 0
    Ok, I implemented both major and minor scenarios and manual tests seem to confirm correct results. There is one scenario, however that this approach does not cover. Any given (x, y) can be diagonal to more than one power of 2. In other words, it can lie on a a diagonal intersection of two powers of 2. Any ideas on how to cater to this scenario?2012-08-07
  • 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?2012-08-07
  • 0
    I see. That is exactly what I'm looking for but my implementation always returns either false/false, true/false, false/true pair against the major/minor tests. I never get a true/true result for a given (x, y) which I know to exist on a major/minor pair. Perhaps I'm making a mistake in the algorithm.2012-08-07
  • 0
    @Raheel: Can you post your code, e.g. at [gist](https://gist.github.com/)? And/or specify the numbers for which it's failing.2012-08-07
  • 0
    Here is the url: https://gist.github.com/3286481. An example of an incorrect answer is (36, 12). This is diagonal to (32, 8) and (32, 16). The MajorDiag function returns false while the MinorDiag returns true. The only case where I get true/true is when x is equal to y.2012-08-07
  • 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.2012-08-07
  • 0
    By the way, this is a good example of how not to report a problem. You had a bug in your code, you formed some hypothesis about it (the problem is due to numbers on two diagonals), and you originally reported only your hypothesis to me, as a fact, thus making it impossible for me to independently assess the problem.2012-08-07
  • 0
    Not sure what I was thinking leaving your second point out (1s in the middle)! And yes, I do need to treat 1 as a power of two but did not think of that since the bit pattern suggested at least one 0 at the end. As for returning `false` on byte 24, I'm afraid I don't follow. Could you please point out the exact point in code.2012-08-07
  • 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.2012-08-07
  • 0
    Thanks. I've updated the same gist link with an updated version that seems to pass all tests. Not very elegant but works pretty fast. I can see the excel screen shot by the way.2012-08-08
  • 0
    @Raheel: Strange, it's back for me now, too. Glad the code is working.2012-08-08
  • 0
    Thanks for all your help here. If you are interested, I'd appreciate your opinion on [this question](http://math.stackexchange.com/questions/179078/calculating-powers-of-2-on-a-2d-grid-without-factoring).2012-08-18
  • 0
    @Raheel: You linked to this question itself; I presume you meant [this question](http://math.stackexchange.com/questions/184109/calculating-closest-and-furthest-possible-diagonal-intersections). It seems Ross gave a good answer to that one. In the future, please include links to earlier related questions, such as Gerry provided there, yourself in the question. Otherwise everyone needlessly starts from scratch without being aware of the work done on the related questions.2012-08-19
  • 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