2

Funny sum :)

 6 months ago
source link: https://codeforces.com/blog/entry/125796
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By hmmmmm, history, 2 hours ago, In English

Let — minimal prime divisor of .

I checked that if .

What is actual estimation of this sum?

2 hours ago, # |

ahahahahahah, funny

99 minutes ago, # |

So the rough upperbound is .

  • 90 minutes ago, # ^ |

    ← Rev. 2 →  

    0

    I think it is

49 minutes ago, # |

← Rev. 6 →  

0

After some reasonable assumptions, answer is

seems a small constant of , I have no evidence for it, but it divides stabilizes at in

So this answer is . Anyone points out that I'm wrong.

how retared i'm, missed a simple prove

updd. i forget it's i ln i not i in first sum, answer should be O(n ln ln n)

  • 47 minutes ago, # ^ |

    Can you explain it in more details?

    • 28 minutes ago, # ^ |

      i just assumed i-th prime is exact and the all divisions are uniform, then i swap the order of summation. all of this seems reasonable under n → inf

    • 13 minutes ago, # ^ |

      I can do it in a very informal way.

      So I heard that in all such things one can assume that the number is prime with probability and not prime otherwise and all these events are independent, so I'm going to heavily use it.

      For a prime , how many numbers up to will have as the minimal prime factor? There are about numbers divisible by , and among them about are not divisible by any prime smaller than . According to the lemma above,

      So the answer is about

      Now, according to the observation about the product, this can be rewritten as

  • 30 minutes ago, # ^ |

    Regarding the second paragraph:

    so your product is indeed about (and also some constant error in the numerator because of all the approximations)

13 minutes ago, # |

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 (I'm using 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 (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 , so


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK