4 ms·
Wouldn't the function sort of "eat itself" if it grew too fast? I can't make this precise, but if it grew fast enough, then most numbers would have many factors
by mrkgnao 10y ago
Wouldn't the function sort of "eat itself" if it grew too fast? I can't make this precise, but if it grew fast enough, then most numbers would have many factors accounted for among the smaller numbers already (in a sort of "greedy" manner).
- SomeStupidPoint 10y agoI'm too tired to work out a closed form, but... f_n = (1 - f_(n-1)) * P_n^(-1) + f_(n-1), where f_n is the fraction divisible by the first n primes and P_n is the nth prime. So we can see the faster f_n approaches 1, the faster the first term approaches 0, and the faster f_n ~ f_(n-1). Perhaps doubly so, as if f_n approaches 1 faster, then P_n is smaller and it's reciprocal bigger as well. (We could plug in an estimate for P_n if we were converting to a closed form, to work out the asymptotic implications.)
- pizza 10y agoSomehow it reminds me of the inverse Ackermann function.. Especially how \alpha(n) has to do w. the time complexity of union-find - maybe related to disjoint factors somehow?