# Structures in the multiplication table involving powers of 2

Context:

This started off as a computational problem but stack overflow and similar programming sites failed to contribute to the math concepts behind the problem (albeit simple ones). I am convinced that the answer will make use of elementary concepts / calculations.

Consider set of $T = \{ 2^k \mathrel | k \in \mathbb N \}$ of all powers of 2. Consider the (infinite) multiplication table $F$ of all positive integers:

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

I like to think of this grid as the South East quadrant.

• Columns and rows are indexed by positive integers $x,y \geqslant 1$ (going off to infinity).
• The value of the $(x,y)$ coefficient/cell is just $F_{x,y} = xy$.
• If we concentrate on the elements of $T$, the rows and columns are themselves also powers of 2, so that we have $(x,y) = (2^{e_x}, 2^{e_y})$. We may represent the co-ordinate in the table $F$ even more succinctly by $2^{e_x} + 2^{e_y}$, which ranges over a set of integers which represent a given row/column pair uniquely (if we restrict to $x \leqslant y$, i.e. the upper-triangular portion of $F$).

Now, I am interested in a subset $S$ of co-ordinates in $F$, consisting of all pairs $(j,k) = (2^{e_x} \pm k, 2^{e_y} \pm k)$ ranging over all integers $e_x, e_y, k \geqslant 0$. (When $k > 0$, we refer to this as a "diagonal intersection".)

Observations:

• For any point $(x,y)$ on this grid, I can compute whether the point lies on a diagonal / anti-diagonal by simply looking out for binary patterns (number of 1s etc.).
• For any point $(x,y)$ on this grid, I can compute the closest power of 2 neighbors by manipulating $x$ and $y$ exponents instead of factoring the products by brute force.
• The concentration of powers of 2 and their diagonal intersections decreases as we move away from $(1,1)$ in any direction.

The Problem:

Given a point $(x,y)$ on this grid, I want to calculate $n$ number of neighboring points in $S$ (let's say $n$ is approximately 100).

Calculating $n$ number of neighboring points in $T \times T$ is trivial from a computational perspective, since we can directly manipulate exponents of $x$ and $y$ rather than factors of the product $xy$ for generic co-ordinates in the table. What I cannot seem to grasp is how to efficiently calculate diagonal intersections of neighboring cells that are closest to the given point $(x,y)$. There are some rules which apply to which intersecting points will qualify but that will form an entirely new question.

P.S.: I don't know if this kind of a grid is popular and has a well-known set of properties / patterns. If so, please include links to articles that document the same.

-
I have attempted to clarify some of your question, but I'm not entirely sure what you're looking for. When you speak of diagonal "intersections", what exactly is intersecting? When you refer to "anti-diagonals", what role do you see them playing? By the 'neighbors' of a cell in the table, do you just mean one of the closer cells (so that you're interested something like the closest 100 cells to a given entry of the table, under the constraints you've named for the cells of interest)? If you can try to clarify your question, you stand a better chance of getting a useful answer. –  Niel de Beaudrap Aug 8 '12 at 23:54
Given any random point (x,y), its closest set2 neighbors would be points that are (2^(ex+/-1), 2^(ey+/-1)). So for (63,125), the closest power of 2 neighbors would be (2^5,2^6),(2^5,2^7),(2^6,2^5),(2^6,2^7). To calculate set3, we take set2 and add each point that is a diagonal of every pair-combination of set2 points. As an example take two cells from the above neighboring set2 as (2,32) and (16,4). Now draw diagonal lines against these two points. The four lines will intersect at exactly 2 coordinates. –  Raheel Khan Aug 9 '12 at 0:38
I want to calculate which diagonal intersections are nearest (in linear distance) to the original point (63, 125). –  Raheel Khan Aug 9 '12 at 0:40
To clarify intersections, please have a look at this Excel screen shot (math.stackexchange.com/questions/179078/…). By neighbors, I mean any power of 2 or power of 2 intersections that are closest to (x,y) in linear distance. –  Raheel Khan Aug 9 '12 at 0:53