2
$\begingroup$

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)?

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

1 Answer 1

3
$\begingroup$

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})$.

$\endgroup$
1
  • 1
    $\begingroup$ Do you have a reference? $\endgroup$ Aug 14, 2023 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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