Products that equal a sum and vice versa A fun pair of equivalences is 1 + 5 = 2 &middot; 3 and 1 &middot; 5 = 2 + 3. There are many like these, another one is 1 + 1 + 8 = 1 &middot; 2 &middot; 5 and 1 &middot; 1 &middot; 8 = 1 + 2 + 5. In general a product of n positive integers equals a sum of n positive integers, and vice versa.

In this challenge you must generate all such combinations of positive integers for an input n > 1, excluding permutations. You can output these in any reasonable format. For example, all the possible solutions for n = 3 are:

(2, 2, 2) (1, 1, 6)
(1, 2, 3) (1, 2, 3)
(1, 3, 3) (1, 1, 7)
(1, 2, 5) (1, 1, 8)


The program that can generate the most combinations for the highest n in one minute on my 2GB RAM, 64-bit Intel Ubuntu laptop wins. If your answer uses more than 2GB of RAM or is written in a language I can not test with freely available software, I will not score your answer. I will test the answers in two weeks time from now and choose the winner. Later non-competing answers can still be posted of course.

Since it's not known what the full sets of solutions for all n are, you are allowed to post answers that generate incomplete solutions. However if another answer generates a (more) complete solution, even if their maximum n is smaller, that answer wins.



To clarify, here's the scoring process to decide the winner:


I will test your program with n=2, n=3,  etc... I store all your outputs and stop when your program takes more than a minute or more than 2GB RAM. Each time the program is run for a given input n, it will be terminated if it takes more than 1 minute.
I look at all the results for all programs for n = 2. If a program produced less valid solutions than another, that program is eliminated.
Repeat step 2 for n=3, n=4, etc... The last program standing wins.
C (gcc), n = 50000000 with 6499 results in 59 s

To avoid producing over a terabyte of output consisting almost entirely of 1s, a sequence of (say) 49999995 1s is abbreviated as 1x49999995.



#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

static int n, *a1, k1 = 0, *a2, k2 = 0, s1, p1, *factor;

static void out() {
  if (s1 == p1) {
    for (int i = 0; i &lt; k1 &amp;&amp; i &lt; k2; i++) {
      if (a1[i] &lt; a2[i])
        return;
      else if (a1[i] &gt; a2[i])
        break;
    }
  }

  for (int i = 0; i &lt; k1; i++)
    printf("%d ", a1[i]);
  printf("1x%d | ", n - k1);
  for (int i = 0; i &lt; k2; i++)
    printf("%d ", a2[i]);
  printf("1x%d\n", n - k2);
}

static void gen2(int p, int s, int m);

static void gen3(int p, int s, int m, int x, int q) {
  int r = s - n + k2 + 2;
  int d = factor[q];
  do {
    if (x * d &lt;= m)
      x *= d;
    q /= d;
  } while (q % d == 0);
  do {
    if (q == 1) {
      a2[k2++] = x;
      gen2(p / x, s - x, x);
      k2--;
    } else {
      gen3(p, s, m, x, q);
    }
    if (x % d != 0)
      break;
    x /= d;
  } while (p / (x * q) &gt;= r - x * q);
}

static void gen2(int p, int s, int m) {
  int n2 = n - k2;
  if (p == 1) {
    if (s == n2)
      out();
  } else if (n2 &gt;= 1 &amp;&amp; m &gt; 1) {
    int r = s - n2 + 1;
    if (r &lt; 2 || p &lt; r)
      return;
    if (m &gt; r)
      m = r;
    if (factor[p] &lt;= m)
      gen3(p, s, m, 1, p);
  }
}

static void gen1(int p, int s, int m) {
  int n1 = n - k1;
  p1 = p;
  s1 = s + n1;
  gen2(s1, p1, s + n1 + 1 - n);
  if (n1 != 0) {
    int *p1 = &amp;a1[k1++];
    for (int x = 2; x &lt;= m &amp;&amp; p * x &lt;= s + x + n1 - 1; x++) {
      *p1 = x;
      gen1(p * x, s + x, x);
    }
    k1--;
  }
}

int main(int argc, char **argv) {
  if (argc &lt; 2)
    return 1;
  n = atoi(argv[1]);
  if (n &lt; 2)
    return 1;
  a1 = malloc(n * sizeof(int));
  a2 = malloc(n * sizeof(int));
  factor = calloc(4 * n - 1, sizeof(int));
  for (int p = 2; p &lt; 4 * n - 1; p++)
    if (factor[p] == 0) {
      factor[p] = p;
      for (int i = p; i &lt;= (4 * n - 2) / p; i++)
        factor[p * i] = p;
    } else if (factor[p] &lt; factor[p / factor[p]]) {
      factor[p] = factor[p / factor[p]];
    }
  gen1(1, 0, 3 * n - 1);
  return 0;
}



Try it online!