Funny sum :)
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.
Let — minimal prime divisor of .
I checked that if .
What is actual estimation of this sum?
2 hours ago, # | ahahahahahah, funny |
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) |
-
Can you explain it in more details?
-
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
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 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK