s = 3; /* we are dealing with factors (s + 1/t[i]) where s >= 2 */

nTuples(n, p, onlyOne = 0, showTuples = 0) = {
  /*
    Return the number of tuples (t1,...,tn) of integers 2 <= t1 <= ... <= tn
    with (s + 1/t1) * ... * (s + 1/tn) = p.
    If showTuples = 1, then print the tuples.
    If onlyOne = 1, then search only until the first tuple was found.
  */

  return(if (p % s == 0, 0, nTuples0(n, p, 0, 1, vector(n), onlyOne, showTuples)));
};

nTuples0(n, p, m, u, t, onlyOne, showTuples) = {
  my(count = 0,
    i = m + 1,
    v = p/u,
    r = 1 / (v/s^(n-m-1) - s), /* t[i] > r */
    w,
    c
  );

  t[i] = if (denominator(r) == 1, r + 1, ceil(r));
  t[i] = max(t[i], if (i == 1, 2, t[m]));

  if (t[i] % s == 0, t[i]++);

  while (v <= (s + 1/t[i])^(n-m),
    w = u * (s + 1/t[i]);

    if (i == n - 1,
      t[n] = 1 / (p/w - s);

      if (t[n] >= t[i] && denominator(t[n]) == 1,
        if (showTuples, print(t, " : ", p));
        if (onlyOne, return(1));
        count++;
      ),

      c = nTuples0(n, p, i, w, t, onlyOne, showTuples);
      if (c > 0 && onlyOne, return(1));
      count += c;
    );

    t[i]++;
    if (t[i] % s == 0, t[i]++);
  );

  return(count);
};

a355626(n) = sum(p = s^n + 1, (s + 1/2)^n, nTuples(n, p));

a355627(n) = sum(k = ceil(log(n) / log(s + 1/2)), floor(log(n) / log(s)), if (k == 0, 0, nTuples(k, n)));

a355628(n) = sum(p = s^n + 1, (s + 1/2)^n, nTuples(n, p, 1));

a355629(n) = nTuples(n, s^n+1);

a355630(n) = forstep (p = floor((s + 1/2)^n), s^n + 1, -1, if (nTuples(n, p, 1), return(p)));

a355631_data(N) = {
  for (p = 1, N,
    for (k = ceil(log(p) / log(s + 1/2)), floor(log(p) / log(s)),
      if (k > 0 && nTuples(k, p, 1), print1(p, ", "); next(2));
    );
  );
};

a355631_bfile(N) = {
  my(c = 0);

  for (p = 1, N,
    for (k = ceil(log(p) / log(s + 1/2)), floor(log(p) / log(s)),
      if (k > 0 && nTuples(k, p, 1), print(c++, " ", p); next(2));
    );
  );
};

/*

A355626 data : for (n = 1,   4, print1(a355626(n), ", "))

A355627 data : for (n = 1,  90, print1(a355627(n), ", "))
A355627 bfile: for (n = 1, 243, print(n, " ", a355627(n)))

A355628 data : for (n = 1,   8, print1(a355628(n), ", "))

A355629 data : for (n = 1,   4, print1(a355629(n), ", "))

A355630 data : for (n = 2,  14, print1(a355630(n), ", "))

A355631 data : a355631_data(280)
A355631 bfile: a355631_bfile(30000)

*/