# How many numbers of this form are less than $2^n$?

The following problem arose while studying probability (specifically, while constructing a joint distribution).

Fix $n\in \mathbb{N}$, and consider the integer $2^n$. Let's denote the largest prime less than $2^n$ by $P$.

I know that the prime number theorem gives bounds on $P$, but I want bounds for other expressions. I'm interested in finding bounds for the number of expressions less than or equal to $2^n$ of specified types:

1. What are the largest integers $k_i$ such that $2^{k_3}*3,2^{k_5}*5,...,2^{k_P}*P\le 2^n$?
2. Also, for each prime $p\le 2^n$, what's the largest power of $p$ less than $2^n$?
• bertrand can give $2^{n-1} < p < 2^n$ – Mudream Jun 22 '17 at 1:32

## 2 Answers

For the largest $k_i$ such that $2^{k_i} p_i \leq 2^n$, simply put $\ln$ in both sides we get that $k_i \ln 2+ \ln p_i \leq n \ln 2$ and $k_i \ln 2 \leq n \ln 2 - \ln p_i$ and $k_i \leq \frac{n \ln 2-\ln p_i}{ln 2}$ so the largest $k_i$ is just $k_i = \lfloor \frac{n \ln 2-\ln p_i}{ln 2} \rfloor$.

For the second question, we want to find the largest $k$ such that $p^k \leq 2^n$, also by putting $\ln$ in both sides we get that $k \ln p \leq n \ln 2$ and then $k$ is simply $k \leq \frac{n \ln 2}{\ln p}$ and the largest $k$ is $k=\lfloor \frac{n \ln 2}{\ln p} \rfloor$.

for the first question:

$2^{k_3} * 3 < 2^{k_3} * 4 = 2^{k_3 + 2} \implies k_3 = n-2$

$2^{k_5} * 5 < 2^{k_3} * 8 = 2^{k_3 + 3} \implies k_5 = n-3$

if $P$ is the largest prime $< 2^n$, since $2P > 2^n$, $k_P = 0$

• Regarding your last sentence, I was asking for each prime $p$. – The Substitute Jun 23 '17 at 23:05