Solve inequality involving product of x terms

Question

What is the minimum value of $x$ such that

$$1-\prod_{k=0}^{x-1}\left(1-\frac{k}{2^{160}}\right)>0.01$$

is true?

Is there any easy way to solve this without using computational software?

Answer 1

Making the problem more general, consider the equation $$1-\prod_{k=0}^{x-1}\left(1-\frac{k}{a}\right)=\epsilon \tag 1$$ where $a$ is a huge number $(2^{160} \sim 1.46 \times 10^{48})$ and $\epsilon \ll 1$.

Rewriting $(1)$ $$\prod_{k=0}^{x-1}\left(1-\frac{k}{a}\right)=1-\epsilon \tag 2$$ Take logarithms of both sides $$\sum_{k=0}^{x-1}\log\left(1-\frac{k}{a}\right)=\log(1-\epsilon) \tag 3$$ Using Taylor $$\log\left(1-\frac{k}{a}\right)=-\frac{k}{a}+O\left(\frac{1}{a^2}\right)$$ Summing over $k$ $$-\frac{(x-1) x}{2 a} \sim - \epsilon$$ Assuming that $x$ is large $$x^2 \sim 2a \epsilon \implies \color{red}{x\sim \sqrt{2a \epsilon}}$$ So, for your case $x\sim 1.71 \times 10^{23}\sim 2^{77}$.

Computing rigorously for $a=2^{n}$, $\epsilon=0.01$ this would give for the product $$\left( \begin{array}{ccc} n & x & \prod_{k=0}^{x-1}\left(1-\frac{k}{2^n}\right) \\ 10 & 5 & 0.990268 \\ 15 & 26 & 0.990128 \\ 20 & 145 & 0.990093 \\ 25 & 819 & 0.990067 \\ 30 & 4634 & 0.990052 \\ 35 & 26214 & 0.990051 \\ 40 & 148291 & 0.990050 \end{array} \right)$$

Edit

For the inequality, the exact values of $x$ are : $5,26,145,821,4646,26280,148664$

Answer 2

We can certainly do better than what I have in my comment above. Let $w = 2^{160}$ For example,

$1-\prod_{k=0}^{x-1}\left(1-\frac{k}{2^{160}}\right) $

$ = 1 - (1 - \frac{1}{w})(1 - \frac{2}{w})\dots (1 - \frac{x-1}{w})$

Multiplying the outer most two and going inwards, we get: $ = 1 - (1 - \frac{x}{w})^{x/2} \approx \frac{x^2}{2w} > 0.01 \implies x > \sqrt{0.02} * 2^{80} \approx 2^{77} $

where I used $(1 - \frac{1}{w})(1 - \frac{x-1}{w}) \approx 1 - \frac{x}{w}$