0
$\begingroup$

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$?
$\endgroup$
  • 2
    $\begingroup$ bertrand can give $2^{n-1} < p < 2^n$ $\endgroup$ – Mudream Jun 22 '17 at 1:32
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.