Timeline for How many random sieve operations to decimate the set {2,...,n}?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2015 at 21:15 | comment | added | Serguei Popov | Now I think that the other answer ($\Omega(n/\sqrt{\log n})$) may be true, but I'm pretty sure it should be $o(n)$ in any case. Well, just intuitive feeling :) | |
| Nov 15, 2015 at 19:50 | comment | added | Anthony Quas | I also thought about this heuristic, but I feel it might not be right. It's true that you delete on average $\log n$ numbers in your first step, but (1) much of this is accounted for by very small divisors - which can only be used once; and (2) once you've used up a small divisor, later removals kill off a lot less. My money is on $\Omega(n)$. (Also in the computer experiment, you see a lot of time where "nothing" is being deleted and $\sigma(n)/n$ decreases from $0.28$ when $n=1000$ to $0.24$ when $n=1000000$.) | |
| Nov 15, 2015 at 14:48 | history | answered | Serguei Popov | CC BY-SA 3.0 |