6
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ – Apple May 27 '16 at 14:59
  • 1
    $\begingroup$ 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... $\endgroup$ – Michael Stachowsky May 27 '16 at 15:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Gottfried Helms May 28 '16 at 10:59
  • 1
    $\begingroup$ 53 and 85 both arrive at 441 (the others do not), so they are in some sense the same case. $\endgroup$ – Aeryk Jun 4 '16 at 0:38
  • 1
    $\begingroup$ 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$? $\endgroup$ – Aeryk Jun 4 '16 at 2:00
2
$\begingroup$

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
$\endgroup$
5
  • $\begingroup$ Very interesting data! Especially remarkable is that $n=725$ takes $90$ iterations to converge. $\endgroup$ – Joseph O'Rourke May 28 '16 at 12:43
  • $\begingroup$ @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. $\endgroup$ – Gottfried Helms May 28 '16 at 12:50
  • 2
    $\begingroup$ @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 $\endgroup$ – Aeryk Jun 4 '16 at 2:14
  • $\begingroup$ @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. $\endgroup$ – Gottfried Helms Jun 6 '16 at 23:32
  • $\begingroup$ 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)}} $ $\endgroup$ – Gottfried Helms Jun 6 '16 at 23:34
1
$\begingroup$

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.

$\endgroup$

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.