Is this set equidistributed? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T06:12:09Z http://mathoverflow.net/feeds/question/58912 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58912/is-this-set-equidistributed Is this set equidistributed? Changwei Zhou 2011-03-19T09:47:46Z 2011-03-20T11:39:02Z <p>For $n\in \mathbb{N}$ numbers $I_{n}=(1,2,3..n)$ and prime $p$, we define operation $(1,2,3..n)$ to $A=(a_{1},a_{2}...a_{p-1})$ as follows:</p> <p>We arrange the $n$ numbers in a circle, then we eliminate the first number, the $p$th number, the 2$p$th number, etc, until there is only $p-1$ numbers left and the process terminated. We identify this subset as $A$. </p> <p>My question is, for given $p$, does $A$ being equidistributed in $I_{n}$ with $n\rightarrow \infty$? I feel that "equidistributed" in arbitrarily set seems to be not well defined. In this one I want at least for a subset of $I_{n}$ of the form $S=(s,s+1...s+t-1)$. $|S\cap A|\rightarrow \frac{t}{n}*(p-1)$ with $n\rightarrow \infty$. I do not know whether this is possible. A few simple cases (like $p$=3, $n$=2011) is already in need of programming and the result seemed to be very random, I feel "intuitively" this should be true, but I do not know how to prove it.</p> <p>There is some confusion which is obvious from the comment. I mean a circular process that eliminate a certain number, jump $p-1$ numbers in between, and then terminate the next number. This process will stop at the place there are $p-1$ numbers left. </p> <p>An example: $n=20$, $p=5$, we have $(1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19)$ in the first elimination process. Then we have $(1,2,3,4,7,8,9,11,13,14,16,17,19)$ in the second round elimination process, and $(1,2,3,7,11,14,16,17,19)$ in the third round, and $(2,3,7,11,16,17,19)$ in the fourth round, finally yielding $(2,7,11,17)$ in the end. </p> http://mathoverflow.net/questions/58912/is-this-set-equidistributed/58923#58923 Answer by Igor Rivin for Is this set equidistributed? Igor Rivin 2011-03-19T15:04:02Z 2011-03-19T15:40:22Z <p>Not quite an answer to the question but see <a href="http://en.wikipedia.org/wiki/Josephus_problem" rel="nofollow">http://en.wikipedia.org/wiki/Josephus_problem</a></p> <p>There is a huge literature on the Josephus problem -- the wiki article is a good start. See also:</p> <p><a href="http://doc.utwente.nl/67513/1/pospp.pdf" rel="nofollow">http://doc.utwente.nl/67513/1/pospp.pdf</a></p> <p>and the very cool:</p> <p><a href="ftp://ftp.cis.upenn.edu/pub/wilf/josephus.ps" rel="nofollow">ftp://ftp.cis.upenn.edu/pub/wilf/josephus.ps</a></p>