7
$\begingroup$

The two sequences A48680 and A48679 of the OEIS define two mutually inverse bijections on the set of all strictly positive natural numbers given (for the comfort of the reader) as follows:

Given an integer $n>0$ with binary expansion $n=\sum_{i=0}^N d_i2^i$, make the substitution $1\longrightarrow 10,\quad 0\longrightarrow 0$ in $d_Nd_{N-1}\ldots d_0$, remove the final digit $0$ and interpret the resulting word (whose digits $1$ are isolated) $e_Me_{M-1}\ldots e_1$ as the Zeckendorff expansion of $\varphi(n)=\sum_{i=1}^M e_if_i$ (where $f_0=f_1=1,f_n=f_{n-1}+f_{n-2}$ is the Fibonacci sequence).

Example: For $n=13=8+4+1$ we get $$1101\longrightarrow 101001(0)\longrightarrow f_6+f_4+f_1=13+5+1=19$$ showing $\varphi(13)=19$.

It is easy to see that $\varphi$ defines a bijection which has a few small finite orbits: $$(1),(2),(3,4),(5,6,7,12,11,17,14,20,16,8),(9),(10)\ .$$ (I suspect that this is the complete list of finite orbits).

The orbit of a "generic" integer should be infinite: Indeed most binary integers with a large number $N$ of digits have roughly N/2 digits equal to 1 suggesting that the number of digits of under iteration should have roughly geometric growth of ratio $\frac{3\log(\omega)}{2\log(2)}$ for $\omega=\frac{1+\sqrt{5}}{2}$ the golden number (where we make of course the perhaps naive assumption that digits $0$ and $1$ are occuring with roughly identical frequencies during iterations).

This heuristic argument does however break down when considering backward iterations.

A few computations of $n\longmapsto \log\log(\varphi^n(a))$ for various initial values $a$ (with infinite orbits) and $n$ in the range $-200,\ldots,200$ depict however graphs which seem to be (up to affine transformations) asymptotically close to the graph $x\longmapsto \vert x\vert$ (with observed asymptotic slopes seemingly fairly close to the expected values $\pm \log\left(\frac{3\log(\omega)}{2\log(2)}\right)$) suggesting that the same (or roughly the same) asymptotical geometric growth-rate occurs also for digits of iterated values when considering the reciprocal function.

Is this an artefact due to numerical limitations? If not, are there some easy (perhaps heuristic and not completely rigourous) explanations for these behaviours.

Final Remark: The definition of $\varphi$ mixes two different numeral systems. It is thus somewhat reminiscent of the famous Syracuse problem.

$\endgroup$
5
  • $\begingroup$ There aren't non strictly positive natural numbers $\endgroup$ Commented Jul 10, 2021 at 22:08
  • 3
    $\begingroup$ There is a sect of people considering $0$ as a positive natural number. $\endgroup$ Commented Jul 10, 2021 at 22:13
  • 1
    $\begingroup$ It is not that we consider $0$ to be positive, but that the word "positive" is ambiguous, and could either mean "$>0$" or "$\ge0$", so I approve of Roland's use of "strictly positive" which is totally non-ambiguous (and I concede, is the way these words are used in French). $\endgroup$ Commented Jul 11, 2021 at 5:09
  • $\begingroup$ Concerning dynamics, up to conjugation by permutations, permutations of $\mathbf{N}$ are classified by their number of cycles (including infinite countable multiplicities and infinite cycles). However, such a dynamical fact as "growing linearly" is not invariant by conjugation by arbitrary permutations, and then one should maybe work in a smaller group. $\endgroup$
    – YCor
    Commented Jul 11, 2021 at 7:18
  • $\begingroup$ Sorry, I think the title is perhaps badly chosen: The interesting thing are metric properties (growth in $\mathbb Z$ as a metric space) of infinite orbites. $\endgroup$ Commented Jul 11, 2021 at 8:08

0

You must log in to answer this question.