4 ms·
As we take the limit as N → ∞, the list continually grows larger. Thus, the number of instances of 37 continually increases, so that they occupy an asymptotical
by LegionMammal978 3y ago
As we take the limit as N → ∞, the list continually grows larger. Thus, the number of instances of 37 continually increases, so that they occupy an asymptotically constant proportion (about 0.963%) of the values in the list; only ~49.061% of the values are less than 37, and only ~49.975% of the values are greater than 37. After a certain point, for even N, there will always be two instances of 37 surrounding the 50% mark in the list, so the median will still be exactly 37, and not some other value. I wrote up a longer explanation in another comment [0].
[0] https://news.ycombinator.com/item?id=38245162 https://news.ycombinator.com/item?id=38245162
- tromp 3y agoOut of the integers 1..2N+1, exactly N have smallest prime factor 2, while the remaining N+1 have smallest prime factor > 2. Thus it is fair to say that the median smallest prime factor is 3 rather than 2.
- tromp 3y agoOops, that's not correct, since 1 has no prime factor. We should instead look at the odd-sized range 2..2N, in which N elements have smallest prime factor 2, making 2 the unique median. Only in even sized ranges 2..2N+1 is the median shared between 2 and 3.
- LegionMammal978 3y agoIn their original paper, De Koninck & Tenenbaum take the convention that the smallest prime factor of 1 is ∞, presumably on the grounds that the minimum value of the empty set is ∞. Under this convention, the range 1..N does make sense, with the median smallest prime factor being 3 for all N ≥ 3 odd, and 2.5 for all N ≥ 4 even. So formally, the limit as N → ∞ wouldn't exist. (They further take the convention that the second-smallest factor of a prime number is ∞, but the choice is ultimately irrelevant for the median of the second-smallest factor, since the primes have natural density 0.)
- tromp 3y agoWhile ∞ is indeed the minimum of the (empty) set of prime factors of 1, it's still not a prime factor, and it feels wrong to include it in median computations.
- deleted 3y ago[deleted]