# A bijection between odd natural integers and compositions

Given an odd natural integer $$2a-1$$ with $$a\geq 1$$, associate to it recursively the composition $$\psi(1)=\emptyset$$ and $$\psi(2^{-n}a)+(n+\delta_{>1}(m))$$ if $$a=2^n m$$ with $$m$$ odd where $$\delta_{>1}(1)=0$$ and $$\delta_{>1}(m)=1$$ otherwise. For $$2a-1=37$$ we get for example \begin{align*} \psi(2\cdot 19-1)&=\psi(2\cdot 2\cdot 5-1)+(0+\delta_{>1}(19))\\ &=\psi(2\cdot 3-1)+(1+\delta_{>1}(5))+1\\ &=\psi(2\cdot 2\cdot 1-1)+2+1\\ &=\psi(2\cdot 1-1)+(1+\delta_{>1}(1))+2+1\\ &=1+1+2+1\\ \end{align*}

First values for $$\psi$$ are given by $$\begin{array}{r|ccccccccc} n&1&3&5&7&9&11&13&15&17\\ \hline \psi(n)&\emptyset&1&1+1&2&1+1+1&1+2&2+1&3&1+1+1+1\\ \end{array}$$

$$\psi$$ is one-to-one: the composition $$n_1+n_2+\cdots+n_l$$ is the image of $$(\cdots(((2^{1+n_1}-1)2^{n_2}-1)2^{n_3}-1)\cdots)2^{n_l}-1$$.

The partition $$1+1+2+1$$ corresponds to $$(((2^{1+1}-1)2^1-1)2^2-1)2^1-1=37.$$

For $$n>0$$, it sends the $$2^{n-1}$$ odd integers $$2^n+1,2^n+3,\dots,2^{n+1}-1$$ to the $$2^{n-1}$$ compositions of sum $$n$$ in an order-preserving way for the lexicographic order on compositions.

Restricting $$\psi$$ to integers $$\geq 5$$ which are congruent to $$1$$ modulo $$4$$ (or to $$3$$ modulo $$4$$) and considering summands of compositions as coefficients of continued fraction expansions, we get of course a bijection onto all rationals in $$(0,1)$$.

Is there a good reference for the bijection $$\psi$$ (or some close relative)?

• The definition of $\psi$ is not clear. Aug 13, 2023 at 20:14
• Is $\delta_{>0}$ supposed to be $\delta_{>1}$? Aug 13, 2023 at 23:29
• Thanks: corrected and clarified (using an example). Aug 14, 2023 at 10:19

More or less a comment. I'd say the closest known bijection is just given by the binary representation, namely, if I understand it correctly, for e.g. $$37$$ we do $$3$$ times the last power of $$2$$ less than $$37$$, here $$3\cdot32=96$$, and the binary representation of the difference to $$37$$, here $$96-37=59=2^5+2^4+2^3+2^1+2^0$$, and finally the increments in the (decreasing) sequence of exponents, here $$(5-4={\bf1},4-3={\bf 1},3-1={\bf 2},1-0={\bf 1})$$.

• Do you have a reference? Aug 14, 2023 at 14:57