Sunday, 30 January 2011

co.combinatorics - Average distance between numbers of the form 2a3b

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
frac1r1sum(ai+1ai)=(ara1)/(r1).



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