# Behavior of a Collatz-like mod-4 sequence: Do some numbers increase without limit?

Define \begin{eqnarray} f(n) &=& (n-1)^2 \; \textrm{if} \; (n \bmod 4) = 1\\ f(n) &=& \lfloor n/4 \rfloor \; \textrm{otherwise} \end{eqnarray} and let $f^k(n) = f(f( \cdots (n) \cdots ) )$ be the result of applying $f(\;)$ $k$ times to $n$. So $f^3(5)=0$ because the iterates produce the sequence $(5,16,4,1,0)$, $f^8(13)=0$ because the sequence is $(13,144,36,9,64,16,4,1,0)$, and so on. Many numbers map to $0$. But some seem not to, i.e., to grow without bound. E.g., here is the start of the sequence for $n=53$, the smallest "problematic" number: $$(53,2704,676,169,28224,7056,1764,441,193600,48400,12100,3025,9144576,2286144,571536,142884,35721,1275918400,318979600,79744900,19936225,\ldots)$$ My question is:

What is special about the numbers $53, 85, 77, 101, \ldots$ that seem to grow without bound? Can one prove that, for any particular number $n$, $\lim_{k \to \infty}f^k(n) = \infty$ ?

• Just as an observation, as soon as the $(n-1)^2$ option happens, the output is always $0$ or $1$ mod $4$. So if $g$ is defined only on integers equivalent to $1$ mod $4$, with $g(4k+1)=d^2$ where $d$ is the largest odd divisor of $k$, then it suffices to search for which $n$ it holds that $\lim_{k\to\infty}g^k(4n+1)=\infty$. This sheds some light on why the $5$ mod $8$ numbers you listed (which are $4n+1$ for odd $n$) have the capacity to explode. – Apple May 27 '16 at 14:59
• I believe you'll need to show the following, if possible (and if true): as stated, once the $(n-1)^2$ option happens, you always get 0 or 1 mod 4. Then, take a look at the division option. In order for it to explode, you'll need to show that once you return to 1 mod 4 you are at a larger integer than you started with. Not sure if that helps... – Michael Stachowsky May 27 '16 at 15:04
• For some small numbers we have possibly $n=77 + 32k, n=85+32k$ diverging, and also $n=101+64k,105+64k$ diverging. Possibly this allows to find meaningful sublists in the list of possibly diverging starting values. – Gottfried Helms May 28 '16 at 10:59
• 53 and 85 both arrive at 441 (the others do not), so they are in some sense the same case. – Aeryk Jun 4 '16 at 0:38
• One other (obvious?) observation: If the base-4 representation of $n$ contains no 1's, then it directly falls to 0. Otherwise it falls until there is a 1 in the rightmost digit. At that point the question becomes: Does a 1 appear in the base-4 form of $(n-1)^2$? – Aeryk Jun 4 '16 at 2:00

This is not an answer but too long for a comment.
I've looked for more simple structure in the list of the potential diverging startingpoints n. I've got this remarkable list for n increased in steps of 16. The expression $n_{40}$ means the 40th iterate started from $n_0$, and documented is the value $f(x)=\log_4(1+x)$ . It seems that all $n_0$ have a diverging trajectory, with the main systematic exception:

• if $n_0 = 5+k \cdot 16$ the iterations seem to diverge
• if $n_0 = 5+2^j \cdot 16$ the tested iterations converged at $n_{40},n_{60}$ or so

However, at index 45, $n_0=5+45\cdot 16 = 725$ there is a suspicious small value, and indeed, further iterations show, that this case has also a converging trajectory. Perhaps here starts another systematic exception - I've not tested it further so far.

Here is the q&d - table of occurences. Note, there are some more $n_0$ with seemingly divergent trajectories, possibly one can state similar lists for them.

 index   n_0      f(n_40)
0     5        0.E-202
1    21        0.E-202
2    37        0.E-202
3    53  7319.43109000
4    69        0.E-202
5    85  7317.43109000
6   101  1778.43168503
7   117  21713.5570367
8   133        0.E-202
9   149  33105.8454885
10   165  21714.5570367
11   181  64089.1819950
12   197  8794.71300153
13   213  31233.9918267
14   229  14399.1441614
15   245  19588.9982699
16   261        0.E-202
17   277  11692.8913443
18   293  21324.9071387
19   309  52525.0264043
20   325  75280.3205060
21   341  412816.543598
22   357  8457.22505438
23   373  48695.2063595
24   389  7944.86049345
25   405  114951.949346
26   421  43423.1140735
27   437  245610.738045
28   453  7863.21231992
29   469  108387.380307
30   485  27329.9204850
31   501  104478.303516
32   517        0.E-202
33   533  127664.156130
34   549  13441.3809126
35   565  14188.4534802
36   581  19847.5273459
37   597  31155.1619582
38   613  13649.1336926
39   629  261684.344974
40   645  9768.31253578
41   661  122116.777066
42   677  113931.186043
43   693  68043.5535663
44   709  24346.4329603
45   725            0.0 ** 90 iterations are needed
46   741  15570.4518083
47   757  29258.7243600
48   773  9214.60724988
49   789  73974.3922236
50   805  129620.074893
51   821  150552.641012
52   837  28679.5491401
53   853  67066.2217326
54   869  2730.81273259
55   885  33191.3766959
56   901  10048.1870338
57   917  629982.314847
58   933  26841.3037906
59   949  9626.11985719
60   965  12369.1434013
61   981  288602.715968
62   997  33603.2403205
63  1013  64087.1819950
64  1029        0.E-202
65  1045  154052.076543
66  1061  587584.400245
67  1077  161520.351894
68  1093  60651.5733297
69  1109  311809.590214
70  1125  142115.581822
71  1141  18330.0985841
72  1157  12911.4593518
73  1173  82858.7585839
74  1189  17327.8175741
75  1205  20186.8735728
76  1221  32147.7713491
77  1237  36688.7632139
78  1253  18574.8869986
79  1269  9183.46362766
80  1285  52446.0968995
81  1301  174327.664458
82  1317  79516.9774718
83  1333  42645.8142774
84  1349  68222.8682003
85  1365  332166.113291
86  1381  139971.870409
87  1397  168699.829041
88  1413  31801.1434636
89  1429  178776.254181
90  1445  72907.9979830
91  1461  88912.4667464
92  1477  7397.26201777
93  1493  39601.4741882
94  1509  658789.653898
95  1525  76077.5540848
96  1541  22169.7016133
97  1557  344441.943668
98  1573  148744.102969
99  1589  84606.9183080
100  1605  7752.98564084
101  1621  39059.2501431
102  1637  77974.8093225
103  1653  87240.8574615
104  1669  66247.6873805
105  1685  43938.1719113
106  1701  38571.9327632
107  1717  45235.6466826
108  1733  594993.327534
109  1749  19080.0053926
110  1765  339488.585999
111  1781  42421.4133738
112  1797  51544.3446576
113  1813  380052.965036
114  1829  38816.8961967
115  1845  382527.130545
116  1861  19586.9982699
117  1877  44300.2273006
118  1893  74159.1965251
119  1909  359757.992003
120  1925  13293.9091873
121  1941  383583.566650
122  1957  150775.076478
123  1973  94657.1031825
124  1989  70276.1119030
125  2005  20190.6474120
126  2021  340196.241896
127  2037  4508.31551895
128  2053        0.E-202   * 50 iterations are needed

• Very interesting data! Especially remarkable is that $n=725$ takes $90$ iterations to converge. – Joseph O'Rourke May 28 '16 at 12:43
• @JosephO'Rourke: yes; and it seems remarkable that its index 45 near the geometric mean of the indexes 32 and 64. Just recently I had a special case (in another field) with base m=181 where its special nature seems to be rooted in the fact that it is near the geometric mean of 128 and 256, so in the near of 2^(15/2) . I did a short look in analoguous cases here (according to the indexes, but also with different starting values of the $n_0$) but no specific observation so far. – Gottfried Helms May 28 '16 at 12:50
• @JosephO'Rourke 725 eventually goes to 16769025 which has a very special base-4 representation: 333332000001. Numbers of this form, i.e. a string of 3's, a single 2, a string of 0's and then a 1, follow a very nice base-4 progression: 333332000001 -> ... -> 33333000001 -> ... -> 3333200001 -> ... -> 333300001 -> ... -> 31 -> 2100 -> 210 -> 21 -> 1000 -> 100 -> 10 -> 1 -> 0 – Aeryk Jun 4 '16 at 2:14
• @Aeryk: That strings with k number of 3's and zeros can be written as $g(k)=(((4^k-1) \cdot 4+2) \cdot 4^k) \cdot 4+1$ which simplifies to $g(k)=(4^k-1)^2$ and indeed is an initial value of $n_0 = g(k)$ steppping down to $n_2=g(k-1)$, $n_4=g(k-2)$ , ... , down to zero. So the numbers $g(k)$ might be seen as somehow "backbone" of numbers, which with their further systematic preimages constitute an infinite subset of numbers whose iterates converge down to zero. – Gottfried Helms Jun 6 '16 at 23:32
• With this, the number $m=725$ can be represented as a preimage of a preimage of $n_0=g(6)$ in the form of $m = 725 = 1+ \sqrt{4^2 \cdot (1+\sqrt{4^3 \cdot g(6)}}$ – Gottfried Helms Jun 6 '16 at 23:34

If f(n) become $a_1→a_k→a_n→$

$a_k=b^2$

$a_{k+1}=(b+1)^2(b-1)^2$

$a_{k+2}=\frac{(b+1)^2(b-1)^2}{16}\geq (\frac{b-1}2)^4\geq [\frac{a_k}2]^2$

So, $a_{n}$ tend to diverge except the numbers with exponent 4.