Cantor Pairing Function

Question

I'm inspecting the Cantor pairing function, that we can find on this link here.

But the strange thing is that Mathematica is outputting a wrong result to me. The code below shows the strange behavior. When we plot the Q2N1 function, the $y$-axis does not corresponds to the correct value. See:

Q2N0[q_] := (Numerator[q] + Denominator[q] + 1)
            (Numerator[q] + Denominator[q])/2 + Denominator[q]

Q2N[q_] := Q2N0[Rationalize[q]]

Q2N1[q_] := Q2N[N[q, 10]]

Q2N1[0.2]

Out[13]= 26

Plot[Q2N1[x], {x, 0, 1}]

As we can see, confronting the code with the plot, when x = 0.2 the correct value is 26, but Mathematica plot function returns a value near of 2.25. The truth is all returned values should be integers or very near to integers, so 2.25 could never be a result. Crazy.

Why this is happening? And, how can we have the correct output?

Edit

I think that I reached a plot with Mathematica, using some ideas presented in the answers. Looks like the problem was with Rationalize. Doing some tests I have found that need to pass a 0 argument, without it the function 'ignores' Rationalize. See below:

Q2N0[q_] := (Numerator[q] + Denominator[q] + 1)
            (Numerator[q] + Denominator[q])/2 + Denominator[q]

Q2N1[q_] := Q2N0[Rationalize[q, 0]]

Plot[Q2N1[x], {x, 0, 10}]

But I'm still having a problem. FindRoot now brings a strange result. Crazy bis =)

Let's see:

In[125]:= Rationalize[5.588723439378913`, 0]

Out[125]= 97873229/17512627

In[127]:= Q2N1[5.588723439378913`]

Out[127]= 6656947957631923

In[130]:= FindRoot[Q2N1[x] == 26, {x, 0.1}]

Out[130]= {x -> 5.58872}

But Q2N1 is a bijection and Q2N1[x] == 26 when x is 0.2. Even if was not a bijection, Q2N1[5.588723439378913] evaluates to 6656947957631923 instead of 26. (See that when I copied and paste 5.58872, Mathematica paste 5.588723439378913 instead of 5.58872).

So, how can we manipulate this function that it will plot OK (already achieved as looks like) and the FindRoot will find the correct root (or at least try it, instead of brings some strange 5.58872 result?

Answer 1

An alternative to bill's plotting approach would be to only evaluate the pairing function at the members of the Farey sequence (similar to the approach in this answer). Thus,

q2N0[q_Rational] := (Numerator[q] + Denominator[q] + 1)
                    (Numerator[q] + Denominator[q])/2 + Denominator[q]

ListPlot[{#, q2N0[#]} & /@ FareySequence[500], PlotStyle -> AbsolutePointSize[1/10]]

Answer 2

FindRoot cannot provide answers to Q2N[x] == 26, because Q2N (and, equivalently, Q2N1) is not a differentiable function. However, a solution clearly exists, which is the whole point of Cantor Pairing. In fact, Solve provides the answer.

Solve[26 == (n + d + 1) (n + d)/2 + d && n > 0 && d > 0, {n, d}, Integers]
(* {{n -> 1, d -> 5}} *)

where n and d are shorthand for Numerator[x] and Denominator[x]. The result is as expected.

More difficult cases are

Q2N[.21]
(* 7481 *)
Solve[7481 == (n + d + 1) (n + d)/2 + d && n > 0 && d > 0, {n, d}, Integers]
(* {{n -> 21, d -> 100}} *)

Q2N[.213]
(* 737291 *)
Solve[737291 == (n + d + 1) (n + d)/2 + d && n > 0 && d > 0, {n, d}, Integers]
(* {{n -> 213, d -> 1000}} *)

Q2N[.2112]
(* 287528 *)
Solve[287528 == (n + d + 1) (n + d)/2 + d && n > 0 && d > 0, {n, d}, Integers]
(* {{n -> 132, d -> 625}} *)

again as expected. (N[132/625] is, indeed, precisely 0.2112.)

Plot of First 1000 Q2N

For completeness, the solutions for the first 1000 values of Q2N can be plotted.

ListPlot[Table[{i, n/d /. Flatten@Solve[i == (n + d + 1) (n + d)/2 + d && n > 0 && d > 0,
   {n, d}, Integers]}, {i, 1000}], AxesLabel -> {"Q2N[x]", x}]

Note that a solution does not exist for every i, although one does for most i (e.g., 913 of the first 1000).

Answer 3

The problem with discontinuity is severe. One approach to understanding this function is to control exactly what values get evaluated (rather than letting this be handled by Plot). For example, here it is for all fractions between $0$ and $1$ with increment of $1/10000$:

q2N0[q_Rational] := (Numerator[q] + Denominator[q] + 1) 
            (Numerator[q] + Denominator[q])/2 + Denominator[q]; 
xvals = Rationalize[Range[0, 1, 0.0001]];
list = q2N0[#] & /@ xvals;
ListPlot[Thread[{xvals, list}]]

As stated by the OP, the function values are all integers, but they bounce around a lot. I do not think this function is well defined for real numbers, but only for rationals. For example, as I have defined it above, q2N0[2/10] makes sense and is equal to 26 (as you expect) but q2N0[0.2] is undefined. You need to be careful with the domain. You can get another view of the function by plotting using ListLinePlot instead of ListPlot.