The following function represents a probability. The left-hand side is arbitrary, let's call it $\frac12$. How to solve for $m$ where $m, n > 0$? $$\frac{1}{2}=\left[1 - \left(\frac{1}{m}\right)^{(m^m)}\right]^{2n}$$
In case it's relevant, this equation is for a computation complexity bound that I am working on, so it'd technically be permissible to make substitutions which don't affect the resulting O(...), in case that's helpful.
I do not think there is a satisfactory exact answer to this. Rather: $1/m^{m^m}$ is falling with $m$. So the function is strictly increasing. Use simple bisection to approximate your solution to arbitrary precision.
You are seeking a solution to:
$$m^m\log m=-\log\left(1-2^{-1/(2n)}\right)\tag1$$
That doesn’t seem to have a closed solution. It might have a solution in terms of the Lambert $W$ function, but if there is, I’m not seeing it.
Some form of numeric solution is required. The right side is constant, and the left side increases rapidly, so you should be able to quickly find the integer part of $m.$
When $n$ is very large, $$2^{-1/(2n)}= 1-\frac{\log 2}{2n}+O\left(\frac1{n^2}\right)$$ so the right side of (1) is $$-\log\left(\frac{\log2}{2n}\right)-\log(1+O(1/n))=\log(2n)-\log\log 2+O(1/n)$$
For example, when $n<2\times 10^{12},$ you have $m$ between $2$ and $3.$
As @Thomas Andrews wrote, you are looking for $m >0$, the zero of function
$$f(m)=m ^m\,\log(m)+\log \left(1-2^{-\frac{1}{2 n}}\right)$$ Alas, Lambert function is of no use and numerical method are required.
Using $n=2^k$, the results, obtained using Newton method, have been fitted according to the empirical model $$m=a\, k^b$$ With $R^2=0.999984$ the results are $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & 1.77198 & 0.00447 & \{1.76299,1.78096\} \\ b & 0.14148 & 0.00077 & \{0.13993,0.14303\} \\ \end{array}$$
Trying for $n=123456789$, this would give $m=2.82288$ while the solution is $2.82861$.
