Rust

Rust port of @Anders Kaseorg's C answer.

Attempt This Online!

#![allow(unused_imports)]
use std::env;

/// A struct holding all the data and buffers used by the algorithm.
struct Data {
    n: i32,
    // Vectors to store values corresponding to a1 and a2 in the original C code.
    // We pre-allocate them to length n because that's the maximum they might need.
    a1: Vec<i32>,
    a2: Vec<i32>,
    // Indices (k1, k2) into a1 and a2 respectively.
    k1: usize,
    k2: usize,
    // Additional variables translated from the original C code.
    s1: i32,
    p1: i32,
    // Factor array to store smallest prime factors or divisor info.
    // Pre-allocated to length 4*n-1 in the original code.
    factor: Vec<i32>,
}

impl Data {
    /// A direct translation of the `out()` function.
    /// Prints the current factorization or values of a1/a2 subject to conditions.
    fn out_fn(&self) {
        // If s1 == p1, check lexicographical ordering constraints
        if self.s1 == self.p1 {
            for i in 0..self.k1.min(self.k2) {
                if self.a1[i] < self.a2[i] {
                    return;
                } else if self.a1[i] > self.a2[i] {
                    break;
                }
            }
        }

        // If we passed the ordering constraint, print out
        for i in 0..self.k1 {
            print!("{} ", self.a1[i]);
        }
        print!("1x{} | ", self.n - self.k1 as i32);
        for i in 0..self.k2 {
            print!("{} ", self.a2[i]);
        }
        println!("1x{}", self.n - self.k2 as i32);
    }

    /// A direct translation of the `gen3()` function.
    fn gen3(&mut self, mut p: i32, s: i32, m: i32, mut x: i32, mut q: i32) {
        let r = s - self.n + self.k2 as i32 + 2;
        let d = self.factor[q as usize];

        // The first "do { ... } while(q % d == 0)" block in the C code
        // translates to:
        loop {
            if x * d <= m {
                x *= d;
            }
            q /= d;
            if q % d != 0 {
                break;
            }
        }

        // The second "do { ... } while(...)" block in the C code
        loop {
            if q == 1 {
                // a2[k2++] = x
                self.a2[self.k2] = x;
                self.k2 += 1;
                self.gen2(p / x, s - x, x);
                self.k2 -= 1;
            } else {
                self.gen3(p, s, m, x, q);
            }

            if x % d != 0 {
                break;
            }
            x /= d;

            // Check the condition in the while(...) of the second do-while
            if p / (x * q) < r - x * q {
                break;
            }
        }
    }

    /// A direct translation of the `gen2()` function.
    fn gen2(&mut self, p: i32, s: i32, mut m: i32) {
        let n2 = self.n - self.k2 as i32;
        if p == 1 {
            if s == n2 {
                self.out_fn();
            }
        } else if n2 >= 1 && m > 1 {
            let r = s - n2 + 1;
            if r < 2 || p < r {
                return;
            }
            if m > r {
                m = r;
            }
            if self.factor[p as usize] <= m {
                self.gen3(p, s, m, 1, p);
            }
        }
    }

    /// A direct translation of the `gen1()` function.
    fn gen1(&mut self, p: i32, s: i32, m: i32) {
        let n1 = self.n - self.k1 as i32;
        self.p1 = p;
        self.s1 = s + n1;

        // Calls gen2 with adjusted parameters:
        self.gen2(self.s1, self.p1, s + n1 + 1 - self.n);

        // If there's still room (n1 != 0), try to extend
        if n1 != 0 {
            // We'll store the current position in a1 at index k1
            for x in 2..=m {
                // The condition "p * x <= s + x + n1 - 1" from C
                if p * x <= s + x + n1 - 1 {
                    self.a1[self.k1] = x;
                    self.k1 += 1;
                    self.gen1(p * x, s + x, x);
                    self.k1 -= 1;
                } else {
                    break;
                }
            }
        }
    }
}

fn main() {
    // Read command-line argument
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        eprintln!("Usage: {} <n>", args[0]);
        std::process::exit(1);
    }

    let n = args[1].parse::<i32>().unwrap_or(0);
    if n < 2 {
        eprintln!("n must be >= 2");
        std::process::exit(1);
    }

    // Initialize the data structure
    let mut data = Data {
        n,
        a1: vec![0; n as usize],
        a2: vec![0; n as usize],
        k1: 0,
        k2: 0,
        s1: 0,
        p1: 0,
        // The original code allocates factor array with length (4*n-1).
        // e.g. factor = calloc(4*n - 1, sizeof(int)).
        factor: vec![0; (4 * n - 1) as usize],
    };

    // This block builds the factor[] array in a manner similar to the original code:
    //   - factor[p] = p if p is prime
    //   - factor[k * p] = p for multiples of p
    //   - also refine factor[] so factor[p] is the smallest factor or a chain factor.
    let limit = 4 * n - 1;
    // Build smallest prime factor
    for p in 2..limit {
        if data.factor[p as usize] == 0 {
            data.factor[p as usize] = p;
            let mut i = p;
            while p as i64 * i as i64 <= (4 * n - 2) as i64 {
                data.factor[(p * i) as usize] = p;
                i += 1;
            }
        } else {
            // If factor[p] < factor[p / factor[p]], set factor[p] = factor[p / factor[p]].
            let f = data.factor[p as usize];
            let pf = p / f;
            if data.factor[p as usize] < data.factor[pf as usize] {
                data.factor[p as usize] = data.factor[pf as usize];
            }
        }
    }

    // Call the top-level generation function.
    data.gen1(1, 0, 3 * n - 1);
}

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 <stdio.h>
#include <stdlib.h>

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

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

  for (int i = 0; i < k1; i++)
    printf("%d ", a1[i]);
  printf("1x%d | ", n - k1);
  for (int i = 0; i < 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 <= 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) >= 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 >= 1 && m > 1) {
    int r = s - n2 + 1;
    if (r < 2 || p < r)
      return;
    if (m > r)
      m = r;
    if (factor[p] <= 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 = &a1[k1++];
    for (int x = 2; x <= m && p * x <= s + x + n1 - 1; x++) {
      *p1 = x;
      gen1(p * x, s + x, x);
    }
    k1--;
  }
}

int main(int argc, char **argv) {
  if (argc < 2)
    return 1;
  n = atoi(argv[1]);
  if (n < 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 < 4 * n - 1; p++)
    if (factor[p] == 0) {
      factor[p] = p;
      for (int i = p; i <= (4 * n - 2) / p; i++)
        factor[p * i] = p;
    } else if (factor[p] < factor[p / factor[p]]) {
      factor[p] = factor[p / factor[p]];
    }
  gen1(1, 0, 3 * n - 1);
  return 0;
}

Try it online!

Python 2, n=175, 28 results in 59s

Made it a little slower using a reduction factor 2, but gets more solutions starting with n=83

I get results for n up to 92 on TIO in a single run.

def submats(n, r):
    if n == r:
        return [[]]
    elif r > 6:
        base = 1
    else:
        base = 2
    mx = max(base, int(n*2**(1-r)))

    mats = []
    subs = submats(n, r+1)
    for m in subs:
        if m:
            mn = m[-1]
        else:
            mn = 1
        for i in range(mn, mx + 1):
            if i * mn < 3*n:
                mats += [m + [i]]
    return mats

def mats(n):
    subs = []
    for sub in submats(n, 0):
        sum = 0
        prod = 1
        for m in sub:
            sum += m
            prod *= m
        if prod > n and prod < n*3:
            subs += [[sub, sum, prod]]
    return subs

def sols(n):
    mat = mats(n)
    sol = [
        [[1]*(n-1)+[3*n-1],[1]*(n-2)+[2,2*n-1]],
    ]
    if n > 2:
        sol += [[[1]*(n-1)+[2*n+1],[1]*(n-2)+[3,n]]]
    for first in mat:
        for second in mat:
            if first[2] == second[1] and first[1] == second[2] and [second[0], first[0]] not in sol:
                sol += [[first[0], second[0]]];
    return sol

Try it online!

Axiom, n=83 in 59 seconds here

-- copy the below text in the file name "thisfile.input" 
-- and give something as the command below in the Axiom window:
-- )read C:\Users\thisuser\thisdirectory\thisfile

)cl all
)time on

-- controlla che l'array a e' formato da elementi  a.i<=a.(i+1)
tv(a:List PI):Boolean==(for i in 1..#a-1 repeat if a.i> a.(i+1) then return false;true)

-- funzione incremento: incrementa a, con #a=n=b/3,sotto la regola di "reduce(+,a)+#a-1>=reduce(*,a)"
-- e che n<reduce(*,a)<3*n ed reduce(+,a)<3*n 
inc3(a:List PI):INT==
   i:=1; n:=#a; b:=3*n
   repeat
      if i>n  then return 0
      x:=reduce(*,a)
      if x>=b then a.i:=1
      else
          y:=reduce(+,a)
          if y>b then a.i=1
          else if y+n-1>=x then
                      x:=x quo a.i
                      a.i:=a.i+1
                      x:=x*a.i
                      if tv(a) then break
                      else a.i:=1
          else a.i:=1
      i:=i+1
   if x<=n then return inc3(a) -- x<=n non va
   x

-- ritorna una lista di liste di 4 divisori di n
-- tali che il loro prodotto e' n
g4(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y*a.k>n then break
            for h in k..#a repeat
                z:=y*a.h
                if z=n  then r:=cons([a.h,a.k,a.j,a.i],r)
                if z>=n then break 
  r

-- ritorna una lista di liste di 3 divisori di n
-- tali che il loro prodotto e' n
g(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y=n  then r:=cons([a.k,a.j,a.i],r)
            if y>=n then break
  r

-- cerca che [a,b] nn si trovi gia' in r
searchr(r:List List List PI,a:List PI,b:List PI):Boolean==
  aa:=sort(a); bb:=sort(b)
  for i in 1..#r repeat
      x:=sort(r.i.1);y:=sort(r.i.2)
      if x=aa and y=bb then return false
      if x=bb and y=aa then return false
  true

-- input n:PI
-- ritorna r, tale che se [a,b] in r
-- allora #a=#b=n
--        ed reduce(+,a)=reduce(*,b) ed reduce(+,b)=reduce(*,a)
f(n:PI):List List List PI==
  n>100000 or n<=1 =>[]
  a:List PI:=[]; b:List PI:=[]; r:List List List PI:=[]
  for i in 1..n repeat(a:=cons(1,a);b:=cons(1,b))
  if n~=72 and n<86 then  m:=min(3,n)
  else                    m:=min(4,n) 
  q:=reduce(*,a) 
  repeat
    w:=reduce(+,a)
    if n~=72 and n<86 then x:= g(w)
    else                   x:=g4(w)
    if q=w then r:=cons([copy a, copy a],r)
    for i in 1..#x repeat
           for j in 1..m repeat
                  b.j:=(x.i).j
           -- per costruzione abbiamo che reduce(+,a)= prodotto dei b.i=reduce(*,b)
           -- manca solo di controllare che reduce(+,b)=reduce(*,a)=q
           if reduce(+,b)=q and searchr(r,a,b) then r:=cons([copy a, copy b],r)
    q:=inc3(a)
    if q=0 then break
  r

results:

 for i in 2..83 repeat output [i, # f(i)]
   [2,2][3,4][4,3][5,5][6,4][7,6][8,5][9,7][10,7][11,8][12,6][13,10][14,7][15,7]
   [16,10][17,10][18,9][19,12][20,7][21,13][22,9][23,14][24,7][25,13][26,11]
   [27,10][28,11][29,15][30,9][31,16][32,11][33,17][34,9][35,9][36,13][37,19]
   [38,11][39,14][40,12][41,17][42,11][43,20][44,12][45,16][46,14][47,14][48,13]
   [49,16][50,14][51,17][52,11][53,20][54,15][55,17]
   [56,14][57,20][58,17][59,16][60,15][61,28][62,15][63,16][64,17][65,18]
   [66,14][67,23][68,20][69,19][70,13][71,18][72,15][73,30][74,15][75,17][76,18]
   [77,25][78,16][79,27][80,9][81,23][82,17][83,26]
 
 
 f 3
    [[[1,2,5],[8,1,1]],[[1,3,3],[7,1,1]],[[1,2,3],[1,2,3]],[[2,2,2],[6,1,1]]]
                                     Type: List List List PositiveInteger
                                   Time: 0.07 (IN) + 0.05 (OT) = 0.12 sec

The way for run above text in Axiom, would be, copy all that text in a file, save the file with the name: Name.input, in a Axiom window use ")read absolutepath/Name".
results: (# f(i) finds the length of the array f(i), that is the number of solutions)

Haskell, a lot of solutions fast

import System.Environment

pr n v = prh n v v

prh 1 v l = [ [v] | v<=l ]
prh n 1 _ = [ take n $ repeat 1 ]
prh _ _ 1 = []
prh n v l = [ d:r | d <-[2..l], v `mod` d == 0, r <- prh (n-1) (v`div`d) d ]

wo n v = [ (c,k) | c <- pr n v, let s = sum c, s>=v,
                   k <- pr n s, sum k == v, s>v || c>=k ]

f n = concatMap (wo n) [n+1..3*n]

main = do [ inp ] <- getArgs
          let results = zip [1..] $ f (read inp)
          mapM_ (\(n,s) -> putStrLn $ (show n) ++ ": " ++ (show s)) results

f computes the solutions, the main function adds getting the input from the command line and some formatting and counting.

Haskell, n=10 with 2 solutions

import           Data.List

removeDups = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []
removeDups' = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []

f n= removeDups $ map sort filterSums
  where maxNumber = 4
        func x y = if (((fst x) == (fst.snd$y)) && ((fst y) == (fst.snd$x)))
                     then [(snd.snd$x),(snd.snd$y)]
                     else [[],[]]
        pOf = removeDups' $ (map sort (mapM (const [1..maxNumber]) [1..n]))
        sumOf = map (\x->((sum x),((product x), x))) pOf
        filterSums = filter (\x-> not$(x == [[],[]])) (funcsumOfsumOf)

This performs like crap, but I at least fixed it so I am actually addressing the challenge now!

Try it online!

Mathematica, n=19 with 11 solutions

this is my new answer according to OP's new criteria

(SOL = {};
For[a = 1, a < 3, a++, 
For[b = a, b < 3, b++, 
For[c = b, c < 5, c++, 
 For[d = c, d < 6, d++, 
  For[e = d, e < 3#, e++, 
   For[k = 1, k < 3, k++, 
    For[l = k, l < 3, l++, 
     For[m = l, m < 5, m++, 
      For[n = m, n < 6, n++, For[o = n, o < 3#, o++,
        s = Join[Table[1, # - 5], {a, b, c, d, e}];
        t = Join[Table[1, # - 5], {k, l, m, n, o}];            
        If[Tr[s[[-# ;;]]] == Times @@ t[[-# ;;]] && 
          Tr[t[[-# ;;]]] == Times @@ s[[-# ;;]], 
         AppendTo[SOL,{s[[-#;;]],t[[-#;;]]}]]]]]]]]]]]];
Union[SortBy[#,Last]&/@SOL])&

if you give an input [n] at the end, the program displays the solutions

here are my results (on my old laptop 64-bit 2.4GHz)

n->solutions
2 -> 2
3 -> 4
4 -> 3
5 -> 5
6 -> 4
7 -> 6
8 -> 5
9 -> 7
10 -> 7
11 -> 8
12 -> 6 (in 17 sec)
13 -> 10 (in 20 sec)
14 -> 7 (in 25 sec)
15 -> 7 (in 29 sec)
16 -> 9 (in 34 sec)
17 -> 10 (in 39 sec)
18 -> 9 (in 45 sec)
19 -> 11 (in 51 sec)
20 -> 7 (in 58 sec)

Ruby, n=12 gets 6 solutions

At least on TIO, usual results for 1 up to 11

->n{
  arr=[*1..n*3].product(*(0..n-2).map{|x|
    [*1..[n/3**x,2].max]|[1]
  }).select{|a|
    a.count(1) >= n-4
  }.map(&:sort).uniq
  arr.product(arr).map(&:sort).uniq.select{|r|
    r[0].reduce(&:+) == r[1].reduce(&:*) &&
    r[0].reduce(&:*) == r[1].reduce(&:+)
  }
}

Try it online!

Gets 10 results under a minute for n=13 on my laptop.

Mathematica, n=293 with 12 solutions

OP changed the challenge and asks for input
Here is the new code that takes any n as input
For n=293 you get the 12 solutions

If[#<5,Union[Sort/@Select[Tuples[{1,2,3,4,5,6,7,8,9},{#}],Tr@#==Times@@#&]],For[a=1,a<3,a++,For[b=a,b<3,b++,For[c=b,c<5,c++,For[d=c,d<10,d++,For[e=d,e<300,e++,If[Tr[s=Join[Table[1,#-5],{a,b,c,d,e}]]==Times@@s,Print[s]]]]]]]]&

input

[n]

You can test this algorithm on Wolfram Sandbox which is an online freely available software
Just follow the link, paste the code (ctrl+v),paste input at the end of the code and press shift+enter to run.
You will get all my solutions in seconds

Here is also Try it online! in C++(gcc)
(Many thanks to @ThePirateBay for supporting and translating my code to a free language)

this program generates only solutions of the form {a,b,c}{a,b,c}
which means a+b+c=a*b*c

It takes 1 sec to compute

the twelve solutions are:

{1,1...,1,1,1,2,293} {1,1...,1,1,1,2,293}
{1,1...,1,1,1,3,147} {1,1...,1,1,1,3,147}
{1,1...,1,1,1,5,74} {1,1...,1,1,1,5,74}
{1,1...,1,1,2,2,98} {1,1...,1,1,2,2,98}
{1,1...,1,1,2,3,59} {1,1...,1,1,2,3,59}
{1,1...,1,1,2,5,33} {1,1...,1,1,2,5,33}
{1,1...,1,1,2,7,23} {1,1...,1,1,2,7,23}
{1,1...,1,1,2,8,20} {1,1...,1,1,2,8,20}
{1,1...,1,1,3,3,37} {1,1...,1,1,3,3,37}
{1,1...,1,1,3,4,27} {1,1...,1,1,3,4,27}
{1,1...,1,1,3,7,15} {1,1...,1,1,3,7,15}
{1,1...,1,2,2,6,13} {1,1...,1,2,2,6,13}