Mathematically navigating a large 2D Numeric grid in C#

Question

I am trying to find certain coordinates of interest within a very large virtual grid. This grid does not actually exist in memory since the dimensions are huge. For the sake of this question, let's assume those dimensions to be (Width x Height) = (Int32.MaxValue x Int32.MaxValue).

  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

Known data about grid:

• Dimensions of the grid = (Int32.MaxValue x Int32.MaxValue).
• Value at any given (x, y) coordinate = Product of X and Y = (x * y).

Given the above large set of finite numbers, I need to calculate a set of coordinates whose value (x * y) is a power of e. Let's say e is 2 in this case.

Since looping through the grid is not an option, I thought about looping through:

int n = 0;
long r = 0;
List<long> powers = new List<long>();
while (r < (Int32.MaxValue * Int32.MaxValue))
{
    r = Math.Pow(e, n++);
    powers.Add(r);
}

This gives us a unique set of powers. I now need to find out at what coordinates each power exists. Let's take 2^3=8. As shown in the grid above, 8 exists in 4 coordinates: (8,1), (4,2), (2,4) & (1, 8).

Clearly the problem here is finding multiple factors of the number 8 but this would become impractical for larger numbers. Is there another way to achieve this and am I missing something?

• Using sets won't work since the factors don't exist in memory.
• Is there a creative way to factor knowing that the number in question will always be a power of e?

Answer 1

Another solution, not as sophisticated as the idea from Commodore63, but therefore maybe a little bit simpler (no need to do a prime factorization and calculating all proper subsets):

const int MaxX = 50;
const int MaxY = 50;
const int b = 6;

var maxExponent = (int)Math.Log((long)MaxX * MaxY, b);

var result = new List<Tuple<int, int>>[maxExponent + 1];
for (var i = 0; i < result.Length; ++i)
  result[i] = new List<Tuple<int, int>>();

// Add the trivial case
result[0].Add(Tuple.Create(1, 1));

// Add all (x,y) with x*y = b
for (var factor = 1; factor <= (int)Math.Sqrt(b); ++factor)
  if (b % factor == 0)
    result[1].Add(Tuple.Create(factor, b / factor));

// Now handle the rest, meaning x > b, y <= x, x != 1, y != 1
for (var x = b; x <= MaxX; ++x) {
  if (x % b != 0)
    continue;

  // Get the max exponent for b in x and the remaining factor
  int exp = 1;
  int lastFactor = x / b;
  while (lastFactor >= b && lastFactor % b == 0) {
    ++exp;
    lastFactor = lastFactor / b;
  }

  if (lastFactor > 1) {
    // Find 1 < y < b with x*y yielding a power of b
    for (var y = 2; y < b; ++y)
      if (lastFactor * y == b)
        result[exp + 1].Add(Tuple.Create(x, y));
  } else {
    // lastFactor == 1 meaning that x is a power of b
    // that means that y has to be a power of b (with y <= x)
    for (var k = 1; k <= exp; ++k)
      result[exp + k].Add(Tuple.Create(x, (int)Math.Pow(b, k)));
  }
}

// Output the result
for (var i = 0; i < result.Length; ++i) {
  Console.WriteLine("Exponent {0} - Power {1}:", i, Math.Pow(b, i));
  foreach (var pair in result[i]) {
    Console.WriteLine("  {0}", pair);
    //if (pair.Item1 != pair.Item2)
    //  Console.WriteLine("  ({0}, {1})", pair.Item2, pair.Item1);
  }
}

Answer 2

The best method is to factor e into it prime components. Lets say they are as follows: {a^m, b^p, c^q}. Then you build set for each power of e, for example if m=2, p=1, q=3,

e^1 = {a, a, b, c, c, c}

e^2 = (a, a, a, a, b, b, c, c, c, c, c, c}

etc. up to e^K > Int32.MaxValue * Int32.MaxValue

then for each set you need to iterate over each unique subset of these sets to form one coordinate. The other coordinate is what remains. You will need one nested loop for each of the unique primes in e. For example:

Lets say for e^2

  M=m*m;
  P=p*p;
  Q=q*q;

  c1 = 1 ;
  for (i=0 ; i<=M ; i++)
  {
    t1 = c1 ;
    for (j=0 ; j<=P ; j++)
    {
      t2 = c1 ;
      for (k=0 ; k<=Q ; k++)
      {
        // c1 holds first coordinate
        c2 = e*e/c1 ;
        // store c1, c2

        c1 *= c ;
      }
      c1 = t2*b ;
    }
    c1 = t1*a ;
  }

There should be (M+1)(P+1)(Q+1) unique coordinates.