1

I am studying complexity theory and have reduced one of the exercises to the inequality.

$$2^n > (100 \times n)^{(100^{100})}$$

Are there any numeric methods (possibly, programming libraries) that will be able to find smallest natural $n >0$ satisfying it?

It seems the answer is between $100^{101}$ and $100^{102}$.

19aksh
  • 12,768
Evgenii.Balai
  • 299

2 Answers2

5

We can take the logarithm base $2$ both sides multiple times so that this becomes $$n\gt100^{100}\log_2{(100n)}$$ $$100n\gt100^{101}\log_2{(100n)}$$ $$\log_2{(100n)}\gt\log_2{(100^{101}\log_2{(100n)})}$$ $$\log_2{(100n)}\gt101\log_2{(100)}+\log_2{(\log_2{(100n)})}$$ $$\log_2{(100n)}-\log_2{(\log_2{(100n)})}-101\log_2{(100)}\gt0$$ Now using the change of variable $u=\log_2{(100n)}$ we can easily solve numerically $$u-\log_2{(u)}-101\log_2{(100)}\gt0$$ $$\implies u\gt680.439798883638808276845585003099668798973\dots$$ $$\implies100n\gt2^{680.439798883638808276845585003099668798973\dots}$$ $$\implies n\gt\frac1{100}2^{680.439798883638808276845585003099668798973\dots}$$ $$\implies n\gt10^{-2+\log_{10}(2)\times680.439798883638808276845585003099668798973\dots}$$ $$\implies n\gt10^{202.8327897075420269711393974772362736472055405050149061014\dots}$$ $$\implies n\gt100^{101.4163948537710134855696987386181368236027702525074530507\dots}$$ The smallest natural $n$ is then $$n_{\min}=\lfloor100^{101.4163948537710134855696987386181368236027702525074530507\dots}\rfloor+1=$$

68043979888363880827684558500309966879897284660412001587205656323033215984332437665307516658753568774082383857364808060327532323202910496758103569569718034366279018545983239970527758425935354868491153543

which I was able to calculate using Wolfram. Note that the constant $680.439798883638808276845585003099668798973\dots$ can be found explicitly using the Lambert-W function.

Peter Foreman
  • 19,947
  • 1
    You could remove the second half by going back to the first formula for the back-substitution, $$n > n^= 100^{100}\log_2(100n^)=100^{100}u^*=6.8043979888...⋅100^{101}.$$ – Lutz Lehmann Aug 07 '19 at 14:25
  • Yeah you can. I initially thought the OP wanted the answer in the form $n\gt100^k$ so I thought this was a better method. But obviously there are better ways. – Peter Foreman Aug 07 '19 at 15:00
5

The Lambert-W function solves the equation $ye^y=x$. Over the reals, it has two branches, one with index $-1$ mapping $(-e^{-1},0)$ to $(-\infty,-1)$ monotonically falling and the index zero branch mapping $(-e^{-1},\infty)$ to $(-1,\infty)$ monotonically increasing.

Bring the equation into the above form, esp. identify $y$. $$ 2^n>(M⋅n)^N\iff e^{\ln 2 \cdot n/N}>M⋅n\iff -\frac{\ln2⋅n}Ne^{-\frac{\ln2⋅n}N}>-\frac{\ln2}{NM} $$ On the zero branch of the Lambert-W function we get $$ -\frac{\ln2⋅n}N>W_0\left(-\frac{\ln2}{NM}\right)\iff n<-\frac{N}{\ln2}W_0\left(-\frac{\ln2}{NM}\right)\sim\frac1M $$ which gives no solution.

On the other $W_{-1}$ branch we get $$ -\frac{\ln2⋅n}N<W_{-1}\left(-\frac{\ln2}{NM}\right)\iff n>-\frac{N}{\ln2}W_{-1}\left(-\frac{\ln2}{NM}\right) $$ With $M=100$ and $N=100^{100}$ this gives $$ n>\frac{100^{100}⋅471.64492813697046}{\ln 2}=6.804397988836388⋅100^{101} $$ You would need a multi-precision implementation to be able to determine the exact smallest value for $n$. For instance in Magma CAS (online) the scipt

RR := RealField(240);
M := RR!100; N := M^M;
n := M*N;
for k in [1..240] do  n := Log(RR!2,M*n)*N; end for; n;

or with Newton

n := M*N; L2:=Log(RR!2);
for k in [1..7] do n:=n*N*(Log(M*n)-1)/(L2*n-N); n; end for;

gives the result

6804397988836388082768455850030996687989728466041200158720565632303321598433
  24376653075166587535687740823838573648080603275323232029104967581035695697
  18034366279018545983239970527758425935354868491153542.55079187667491436363
  201084068556561
Lutz Lehmann
  • 126,666
  • I might actually delete my answer because I prefer this approach. Note that the exact value of the lower bound for natural number $n$ is $n\ge$68043979888363880827684558500309966879897284660412001587205656323033215984332437665307516658753568774082383857364808060327532323202910496758103569569718034366279018545983239970527758425935354868491153543 if you want to add it to your answer. – Peter Foreman Aug 07 '19 at 13:32
  • I am not very familiar with Magma CAS, so I am curious why 240 is sufficient. But it seems the documentation guarantees that all calculations will be accurate up to 240 decimal digits. Good enough, accepting the answer. – Evgenii.Balai Aug 07 '19 at 15:01