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 Answer 1

Reset to default
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$
7
  • $\begingroup$ the approximation is effective when $\ln^{k+1}(n) < n$. $\endgroup$
    – Ahmad
    May 5, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 14:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .