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.