3 ms·
Out 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 m
by tromp 3y ago
Out 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.