# One-to-one correspondence between pairs of integers and the positive integers

It is well-known that there are one-to-one correspondences between pairs of integers and the positive integers. Your task is to write code defining such a correspondence (by defining a pair of functions/programs that are inverses of each other) in your programming language of choice, plus a correctness check (see below) with the smallest number of bytes for the correspondence definition (not taking the correctness check into account).

The solution must include :

• the definition of a function/program f having two integer arguments and returning an integer (that's one direction of the bijection).

• either the definition of a function/program g having one integer argument and returning a pair of integers (might be an array, a list, the concatenation of the two integers separated by something ...) or two functions/programs a and b having an integer argument and returning an integer (that's the other direction).

• an additional code snippet checking that for the f and g (or f and a,b) you defined above, you have g(f(x,y))=(x,y) (or a(f(x,y))=x and b(f(x,y))=y) for any integers x,y in the range -100 < x < 100,-100 < y < 100. Note that f and g have to work for values outside of this range as well.

You may rename a,b,f or g of course. The two solutions do not have to be written in the same language.

Below is a not-optimal-at-all solution in PARI/GP, with 597 characters for the function definitions.

plane_to_line(x,y)={
my(ax,ay,z);
ax=abs(x);
ay=abs(y);
if((ax<=ay)*(y<0),        z=4*y*y-2*y+x+2;);
if((ax<=ay)*(y>=0),       z=4*y*y-2*y-x+2;);
if((ay<=ax)*(x<0),        z=4*x*x    -y+2;);
if((ay<=ax)*(x>=0)*(y<0), z=4*x*x+4*x+y+2;);
if((ay<=ax)*(x>=0)*(y>=0),z=4*x*x-4*x+y+2;);
if((x==0)*(y==0),z=1;);
return(z);
}

line_to_plane(z)={
my(l,d,x,y);
l=floor((1+sqrt(z-1))/2);
d=z-(4*l*l-4*l+2);
if(d<=l,x=l;y=d;);
if((l<d)*(d<=3*l),x=2*l-d;y=l;);
if((3*l<d)*(d<=5*l),x=(-l);y=4*l-d;);
if((5*l<d)*(d<=7*l),x=d-6*l;y=(-l););
if((7*l<d)*(d<8*l) ,x=l;y=d-8*l;);
if(z==1,x=0;y=0;);
return([x,y]);
}


and the correctness-check code :

accu=List([])
m=100;
for(x=-m,m,for(y=-m,m,if(line_to_plane(plane_to_line(x,y))!=[x,y],\
listput(accu,[x,y]);)))
Vec(accu)

• We've already done the second part of this but I guess the fact that both functions need to be each other's inverse might be sufficient interaction to justify a multi-part challenge. Apr 26 '16 at 10:03
• @MartinBüttner I'm not sure independent multi-part works. Part of the challenge is to pick the encoding that gives you the shortest functions. Apr 26 '16 at 10:06
• Can we provide only one program which can be called both ways? Apr 26 '16 at 10:07
• @EwanDelanoy I think Fatalize was suggesting to count the program that can do both things only once. Apr 26 '16 at 11:33
• @LevelRiverSt To supplement Katenkyo's comment, the reason Z^n stands for n-tuples is that the omitted operator isn't (pairwise) multiplication but the Cartesian product. Z^2 = ZxZ. Apr 26 '16 at 11:34

# MATL, 43 36 bytes

This uses the spiral (1YL) function, which generates a square 2D array of given size with values arranged in an outward spiral. For example, with input 7 it produces

43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20  7  8  9 10 27
40 19  6  1  2 11 28
39 18  5  4  3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31


The center of the array, which contains 1, corresponds to the tuple [0 0]. The upper left corner corresponds to [-3 -3] etc. So for example f (-3,-3) will be 43 and g (43) will be [-3 -3].

The code generates a 2D array with this spiral matrix, as large as needed to do the conversion. Note that larger sizes always give the same result for the entries already included in smaller sizes.

### From Z2 to N (18 bytes):

|X>tEQ1YLGb+QZ}3$)  Try it online! |X> % input is a 2-tuple. Take maximum of absolute values tEQ % duplicate. Multiply by 2 and increase by 1. This gives necessary size of spiral 1YL % generate spiral G % push input 2-tuple again b+Q % bubble up, add, increase by 1. This makes the center correspont to [0 0] Z} % split tuple into its values 3$)   % use those two value as indices into the spiral array to obtain result


### From N to Z2 (25 18 bytes)

Eqt1YLG=2#fhw2/k-q


Try it online!

Eq      % input is a number. Multiply by 2, add 1. This assures size is enough and odd
t1YL    % duplicate. Generate spiral of that size
G=      % compare each entry with the input value
2#fh    % 2-tuple of row and column indices of matching entry
w2/k-q  % swap. Offset values so that center corresponds to [0 0]


### Snippet for checking

Note that G needs to be modified to accomodate the fact that we have don't have a single input. The code is slow, so the link checks tuples with values from -9 to 9 only. For -99 to 99 just replace the first line.

The code tests each tuple with values in the defined range. It does the conversion to a number, then from that number back to a tuple, and then checks if the original and recovered tuple are equal. The results should all be 1, indicating that all comparisons give true.

It takes a while to run.

Try it online!

-9:9                     % Or use -99:99. But it takes long
HZ^!"@                   % Cartesian power: gives tuples [-9 -9] ... [9 9].
% For each such tuple
|X>tEQ1YL@b+QZ}3$) % Code from Z^2 to N with G replaced by @ (current tuple) XJ % Copy result into clipboard J Eqt1YLJ=2#fhw2/k-q % Code from N to Z^2 with G replaced by J @!X= % Compare original tuple with recovered tuple: are they equal?  ## JavaScript (ES6), 171 bytes (x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y)) x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))])


Bit twiddling: negative numbers have their bits flipped; each integer is then doubled, and 1 added if it was originally negative; the bits from the integers are then interleaved. The reverse operation deletes alternate bits, divides by 2, and flips all the bits if the value was negative. I could save 3 bytes by limiting myself to 15-bit values instead of 16-bit values.

f=(x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y))
g=x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))]) for(i=-100;i<=100;i++)for(j=-100;j<100;j++)if(g(f(i,j))!=i||g(f(i,j))!=j)alert([i,j]) # Jelly, 504846454340 39 bytes ## Plane to line (1817 16 bytes): AḤ_<0$
+RS+
,Ñç/


Try it online!

## Line to plane (3230292724 23 bytes):

HĊN⁸¡
³R‘R’U⁹¡F³ịÇ
ç1,¢


Try it online!

## Explanation:

I'll only explain plane to line, because line to plane is just its opposite.

Firstly, we convert each integer to a natural number, by the function f(x) = 2*|x| - (x<0).

Then, we convert the two natural numbers to another two natural numbers, by the function g(x,y) = (x+y,y).

Finally, we convert them into one natural number, by the function h(x,y) = (x+1)C2 + y

• @LuisMendo Yes, and now the try-it-online links' input is 7 Apr 26 '16 at 14:31
• This looks better :-) I assume you are working on the checking snippet Apr 26 '16 at 14:35
• @LuisMendo Does the checking snippet count towards the score? Apr 26 '16 at 16:29
• No, the challenge says not taking the correctness check into account Apr 26 '16 at 16:36