Say you want to sample from a sequence of length n. Multiples of a number that is relatively prime to the length of the sequence (n) cover the entire sequence and have the property that the entire sequence is covered before any number is repeated. This is a known result from number theory. We could use the result to (sequentially) (see below for what I mean) sample from a series.
For instance, if the sequence is 1, 2, 3,…, 9, the number 5 is one such number (5 and 9 are coprime). Using multiples of 5, we get:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| X | ||||||||
| X | X | |||||||
| X | X | |||||||
| X | X | |||||||
| X | X |
If the length of the sequence is odd, then we all know that 2 will do. But not all even numbers will do. For instance, for the same length of 9, if you were to choose 6, it would result in 6, 3, 9, and 6 again.
Some R code:
seq_length = 6
rel_prime = 5
multiples = rel_prime*(1:seq_length)
multiples = ifelse(multiples > seq_length, multiples %% seq_length, multiples)
multiples = ifelse(multiples ==0, seq_length, multiples)
length(unique(multiples))
Where can we use this? It makes passes over an address space less discoverable.