Блог пользователя hmmmmm

Funny sum :)
Автор hmmmmm, история, 9 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +113
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится +148 Проголосовать: не нравится

ahahahahahah, funny

→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится -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})$$$.

    → Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    липстик я наношу на себя липстик

    → Ответить
»
9 месяцев назад, # |
← 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.$$$
→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

ahahahahaha very funny

→ Ответить