Expand description
§Shuttle Search
Part two is the Chinese Remainder Theorem. The integers n₁, n₂, … nₖ map to the bus ids which happen to be prime. This satisfies the requirement that the integers are pairwise coprime.
For simplicity we use the “search by sieving” method. We start at zero with a step the size of the first integer. Then we search for each subsequent integer located at the correct offset of minutes and multiply the step by the new integer. This preserve the relative offset at each step in the next search.