Unexpected behavior involving √2 and parity

Question

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$:

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$:

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$:

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

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

Answer 1

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

Answer 2

Here is a heuristic answer inspired by this comment of Lucia.

First, let assume that the probabilty for an integer $n$ to be odd is $\frac{1}{2}$, and that the probabilty for $f(n)$ to be odd when $n$ is even (resp. odd) is also $\frac{1}{2}$. We will observe that (surprisingly) it is no more $\frac{1}{2}$ for $f^{\circ r}(n)$ when $r \ge 2$ (in some sense, the probability does not commute with the composition of $f$ with itself).

• if $n$ and $m=f(n)$ are even: note that $\frac{n}{\sqrt{2}} = m+\theta$ (with $0 < \theta < 1$) so that $m=\frac{n}{\sqrt{2}}- \theta$, then $$f^{\circ 2}(n) = f(m) = \left \lfloor{\frac{m}{\sqrt{2}}} \right \rfloor = \left \lfloor{\frac{\frac{n}{\sqrt{2}}- \theta}{\sqrt{2}}} \right \rfloor = \left \lfloor \frac{n}{2} - \frac{\theta}{\sqrt{2}}\right \rfloor$$ but $\frac{n}{2}$ is even with probability $\frac{1}{2}$, so in this case, $f^{\circ 2}(n)$ is odd with probability $\frac{1}{2}$.

• if $n$ is even and $m=f(n)$ is odd: $$f^{\circ 2}(n) = f(m) = \left \lfloor\sqrt{2}m \right \rfloor = \left \lfloor \sqrt{2}(\frac{n}{\sqrt{2}} - \theta) \right \rfloor = \left \lfloor n - \sqrt{2} \theta) \right \rfloor$$ but $n$ is even and the probability for $0<\sqrt{2} \theta<1$ is $\frac{\sqrt{2}}{2}$ (because $\theta$ is assumed statistically equidistributed on the open interval $(0,1)$), so $f^{\circ 2}(n)$ is odd with probability $\frac{\sqrt{2}}{2}$.

• if $n$ is odd and $m=f(n)$ is even:
  $$f^{\circ 2}(n) = f(m) = \left \lfloor{\frac{m}{\sqrt{2}}} \right \rfloor = \left \lfloor{\frac{\sqrt{2}n-\theta}{\sqrt{2}}} \right \rfloor = \left \lfloor n - \frac{\theta}{\sqrt{2}} \right \rfloor $$ but $n$ is odd and $0 < \frac{\theta}{\sqrt{2}}<1$, so $f^{\circ 2}(n)$ is even.

• if $n$ is odd and $m=f(n)$ is odd:
  $$f^{\circ 2}(n) = f(m) = \left \lfloor \sqrt{2} m \right \rfloor = \left \lfloor \sqrt{2} (\sqrt{2}n-\theta) \right \rfloor = \left \lfloor 2n - \sqrt{2} \theta \right \rfloor $$ but $2n$ is even and the probability for $0<\sqrt{2} \theta<1$ is $\frac{\sqrt{2}}{2}$, so $f^{\circ 2}(n)$ is odd with probability $\frac{\sqrt{2}}{2}$.

By combining these four cases together, we deduce that the probability for $f^{\circ 2}(n)$ to be odd is $$\frac{1}{2} \times \frac{1}{2} \times (\frac{1}{2} + \frac{\sqrt{2}}{2} + 0 + \frac{\sqrt{2}}{2}) = \frac{2\sqrt{2}+1}{8}$$

By continuing in the same way, we get that the probability for $f^{\circ 3}(n)$ to be odd is:
$$ \frac{1}{4} (\frac{1}{2}\frac{1}{2} + \frac{1}{2}\frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2}\frac{\sqrt{2}}{2} + 1\frac{1}{2} + \frac{\sqrt{2}}{2}\frac{\sqrt{2}}{2}) = \frac{\sqrt{2}+7}{16}$$

For $2 \le r \le 24$, we computed the probability $p_r$ for $f^{\circ r}(n)$ to be odd (see Appendix). It seems (experimentally) that $p_r$ converges to a number $\simeq 0.532288725 \simeq \frac{8+3\sqrt{2}}{23}$ by Inverse Symbolic Calculator. This leads to the following question/conjecture:
$$\lim_{r \to \infty}p_r = \frac{8+3\sqrt{2}}{23} \ \ ?$$

If so, consider the number $\alpha$ mentioned in the main post, then $$\alpha = 1-\frac{8+3\sqrt{2}}{23} = \frac{15-3\sqrt{2}}{23} \simeq 0.467711,$$ which matches with the computation in the main post. And next, we would have:
$$ \delta = \frac{\sqrt{2}}{2^{\alpha}}= 2^{\frac{1}{2}-\alpha} = 2^{\frac{6\sqrt{2}-7}{46}} \simeq 1.022633$$

---

Appendix

Computation

sage: for i in range(3,26):
....:     print(sq2(i))
....:
[1/4*sqrt(2) + 1/8, 0.478553390593274]
[1/16*sqrt(2) + 7/16, 0.525888347648318]
[3/32*sqrt(2) + 13/32, 0.538832521472478]
[15/64*sqrt(2) + 13/64, 0.534581303681194]
[5/128*sqrt(2) + 61/128, 0.531805217280199]
[39/256*sqrt(2) + 81/256, 0.531852847392776]
[93/512*sqrt(2) + 141/512, 0.532269260352925]
[51/1024*sqrt(2) + 473/1024, 0.532348527032254]
[377/2048*sqrt(2) + 557/2048, 0.532303961432938]
[551/4096*sqrt(2) + 1401/4096, 0.532283123258685]
[653/8192*sqrt(2) + 3437/8192, 0.532285334012406]
[3083/16384*sqrt(2) + 4361/16384, 0.532288843554459]
[3409/32768*sqrt(2) + 12621/32768, 0.532289246647030]
[7407/65536*sqrt(2) + 24409/65536, 0.532288816169701]
[22805/131072*sqrt(2) + 37517/131072, 0.532288667983386]
[24307/262144*sqrt(2) + 105161/262144, 0.532288700334941]
[72761/524288*sqrt(2) + 176173/524288, 0.532288728736551]
[159959/1048576*sqrt(2) + 331929/1048576, 0.532288729880941]
[202621/2097152*sqrt(2) + 829741/2097152, 0.532288725958633]
[639131/4194304*sqrt(2) + 1328713/4194304, 0.532288724978704]
[1114081/8388608*sqrt(2) + 2889613/8388608, 0.532288725350163]
[1825983/16777216*sqrt(2) + 6347993/16777216, 0.532288725570602]
[5183461/33554432*sqrt(2) + 10530125/33554432, 0.532288725561857]

Code

def sq2(n):
    c=0
    for i in range(2^n):
        l=list(Integer(i).digits(base=2,padto=n))
        if l[-1]==1:
            cc=1/4
            for j in range(n-2):
                ll=[l[j],l[j+1],l[j+2]]
                if ll==[0,0,0]:
                    cc*=1/2
                if ll==[0,0,1]:
                    cc*=1/2
                if ll==[0,1,0]:
                    cc*=(1-sqrt(2)/2)
                if ll==[0,1,1]:
                    cc*=sqrt(2)/2
                if ll==[1,0,0]:
                    cc*=1
                if ll==[1,0,1]:
                    cc=0
                    break
                if ll==[1,1,0]:
                    cc*=(1-sqrt(2)/2)
                if ll==[1,1,1]:
                    cc*=sqrt(2)/2
            c+=cc
    return [c.expand(),c.n()]

Answer 3

You can say with Beatty theorem : $A=\{E(n(\sqrt{2}+2)) \text{ ; } n\in\mathbb N^*\}$ and $B=\{E(n \sqrt{2});n\in\mathbb N^*\}$ is a partition of $\mathbb N^*$

And we have $E(n(\sqrt{2}+2))=2n+E(n\sqrt{2})$

with $E$ is the function integer part