1
$\begingroup$

I have an idea but I don't know how to formalize my idea in a function. That's what n should give me back as (x,y):

n = 0 -> (0,0)
n = 1 -> (1,0)
n = 2 -> (0,1)
n = 3 -> (2,0)
n = 4 -> (1,1)
n = 5 -> (0,2)
n = 6 -> (3,0)
n = 7 -> (2,1)
n = 8 -> (1,2)
n = 9 -> (0,3)
n = 10 -> (4,0)

How do I formulate a function for this one? I also need one for N -> N x {1,...,n) but I think it's the same function, is it?

$\endgroup$

marked as duplicate by Ross Millikan, Xander Henderson, trancelocation, user99914, Strants May 15 '18 at 13:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5
$\begingroup$

Each $n \in \mathbb N$ can be uniquely written as $n=m(m+1)/2 + j$ with $0 \le j \le m$, namely $m = \left\lfloor \dfrac{\sqrt{8n+1}-1}{2} \right\rfloor$. Then take $f(n) = (m-j,j)$.

It's simpler, though, to write the inverse function from $\mathbb N \times \mathbb N$ to $\mathbb N$:

$$ (i,j) \mapsto \frac{(i+j)(i+j+1)}{2}+j $$

$\endgroup$
  • $\begingroup$ That looks very irritating for me. If I try it with n = 1, then I get m = 1 and j = 0, means f(n) = (1,0) which is true. But if I try it with n = 2, I need to take the root of 17. But that wouldn't result in a natural number for m. Where is my error? $\endgroup$ – CoreNoob May 15 '18 at 0:33
  • $\begingroup$ @corenoob Note the floor operation $\endgroup$ – Bram28 May 15 '18 at 0:35
  • $\begingroup$ @Bram28. Thanks. I'm such an idiot. How do you guys come up with such functions? I'm a c.s. student in the 2nd semester but I wouldn't be able to come up with the function above. $\endgroup$ – CoreNoob May 15 '18 at 0:39
  • $\begingroup$ @CoreNoob The bijection you indicated is pretty standard, even as the actual function is a pain to figure out. My guess is Robert had this function laying around in his notes somewhere ... though it's possible he figured it out on the spot! $\endgroup$ – Bram28 May 15 '18 at 0:43
1
$\begingroup$

There is an easier bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$. If $n$ $\in$ $\mathbb{N}$, there is a unique pair $(x_n,y_n)$ $\in$ $\mathbb{N}\times\mathbb{N} $ such that $n = 2^{x_n-1}\cdot (2y_n - 1)$ (using fundamental theorem of arithmetic), defining the map

\begin{align*}F:&\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}\\ &n\rightarrow (x_n,y_n) \end{align*} you get a bijection.

$\endgroup$
  • $\begingroup$ Thanks for this one. But that is N x N -> N and not N -> N x N, right? f(n) would be N -> N x N. $\endgroup$ – CoreNoob May 15 '18 at 0:51
  • $\begingroup$ So you can use the inverse of $F$, $F^{-1} (n,m) = 2^{n-1} \cdot (2m - 1)$ $\endgroup$ – Matheus Manzatto May 15 '18 at 0:54
  • $\begingroup$ If you are concerned about the domain of $F$, is correct, this map associates every natural $n$ $\in$ $\mathbb{N}$ to a pair $(x_n,y_n)$ $\in$ $\mathbb{N}\times \mathbb{N}$ $\endgroup$ – Matheus Manzatto May 15 '18 at 0:57
  • $\begingroup$ What is the inverse function of f(n,m) = 2^(n-1) * (2m-1) ? $\endgroup$ – CoreNoob May 15 '18 at 1:07
  • $\begingroup$ The inverse of $f $ is the function $F $ that I explain in my answer. Just observe that $F (f (n,m)) =(n,m) $ $\endgroup$ – Matheus Manzatto May 15 '18 at 1:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.