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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3803 |
2 | jiangly | 3707 |
3 | Benq | 3627 |
4 | ecnerwala | 3584 |
5 | orzdevinwang | 3573 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | Radewoosh | 3542 |
9 | jqdai0815 | 3532 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 163 |
1 | maomao90 | 163 |
3 | adamant | 161 |
4 | maroonrk | 152 |
5 | -is-this-fft- | 151 |
6 | nor | 150 |
7 | atcoder_official | 147 |
7 | SecondThread | 147 |
9 | TheScrasse | 146 |
10 | Petr | 145 |
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?
Название |
---|
ahahahahahah, funny
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})$$$.
липстик я наношу на себя липстик
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
(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
Mertens' third theorem gives an estimate for the product:
($\gamma$ is Euler's constant) The logs cancel so we get
and by Mertens' second theorem, the sum of the reciprocals of primes up to $n$ is about $$$\ln \ln n$$$, so
ahahahahaha very funny