For n = 3, there are 6 permutations in total. Among them, a(3) = 2 permutations require the minimum number of comparisons, namely 2, when sorted using binary search: <2,3,1> and <3,2,1>. The remaining permutations, <1,2,3>, <1,3,2>, <2,1,3>, and <3,1,2>, require 3 comparisons. This is the row n = 3 of the triangle in A395685.
g(k)^4 < k holds if and only if k has no divisor d with k^(1/4) <= d <= k^(3/4), if and only if A006530(k)^4 > k^3, i.e., the largest prime factor of k exceeds k^(3/4). Proof: if p = A006530(k) > k^(3/4), every divisor of k is either a multiple of p (hence > k^(3/4)) or a divisor of k/p < k^(1/4). Conversely, if p <= k^(3/4) and p >= k^(1/4), then p itself lies in the excluded range; if all prime factors of k are < k^(1/4), multiplying them one at a time yields a divisor in [k^(1/4), k^(1/2)).
a(n) = A000720(n) for 1 <= n <= 15, since every composite k has a divisor in [2, sqrt(k)], so g(k) >= 2 and g(k)^4 >= 16 > k.
This is the m = 4 member of a family: for each integer m >= 3, the condition g(k)^m < k is equivalent to A006530(k)^m > k^(m-1), giving Sum_{c=2..floor(n^(1/m))} (A000720(floor(n/c)) - A000720(c^(m-1))) = a_m(n) - A000720(n). The case m = 3 is A396205. The equivalence fails for m = 2 (e.g., k = 12).
Limiting density: a(n)/n tends to log(4/3) = 0.28768... (follows from the formula together with the Prime Number Theorem).
For n >= 1, A000720(n) = a(n) - Sum_{c=2..floor(n^(1/4))} ( A000720(floor(n/c)) - A000720(c^3) ).
a(n) ~ n * log(4/3).
EXAMPLE
g(10) = 2 and 2^4 = 16 is not less than 10, so the indicator at k = 10 is 0; hence a(10) = a(9) = 4. (Note A006530(10) = 5 < 10^(3/4), so 10 is counted in A396205 but not here.)
g(22) = 2 and 2^4 = 16 < 22, so the indicator at k = 22 is 1; hence a(22) = 9.
For fixed k, the asymptotic growth of T(n,k) with increasing n follows T(n,k) ~ (2^(2*k-1) / ((2*k)!*g^(4*k-1)*sqrt(Pi))) * n^(2*k - 3/2) * r^(-n), where g=1.13003... and r=0.40270... (eq. 16 of Agranat-Tamir et al., Adv. Appl. Math. 180 (2026), 103131).
a(n) >= 3 * sqrt(3 * n). If x + y + z = q for some constant q < 3 * sqrt(3 * n), then (x * y * z) / (x + y + z) = n if and only if x * y * z = qn. Given the fact that x + y + z = q for some constant q, x * y * z is maximized when x = y = z. So since q < 3 * sqrt(3 * n), x, y, z < sqrt(3 * n), but then (x * y * z) / (x + y + z) < (3n * sqrt(3 * n)) / (3 * sqrt(3 * n)) = n, so x, y, and z are not a viable solution. Thus, there exists no viable solutions when x + y + z < 3 * sqrt(3 * n).
A corollary of this is that when sqrt(3 * n) is an integer, then a(n) = 3 * sqrt(3 * n). In this case, when x = y = z = sqrt(3 * n), (x * y * z) / (x + y + z) = (3n * sqrt(3 * n)) / (3 * sqrt(3 * n)) = n.
a(n) <= 2n + 4, since for all n, if x = 2, y = n, and z = n + 2, (x * y * z) / (x + y + z) = (2 * n * (n + 2)) / (2 + n + (n + 2)) = n, and x + y + z = 2 + n + (n + 2) = 2n + 4. So there always exists a valid solution where x + y + z = 2n + 4. This bound is exactly achieved when n = 1, 2, and 4.
EXAMPLE
If x = 3, y = 4, and z = 7, then (x * y * z) / (x + y + z) = 84 / 14 = 6. We can check that x + y + z = 14 is less than (or at least as good as) any other valid solution. So, a(6) = 14.
MATHEMATICA
a[n_] := Minimize[x + y + z, x*y*z/(x + y + z) == n && x > 0 && y >= x && z >= y, {x, y, z}, Integers][[1]] (* Hugo Pfoertner, Aug 20 2026 *)
The term (1/k^(s-1))/(s-1), here evaluated at k = 2, is found in zeta(s) = lim_{k->oo} (Sum_{n=1..k} 1/n^s+1/(s-1)/k^(s-1)) which is valid for Re(s) > 0. This entry is the Volchkov integral of that term. For the Volchkov integral of 1/n^s evaluated at n = 2 see A336308.
Equals Integral_{t>=0} (1 - 12*t^2)/((1 + 4*t^2)^3) * Integral_{sigma>=1/2} Re(IndefiniteIntegral) dsigma dt where IndefiniteIntegral = Integral_{s} (1/2^(s-1))/(s-1) ds and s has been substituted with s = sigma + i*t.
Equivalently, the number of arrow-type semigroupoids with n objects and no isolated object, up to isomorphism, in the sense of Egri-Nagy and Nehaniv (2025).
a(2) = 6: on two unlabeled points the transitive relations with no isolated point are a->b; a->b with a loop on a; a->b with a loop on b; the two loops a->a and b->b with no arrow between them; a->b with loops on both points; and the complete relation a->b, b->a with loops on both.
