In general, at the
k
th iteration, the
k
th element in the array gets transposed to the
2k
th position, and won't get touched again until the
2k
th iteration, at which time it gets transposed to the
4k
th position, ad infinitum. A prime doesn't get transposed until its turn comes along, so to speak, so all primes get shuffled forward. But we can easily make a list of the innocent victims simply by printing off the first element to be transposed at iteration 2 and each odd iteration. The list goes: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ... —
Théophile Mar 5 at 13:34