hmmmmm's blog

Funny sum :)
By hmmmmm, history, 9 months ago, In English

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?

  • Vote: I like it
  • +113
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +148 Vote: I do not like it

ahahahahahah, funny

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    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})$$$.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +108 Vote: I do not like it

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.$$$
→ Reply
»
9 months ago, # |
  Vote: I like it -13 Vote: I do not like it

ahahahahaha very funny

→ Reply