Skip to main content
6 of 6
edited body; added 18 characters in body; deleted 2 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The down function is moving along (something essentially equivalent to) the usual Cantor pairing function $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, since it moves from each point on a diagonal $x+y=\text{constant}$ to the next point until the diagonal runs out at the y-axis, and then it jumps to the next lower diagonal.

Meanwhile, the cane function counts how many times that happens before you hit the origin. So the cane function is the precisely a version of the usual Cantor pairing function. Your function differs from the usual function in that it swaps $x$ and $y$ from the usual function, since Cantor's function goes down and to the right, rather than up and the to left as with your recursion; but this is an inessential difference. In the end, the function maps a pair $(x,y)$ to the code of that pair.

In fact, the function $\text{cane}(x,y)$ is a quadratic polynomial in $x$ and $y$, and I challenge you to figure out the precise formula. All you need to do is to count the number of points on earlier diagonals, which is a triangular number, and then count the number of points on the current diagonal up to the point $(x,y)$. This gives a quadratic formula for $\text{cane}(x,y)$.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k