4 ms·

It's more surprising that it grows so slowly. 50% of integers are have a factor under 3, 73% - under 6, but then it slows down to a trickle. 88% under 100, and

• 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 ago
    I'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 ago
    Somehow 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?
• demonshalo 10y ago
  I don't find the growth rate surprising at all! > 50% of integers are have a factor under 3 every other number is divisible by 2, that is literally half. > 73% - under 6 Well I think about it this way: every other number is divisible by two, every third number is divisible by 3 and every fifth number is divisible by 5. It just so happens that some of the numbers that are divisible by 2 are also divisible by 3 or 5 such as 10 for instance. Thus the 73% is nor rly surprising. 1/2 + 1/3rd of what remains + 1/5 of what remains - the intersections! > but then it slows down to a trickle. 88% under 100, and just 92% under 1000. I honestly expected it to be a bit lower than 92 but I am clearly wrong about this. Here is an interesting quick visualization I made. Blue are primes, whites are composites! https://imgur.com/a/7EhdI https://imgur.com/a/7EhdI Edit: you can clearly notice a diagonal shape in the pic above. If you however change the table from 5 cols to any N cols, you will get a distinct shape for each N. It's pretty cool to play with actually. There are a ton of shapes that have been known and used for centuries. I'd highly recommend googling around and reading a bit about them on wikipedia!
  • sova 10y ago
    Nice explanation. Thanks! A bit off topic, but how do people make images that are so tall (in px)?
    • demonshalo 10y ago
      Np! I used a chrome plugin called "Full Page Screen Capture". You can use similar extension for FF if you are using that! The table itself is a long html page! :D
  • Grue3 10y ago
    The growth rate of a function obviously has nothing to do with the first few values, I don't know why you would assume those were the ones that surprised me, or that I don't know how to calculate them. What I wanted to point out is that this function approaches its limit (100%) very slowly, much slower than 100(1-1/n), or even 100(1-1/log(n)).
    • demonshalo 10y ago
      > or that I don't know how to calculate them. apologies, I don't know your background nor do I have an insight as to what goes on in your head. All I wanted to point out is that it's actually not a surprising growth rate. And while yes, you are right about the "speed" of the function. However that is not "unexpected". At least I don't find that to be the case personally!