21
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Perhaps I made a mistake, but I get a different value of $p_0(10^4)$ (0.4912 instead of 0.4700). For larger $m$ the value seems even closer to 1/2. As a control the computation for $m=10^4$ has a maximum of $f^{\circ k}(73)$ equal to $1341801280048839911857201274496$ (for $k=2584$), so roundoff errors when computing $n\cdot \sqrt{2}^{\pm 1}$ could have occured in your computation. Could some confirm the above? $\endgroup$ – Kasper Andersen Feb 25 at 21:10
  • 3
    $\begingroup$ @Kasper Andersen The problem seems to be the floating point arithmetic you use. I calculated (with python and the module mpmath) $p_0(10^4)$ and $p_0(10^5)$ with a precision of 100,1000,10000 decimal places and got for 10000 decimal places the same values as in the table. But for fewer decimal places the values were different, f.i. with double precision the values seemed to converge to $0.5$. $\endgroup$ – Dieter Kadelka Feb 25 at 23:33
  • 6
    $\begingroup$ @მამუკა ჯიბლაძე : Sorry for the confusion. I though I was using Magma for the computation with quite large precision, unfortunately the way to compute $\sqrt{2}$ is not RealField(d)!Sqrt(2) but Sqrt(RealField(d)!2) (d is the precision). So now my results are in happy agreement with the table and also with your result for $f^{\circ 2584}(73)$. $\endgroup$ – Kasper Andersen Feb 26 at 10:54
  • 2
    $\begingroup$ @მამუკაჯიბლაძე: Four distinct equivalence classes reaching cycles, and at least one which does no. The question is : are all the numbers non-reaching a cycle, in the same class? Very interesting! $\endgroup$ – Sebastien Palcoux Feb 26 at 17:08
  • 2
    $\begingroup$ @მამუკაჯიბლაძე: I tried $73$ and $123456789$, but up to the 10000th iteration they share no point. If we assume that for a subset of numbers $n$ of natural density one, the sequence $f^{\circ r}(n)$ has exponential grows (expected $\sim 1.02^r$), then I think that an argument of density can prove that there must have infinitely many equivalence classes. $\endgroup$ – Sebastien Palcoux Feb 27 at 2:56
6
$\begingroup$

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!)
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting! A number $m$ admits no predecessor iff the interval $[m\sqrt{2},(m+1)\sqrt{2}]$ admits no even number and the interval $[m/\sqrt{2},(m+1)/\sqrt{2}]$ admits no odd number. There are exactly $r_{\ell}$ such numbers $m<10^{\ell}$ with $\ell=1,2,3,4,5,6$ and $r_{\ell}=2,29,292,2928,29289,292893$. Strangely, for $\ell \le 6$ we observe that $r_{\ell-1} = ⌊ r_{\ell}/10⌋$, it should be true in general, I don't know why but it should be due to some pattern. $\endgroup$ – Sebastien Palcoux Feb 28 at 16:51
  • 2
    $\begingroup$ Numbers without predecessors are described in the answer by @Dattier as those of the form $\lfloor n(2+\sqrt2)\rfloor$ $\endgroup$ – მამუკა ჯიბლაძე Feb 29 at 7:28
  • 1
    $\begingroup$ Moreover it seems that numbers with one predecessor are those of the form $\lfloor2k\sqrt2\rfloor$ and numbers with two predecessors those of the form $\lfloor(2k-1)\sqrt2\rfloor$ $\endgroup$ – მამუკა ჯიბლაძე Feb 29 at 7:56
  • 1
    $\begingroup$ In fact, predecessor of $\lfloor2k\sqrt2\rfloor$ is $4k$ while predecessors of $\lfloor(2k-1)\sqrt2\rfloor$ are $2k-1$ and $4k-2$. $\endgroup$ – მამუკა ჯიბლაძე Feb 29 at 8:02
  • 1
    $\begingroup$ I believe it is better to extend your answer, not to have too many partial answers. Note that relevant keywords here are Sturmian sequences and Beatty sequences (the latter mentioned in another answer) $\endgroup$ – მამუკა ჯიბლაძე Feb 29 at 8:12
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ What is $E(x)$? How does this answer the question? $\endgroup$ – Wojowu Feb 25 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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