# Tracing diagonal numbers on a 2D grid or matrix.

I need to test a cell on a 2D grid/matrix to see if it's diagonal numbers have a power of 2 in them.

Example:

    C0 C1 C2 C3 C4 C5 C6 C7 C8 C9
R0: 00 01 02 03 04 05 06 07 08 09
R1: 10 11 12 13 14 15 16 17 18 19
R2: 20 21 22 23 24 25 26 27 28 29
R3: 30 31 32 33 34 35 36 37 38 39
R4: 40 41 42 43 44 45 46 47 48 49
R5: 50 51 52 53 54 55 56 57 58 59


The size of the grid is known. The values in each cell are simply ((R*W)+C) where:

• R=Row Number
• W=Width of Grid
• C=Column Number

Now let's pick two random cells:

• C3R4 = 43. Has diagonal values of (10, 21, 32, 54) & (07, 16, 25, 34, 52) out of which 16 and 32 are powers of 2.
• C8R1 = 18. Has no diagonal values that are powers of 2.

Required Result: f(x, y) = True or False.

Question:

• Is there a way to detect the above without looping?
• If this is not possible in a linear way, what would be the most efficient way to loop?
-
In the first line, you ask about $x^2$, but in the rest of the question, you ask about powers of 2. They are not the same thing. Which do you really mean? Can you edit the question accordingly, please. – Gerry Myerson Jul 26 '12 at 6:18
How would your grid look if $C\geq 10$? – draks ... Jul 26 '12 at 6:49
A simple way, without thinking would be to generate a list of squares or powers or etc, find their coordinates using $C = n \mod W$ and $R = \lfloor n/W \rfloor$ and then check if they are in the same diagonal. If they are, $|x_1 - x_2| = |y_1 - y_2|$. For a faster method, you'll have to clarify the question. – Karolis Juodelė Jul 26 '12 at 6:57
You probably wanted 'constant' instead of 'linear'. The most brute search of the diagonals would be 'linear'. – Karolis Juodelė Jul 26 '12 at 6:59
@KarolisJuodelė: Please excuse my lack of exposure to notation. How could I express the above as a function or algorithm? – Raheel Khan Jul 26 '12 at 20:24

## 1 Answer

If you assume $y$ to be even and $x\leq y$. Start at $(x,y)=10x+y$, the following values lie on

• the antidiagonal $S_a=\{-x\leq z\leq y\; :\; 10(x+z)+(y-z)\}$ and
• the diagonal $S_d=\{x\leq z\leq y\; :\; 10(x-z)+(y-z)\}$.

So there are $|S_d|+|S_a|-1=(y+x+1)+(x-y+1)=2x+2-1=2x+1\;$ values at all, which is linear ($\pm 1$'s because you count the value itself twice). Convert your values in binary form to see if it's a power of $2$.

-
Please excuse my lack of exposure to notation. The equations are greek to me. Could you explain the same as a function or algorithm please? – Raheel Khan Jul 26 '12 at 20:21
@RaheelKhan Pick your example $18=10*1+8$ (since I assumed $x\leq y$). So $x=1, y=8$. For the set of entries on antidiagonal $S_a$, you have the following entries: 1. $z=-x=\color{red}{-1}$, so $10(1+\color{red}{(-1)})+(8-\color{red}{(-1)})=10(0)+9=07$ 2. $z=0$, that $18$ again 3. $z=1$ gives $10(1+1)+(8-1)=27$ and so forth till $z=y=8$, which gives $10(1+8)+(8-8)=90$. Here I extended your grid in the row dimension. This is how you get the first set. – draks ... Jul 26 '12 at 22:21
Thanks. Does your equation assume a square grid? I also did not understand 2x+1 since it does not take into account the height of the grid. I used Pythagoras to figure out the number of diagonal cells. – Raheel Khan Jul 26 '12 at 22:27