The point of this answer is simply to repeat Scott's answer in a more visible place. If he wants to post it himself, I'll delete my post:
Let ai be the sequence of these integers, sorted into order. Let arleqN<ar+1. We want to estimate
frac1r−1sum(ai+1−ai)=(ar−a1)/(r−1).
As Scott explains,
r=(1/2)cdot(logN/log2+O(1))cdot(logN/log3+O(1))=(logN)2/(2log2log3)+O(logN).
Also, there is clearly a power of 2 between N and N/2, so arsimN.
So the average distance is simN/(logN)2. If you work harder, you can probably tighten up the bounds to show that it is N(2log2log3)/(logN)2(1+O(1/logN))
No comments:
Post a Comment