### hmmmmm's blog

By hmmmmm, history, 2 weeks ago,

Let $p_i$ — minimal prime divisor of $i$.

$s(n) = \sum_{i=2}^n \lceil \log_2(p_i) \rceil$.

I checked that $s(n) \leq 4 \cdot n$ if $n \leq 10^{10}$.

What is actual estimation of this sum?

• +103

 » 2 weeks ago, # |   +148 ahahahahahah, funny
•  » » 2 weeks ago, # ^ |   -21 Stupid mods deleted my proof, so there it is again:$s(n) = \sum_{i = 2}^{n}\lceil \log_2(p_i) \rceil \leq \sum_{i = 2}^{n}\lceil \log_2(i) \rceil \leq \sum_{i = 2}^{n}\lceil \log_2(n) \rceil < n\log_2(n) < n ^ {69}$So the upperbound is $O(n^{69})$.
•  » » 2 weeks ago, # ^ |   +16 липстик я наношу на себя липстик
 » 2 weeks ago, # | ← Rev. 2 →   +108 Please correct me if I'm wrong, but I think you can get a rough estimate like this (if you ignore the ceilings).By Inclusion-Exclusion the contribution of a prime $p_i \leq n$ (I'm using $p_1, p_2, \dots$ to denote the primes) is approximately $\log_2(p_i) \cdot (\frac{n}{p_i} - \sum\limits_{S \subseteq \{1, 2, \dots, i-1\}} (-1)^{|S| - 1} n \prod\limits_{j \in S} \frac{1}{p_j}).$(I'm saying approximately since you would need floors to get an exact answer.)You can rearrange this as $\frac{n\log_2(p_i)}{p_i} \prod\limits_{j=1}^{i-1} (1 - \frac{1}{p_j})$ (try expanding the product to see why). So $s(n) \approx n \sum\limits_{p_i \leq n} \frac{log_2(p_i)}{p_i} \prod\limits_{p_j < p_i} (1 - \frac{1}{p_j}).$Mertens' third theorem gives an estimate for the product: $s(n) \approx n \sum\limits_{p_i \leq n} \frac{\log_2(p_i)}{p_i} \frac{e^{-\gamma}}{\ln {p_i}}.$($\gamma$ is Euler's constant) The logs cancel so we get $s(n) \approx \frac{1}{\ln 2} \cdot e^{-\gamma} n \sum\limits_{p_i \leq n} \frac{1}{p_i},$and by Mertens' second theorem, the sum of the reciprocals of primes up to $n$ is about $\ln \ln n$, so $s(n) \approx \frac{e^{-\gamma}}{\ln 2} \cdot n \cdot \ln \ln n.$
 » 2 weeks ago, # |   -13 ahahahahaha very funny