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

365 Views Asked by At

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

2

There are 2 best solutions below

0
On

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.

5
On

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