Mission Integers and Brooklyn Integers are hipster web services that generate unique integers. Cleverly, they cooperate so the integers are unique across both sites. They did it the easy way; Mission returns even numbers, Brooklyn returns odd ones. I wanted to add a third site but there’s no way to do that, they’ve claimed all of the integers already.
So… can you generate integer sequences such that there can be an infinite number of generators with no collision? Supporting any predetermined number N of sites is easy; have site S generate s + n, s + 2n, s + 3n, s + 4n. But what if you don’t know N ahead of time? Yes, with maths!
Let’s say the Nth number that site S generates is the pair (S, N). We need an algorithm that creates a bijective mapping between (S, N) and the integers. Ie, for the current setup, Mission, even numbers, is site 0. Brooklyn, odd numbers, is site 1. The algorithm for number (S, N) is currently return n*2 + s
The trick is creating a bijection from the set of all integers to the set of all pairs of integers. I remember from college math this is possible (the cardinality of the set of all integers Z is the same as the cardinality of the cross product ZxZ) but I’d forgotten the constructive proof. Happily, Wikipedia remembers: something like the Cantor pairing function. http://en.wikipedia.org/wiki/Cantor_pairing_function
And the function for (s, n) is…
The picture is the useful intuition; basically you’re laying the tuples down on a square, then counting off cells.<
This kind of bijection comes in handy as a way to code large 2d spaces into 1d. I feel certain there’s an application for maps.
Here’s my implementation.
The drawback to this approach is the size of the Nth integer is O(N²). Mission integer 18,225,714 is 41,522,085,907,653 or about 2⁴⁵ in the cantor numbering.
See also Part 2
Nelson's log 