3
$\begingroup$

Let $k$ be a fixed positive integer or even positive real number. Let $n$ be a large integer. I am interested in the following question:

What is the probability that the largest prime power divisor of $n$ is smaller than $(\log(n))^k$?

Surely this probabilty goes to $0$ when $n$ goes to infinity, but I wonder how fast it goes to $0$. For example, by the prime number theorem, every integer $n$ has a prime power divisor bigger than $(1 - \epsilon)\log(n)$, so for $k < 1$, this probability is actually $0$. For $k \approx 1$ I reckon this probability should be around $\frac{1}{n}$, and I think that if we replace $(\log(n))^k$ by $c \log(n)$ for some $c > 1$, then something close to $\frac{1}{n}$ should still hold, maybe $\frac{1}{n^{1 + o(1)}}$. In any case, I have no clue as to what happens for $k > 1$, so I would love to know.

$\endgroup$
1
$\begingroup$

It's an approximation, So we want the probability of B-smooth such that $B= \ln^k(n)$.

Which means that it must be divisible by primes less than $\ln^k(n)$, which means that for some number $1<m<n$, m to be $\ln^k(n)$-smooth it must not be divisible by any prime between $\ln^k(n)$ and $n$.

The probability that a number is divisible by prime $p$ is $\frac{1}{p}$ and the probability that its not divisible by $p$ is $1-\frac{1}{p}$, and we want it to be not divisible by any prime between $\ln^k(n)$ and $n$ which means $\prod \limits_{\ln^k(n) < p \leq n} 1-\frac{1}{p}$ which is equal to $\prod \limits_{i=\pi(\ln^k(n))}^{\pi(n)} 1-\frac{1}{p_i}$, now we can approximate this by $\pi(x)=\frac{x}{\ln(x)}$ and $p_i=i \ln(i)$ and $\prod f(x) = e^{\sum \ln(f(x))}$,substituting that we arrive at

$e^{\sum \limits_{i=\pi(\ln^k(n))}^{\pi(n)}\ln(1-\frac{1}{i \ln(i)})} \approx e^{-\int \limits_{i=\pi(\ln^k(n))}^{\pi(n)} \frac{1}{i \ln(i)}} di = \frac{\ln(\pi(\ln^{k}(n)))}{\ln(\pi(n)} = \frac{\log \left(\frac{\log ^k(n)}{\log \left(\log ^k(n)\right)}\right)}{\log \left(\frac{n}{\log (n)}\right)} $

A good approximation is : $$\frac{\log \left(\frac{\log ^k(n)}{\log \left(\log ^k(n)\right)}\right)}{\log \left(\frac{n}{\log (n)}\right)}$$

$\endgroup$
  • $\begingroup$ the approximation is effective when $\ln^{k+1}(n) < n$. $\endgroup$ – Ahmad May 5 '17 at 13:00
  • $\begingroup$ This looks as if you only consider prime divisors. But I don't want my numbers to have prime power divisors bigger than $\log^k(n)$ either. Does that change the asymptotic? $\endgroup$ – Woett May 5 '17 at 13:15
  • $\begingroup$ Actually, I may have convinced myself it indeed should not change the asymptotic, since the number of primes in the interval $[log^k(n), n]$ is asymptotically the same as the number of prime powers in that interval. $\endgroup$ – Woett May 5 '17 at 13:28
  • $\begingroup$ @Woett yes, also i took it to the minimal approximation since $\pi(x)$ is better approximated by $Li(x)$ and $p_i = i(\ln(n)+\ln(\ln(n))-1)$ which is way better than the one i used, but it will be complicated to approximate, surely there is a way better approximation than the one i calculate. $\endgroup$ – Ahmad May 5 '17 at 14:01
  • $\begingroup$ Oh, no worries. I'm just trying to formulate a heuristic for myself for something I'm working on, so any approximation should suffice. Thank you very much! $\endgroup$ – Woett May 5 '17 at 14:17

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.