Thursday: Is it all odds, or just primes?

Considering the problem from yesterday, assume you have N boxes and an infinite number of sets of M objects that you must insert into boxes in sequence.  Box 1 gets item 1, when you reach box N, you move back to box 1.  When you get to item M, you continue to the second set of M objects, and insert item 1 of that set into your box.  When does this method preferentially sort item m into box n?

This is basically just a modulus, so you can tell that if item m fell into box n last time, it will fall into the box (M-N) next time it comes around.  Therefore, N=M has a shift of zero, so it's the case that's maximally sorted: item m always falls into box n.

For both N and M even, (M-N) = 2K, so an even m can only fall into an even n, and an odd m can only fall into an odd n.  Therefore, the concentration of m should be something like 0.5 * (1/N).

The odd cases are where I start having problems.  N,M both odd also has a shift equivalent to 2K, so that should have concentrations of 0.5 * (1/(N -1)), 0.5 * (1 / (N + 1).  I think.

The odd/even cases should be symmetric, and should also have a maximal sorting.  However, I'm not entirely convinced that it's fully random (1/N) unless the odd number is prime, or at least has no factors that are also factors of the even number.  My number theory isn't all that strong to argue this with logic, and I'm too lazy to search for counter-examples numerically tonight.

• Bunny race.
• Nameable characters.
• Spogetyi.
• Math game.  I had to cheat on the final level