Unexpected Behavior – Involving ?2 and Parity

collatz conjecturecomputational-number-theoryds.dynamical-systemsnt.number-theory

This post makes a focus on a very specific part of that long post. Consider the following map:
$$f: n \mapsto \left\{
\begin{array}{ll}
\left \lfloor{n/\sqrt{2}} \right \rfloor & \text{ if } n \text{ even,} \\
\left \lfloor{n\sqrt{2}} \right \rfloor & \text{ if } n \text{ odd.}
\end{array}
\right.$$

Let $f^{\circ (r+1)}:=f \circ f^{\circ r}$, consider the orbit of $n=73$ for iterations of $f$, i.e. the sequence $f^{\circ r}(73)$: $$73, 103, 145, 205, 289, 408, 288, 203, 287, 405, 572, 404, 285, 403, 569, 804, 568, 401, \dots$$

It seems that this sequence diverges to infinity exponentially, and in particular, never reaches a cycle. Let illustrate that with the following picture of $(f^{\circ r}(73))^{1/r}$, with $200<r<20000$:

enter image description here

According to the above picture, it seems that $f^{\circ r}(73) \sim \delta^r$ with $\delta \sim 1.02$.

Now consider the probability of the $m$ first terms of the sequence $f^{\circ r}(73)$ to be even: $$p_{0}(m):= \frac{|\{ r<m \ | \ f^{\circ r}(73) \text{ is even}\}|}{m}.$$
Then $p_1(m):=1-p_0(m)$ is the probability of the $m$ first terms of $f^{\circ r}(73)$ to be odd.

If we compute the values of $p_i(m)$ for $m=10^{\ell}$, $\ell=1,\dots, 5$, we get something unexpected:
$$\scriptsize{ \begin{array}{c|c}
\ell & p_0(10^{\ell}) &p_1(10^{\ell}) \newline \hline
1 &0.2&0.8 \newline \hline
2 &0.45&0.55 \newline \hline
3 &0.467&0.533 \newline \hline
4 &0.4700&0.5300 \newline \hline
5 &0.46410&0.53590 \newline \hline
6 & 0.465476& 0.534524
\end{array} }$$ (the line for $\ell = 6$ was computed by Gottfried Helms, see the comments)

It is unexpected because it seems that $p_0(m)$ does not converge to $1/2$, but to $\alpha \sim 0.465$.
It matches with the above observation because $$ \delta \sim 1.02 \sim \sqrt{2}^{(0.535-0.465)} = \sqrt{2}^{(1-2 \times 0.465)} \sim \sqrt{2}^{(1-2\alpha)}.$$

Question: Is it true that $f^{\circ r}(73)$ never reach a cycle, that $(f^{\circ r}(73))^{1/r}$ converges to $\delta \sim 1.02$, that $p_0(m)$ converges to $\alpha \sim 0.465$, and that $\delta^24^{\alpha} = 2$? What are the exact values of $\delta$ and $\alpha$? (or better approximations?)

The following picture provides the values of $p_0(m)$ for $100 < m < 20000$:
enter image description here

Note that this phenomenon is not specific to $n=73$, but seems to happen as frequently as $n$ is big, and then, the analogous probability seems to converge to the same $\alpha$. If $n <100$, then it happens for $n=73$ only, but for $n<200$, it happens for $n=73, 103, 104, 105, 107, 141, 145, 146, 147, $ $ 148, 149, 151, 152, 153, 155, 161, 175, 199$; and for $10000 \le n < 11000$, to exactly $954$ ones.

Below is the picture as above but for $n=123456789$:
enter image description here

Alternative question: Is it true that the set of $n$ for which the above phenomenon happens has natural density one? Is it cofinite? When it happens, does it involves the same constant $\alpha$?

There are exactly $1535$ numbers $n<10000$ for which the above phenomenon does not happen. The next picture displays for such $n$ the minimal $m$ (in blue) such that $f^{\circ m}(n) = f^{\circ (m+r)}(n)$ for some $r>0$, together with the miniman such $r$ (in red):

enter image description here

In fact all these numbers (as first terms) reach the following cycle of length $33$:

$$(15,21,29,41,57,80,56,39,55,77,108,76,53,74,52,36,25,35,49,69,97,137,193,272,192,135,190,134,94,66,46,32,22)$$

except the following ones: $$7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 26, 27, 28, 38, 40, 54,$$ which reach $(5,7,9,12,8)$, and that ones $1, 2, 3, 4, 6$ which reach $(1)$, and $f(0)=0$.

If the pattern continues like above up to infinity, they must have infinity many such $n$.

Bonus question: Are there infinitely many $n$ reaching a cycle? Do they all reach the above cycle of length $33$ (except the
few ones mentioned above)? What is the formula of these numbers $n$?

Below is their counting function (it looks logarithmic):
enter image description here

Best Answer

A list of predecessors as mentioned in my comment.

I document pairs of $(m,n)$ for consecutive $m$ and their 1-step predecessors $n$ such that $f(n)=m$. The value $n=0$ indicates, that $m$ has no predecessor. I didn't reflect, that one $m$ can have two predecessors, but if $n/2$ is odd, then $n/2$ is a second predecessor.(This makes the table more interesting, because all odd predecessors $n$ are overwritten by the even predecessors $2n$...

Moreover, a nearly periodic structure occurs. I tried to resemble this by the arrangement of three or four columns of $(m,n)$ such that the first column contains all $m$ which have no predecessor. The basic pattern is not really periodic, but has super-patterns which again seem to be periodic but actually aren't. This pattern-superpattern-structure is also recursive. It reminds me of a similar structure when I looked at $\beta=\log_2(3)$ and found a similar style of pattern-superpattern-supersuperpattern-... and is there related to the continued fraction of $\beta$.
So I think we'll get no nice description for the cases $m$ which have no predecessor... 

 m     n         m     n         m     n         m    n
------------------------------------------------------------- 
                 1     2         2     4    
 3     0         4     6         5     8    
 6     0         7    10         8    12         9    14    

10     0        11    16        12    18    
13     0        14    20        15    22        16    24    

17     0        18    26        19    28    
20     0        21    30        22    32    
23     0        24    34        25    36        26    38    

27     0        28    40        29    42    
30     0        31    44        32    46        33    48    

34     0        35    50        36    52    
37     0        38    54        39    56    
40     0        41    58        42    60        43    62    

44     0        45    64        46    66    
47     0        48    68        49    70        50    72    

51     0        52    74        53    76    
54     0        55    78        56    80        57    82    

58     0        59    84        60    86    
61     0        62    88        63    90    
64     0        65    92        66    94        67    96

Update Some more explanation on the idea of "recursive aperiodic pattern". If we list the values $m$ which have no predecessor, we get 

m_k:   3, 6,10,13, 17,20,23,27,30,...

Writing the differences (I have prepended a zero-value to the above list of $m_k$) 

    ,3,3,4  ,3,4  ,3,3,4  ,3,4  ,3,3,4  ,3,4  ,3,4  ,3,3,4 , ...

We note, that we have a pattern of two different words: 3,3,4 and 3,4 repeating, but aperiodical. Let's denote the longer one with the capital A and the shorter one with the small a (and A means a difference of 10 and a of 7).
We get 

 Aa Aa Aaa 
 Aa Aaa 
 Aa Aa Aaa 
 Aa Aaa
 Aa Aa Aaa
 Aa Aaa
 Aa ...

Again we find only two kind of "words". Let's them shorten by Aaa=B and Aa=b. B means now a difference of 24, b of 17. Then we get 

   bbB bB
   bbB bB
   bbB bB bB
   bbB bB
   bbB bB bB
   bbB bB
   bbB bB
   bbB bB bB
   ...

Next obvious step gives 

   Cc Cc Ccc
   Cc Ccc
   Cc Cc Ccc
   Cc Ccc
   Cc Cc Ccc
   Cc Ccc
   ...

with c representing a difference of 17+24=41 and C of 17+17+24=58.
And so on.
If I recall correctly, then with the mentioned case of working with $\beta = \log_2(3)$ the same style of recursive pattern reflected the convergents of the continued fractions of $\beta$.
The first few differences here match the convergents of the continued fraction of $\sqrt2$ so far: 

            a    b    c                    short patterns
 -------------------------------------
[1  1  3    7    17   41  99   239   577  ...  ]  convergents of contfrac(sqrt(2))
[0  1  2    5    12   29  70   169   408  ...  ] 
 -------------------------------------...
          A/2   B/2   C/2                  long patterns

Update 2 The above can be explained by the following:

  • a number of the form $\lfloor2k\sqrt2\rfloor$ has exactly one predecessor $4k$;
  • a number of the form $\lfloor(2k-1)\sqrt2\rfloor$ has exactly two predecessors $2k-1$ and $4k-2$;
  • a number has no predecessors iff it has form $\lfloor n(2+\sqrt2)\rfloor$.

The first two statements are easily checked, while the third follows from the Beatty theorem, as explained in another answer by @Dattier

Update 3 Using a back-step algorithm (recursive) it seems I've got the predecessing tree of $m=73$. If no bugs, then this tree would also be complete. (But my routine may still be buggy, please check the results!)

The back-steps go from top-right south-west (antidiagonal) downwards. When there are two possible predecessors, they occur in the same column, but on separate rows.
If there is a predecessor without further predecessor, a short line (---) is printed.

                                    73   <--- start
                                104   
                            148   
                        105 ---

                        210   
                    149   
                212   
            300 ---

                    298   
                211 ---

                422   
            299   
        424   
    600 ---

            598   
        423 ---

        846 ---
    ---------------------------- tree seems to be complete (please check for errors!)
Related Question