17
$\begingroup$

This function has been explored a bit at MSE (in June 2016): \begin{eqnarray} f(n) &=& (n-1)^2 \; \textrm{if} \; (n \bmod 4) = 1\\ f(n) &=& \lfloor n/4 \rfloor \; \textrm{otherwise} \end{eqnarray} with $f^k(n) = f(f( \cdots (n) \cdots ) )$ the result of applying $f(\;)$ $k$ times to $n$. The analysis by Gottfried Helms reveals interesting patterns and anomalies, including that it requires $90$ iterations to achieve convergence (to zero) for $n=725$. It would be useful to answer this specific question, on the smallest $n$ that might possibly diverge:

Is $f^k(53)=0$ for any finite $k$?

The first $25$ iterations are: $$ 53,2704,676,169,28224,7056,1764,441,193600,48400,12100,3025,\\ 9144576,2286144, 571536,142884,35721,1275918400,318979600,\\ 79744900,19936225,397453027378176,99363256844544,\\ 24840814211136,6210203552784,1552550888196,\ldots $$

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The integers $n \leq 1000000$ whose sequences reach $0$ and exceed $10^{16}$, but not $10^{100}$ are 65533, 65541, 131065, 131069, 131077, 131081, 262129, 262132, 262134, 262135, 262137, 262141, 262149, 262153, 262161, 262164, 262166, 262167, 524257, 524260, 524262, 524263, 524273, 524276, 524278, 524279, 524281, 524285, 524293, 524297, 524305, 524308, 524310, 524311, 524321, 524324, 524326, 524327. All of these numbers are very close to powers of $2$. The maximum iterate occuring in one of the corresponding sequences is 295156912447327043584. $\endgroup$
    – Stefan Kohl ♦
    Commented Jan 19, 2017 at 21:18
  • 1
    $\begingroup$ What fraction of these numbers less than a million are known to converge? Gerhard "Needs Lowest Of Lowest Terms" Paseman, 2017.01.19. $\endgroup$
    – Gerhard Paseman
    Commented Jan 19, 2017 at 22:17
  • 1
    $\begingroup$ @GerhardPaseman: 187596 of them. $\endgroup$
    – Stefan Kohl ♦
    Commented Jan 19, 2017 at 22:29
  • $\begingroup$ @StefanKohl: Perhaps you're interested in the patterns of the trajectories of your numbers in my new answer. $\endgroup$
    – Gottfried Helms
    Commented Mar 16, 2017 at 3:19

2 Answers 2

Reset to default
6
$\begingroup$

This is not an answer, just elaboration of what really happens.

$\def\OP{\mathop{\rm OP}}$Denote by $\OP(n)$ the odd part of $n$, i.e. the maximal its odd divisor.

1. Once your process comes to an odd square $(2t+1)^2$ (which happens soon), the next few steps lead to an odd square $(\OP(t(t+1)))^2$. If neither $t$ nor $t+1$ is a power of $2$ (in particular, $t>1$), then this new square is at least $(3t)^2>(2t+1)^2$. So, if we never obtain a number of the form $(2^k\pm1)^2$, then these squares increase, and the process diverges. (One may notice that the number $(2^k\pm 1)^2$ is transformed into $(2^{k-1}\pm 1)^2$, so in this case we finally arrive at $0$.)

So, our process starting from an odd square may be reformulated as iterating the function $g(1+2t)=\OP(t(t+1))$. Let us try to see when these iterations starting from an odd number not of the form $2^t\pm 1$ may come to a number of the form $2^t\pm 1$. (The process under consideration starts from $13$.)

2. Assume now that $g(M)=2^a\pm 1$. We have $g(M)=\OP(M^2-1)$, so $M^2-1=2^b(2^a\pm1)$, where $b\leq a+2$ if $M$ is large enough, say $M>7$. If $a+b$ is even, then $M^2$ is too close to another square $2^{a+b}$, which is impossible (unless $M$ itself has our form); so $a+b=2k+1$, $b\leq k+1$, $M^2=2^{2k+1}\pm 2^b+1$.

Thus the only values of $M$ which lead to $2^m\pm1$ are square roots of the numbers of the form $2^{2k+1}\pm 2^b+1$, where $b\leq k+1$. Surely, $M$ is the closest odd integer to $2^k\sqrt 2$.

And this is where I am stuck. There are few small cases, namely $(k,M)=(3,11), (4,23), (7,181);$ indeed, $g(11)=2^4-1$, $g(23)=2^5+1$, $g(181)=2^{12}-1$. My program claims no other examples for $k\leq 4000$...

Surely, our equation may be rewritten as Pell equation $2\cdot (2^k)^2-M^2=\mp 2^b-1$, but how can one analyze it?

By the Ramanujan--Nagell theorem, there are no larger solutions for $x^2+7=2^n$ (smaller ones do not count in our case).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In MSE the user Aeryk observed a nice pattern in the base-4 notation. I commented: "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." (The number 725 is such a preimage, btw) $\endgroup$
    – Gottfried Helms
    Commented Jun 6, 2016 at 23:13
4
$\begingroup$

This is no answer, just some more illustrative material triggered by the numberlist of @Stefan Kohl.

I consider the numbers $m$ from Stefan's list in base-4 representation.

By that representation the iterations exhibit some much simplified pattern: if the last digit is "1" subtract and square, otherwise simply cut that digit. This reduces to two operations on some number $m$:

  • $f(m)$: cut all trailing digits in base-4-representation of $m$ after the last "1" ; return(m)
  • $g(m)$: do $m = (m-1)^2$; do $m = f(m)$ ; return(m)

In the following table I document the initial $f(m)$-transform and then the first couple of transforms by $g(m)$. (Note that a lot(!) of iterations of the original description are thus hidden).
The data found in the table reduce to only two systematic patterns which are able to decrease to zero.

 --- m=65533 '33333331'_4 ------------------
33333331
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=65541 '100000011'_4 ------------------
100000011
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=131065 '133333321'_4 ------------------
133333321
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=131069 '133333331'_4 ------------------
133333331
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=131077 '200000011'_4 ------------------
200000011
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=131081 '200000021'_4 ------------------
200000021
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=262129 '333333301'_4 ------------------
333333301
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262132 '333333310'_4 ------------------
33333331
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262134 '333333312'_4 ------------------
33333331
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262135 '333333313'_4 ------------------
33333331
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262137 '333333321'_4 ------------------
333333321
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262141 '333333331'_4 ------------------
333333331
3333333200000001
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=262149 '1000000011'_4 ------------------
1000000011
10000000200000001
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
--- m=262153 '1000000021'_4 ------------------
1000000021
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=262161 '1000000101'_4 ------------------
1000000101
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=262164 '1000000110'_4 ------------------
100000011
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=262166 '1000000112'_4 ------------------
100000011
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=262167 '1000000113'_4 ------------------
100000011
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524257 '1333333201'_4 ------------------
1333333201
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524260 '1333333210'_4 ------------------
133333321
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524262 '1333333212'_4 ------------------
133333321
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524263 '1333333213'_4 ------------------
133333321
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524273 '1333333301'_4 ------------------
1333333301
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524276 '1333333310'_4 ------------------
133333331
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524278 '1333333312'_4 ------------------
133333331
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524279 '1333333313'_4 ------------------
133333331
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524281 '1333333321'_4 ------------------
1333333321
3333333200000001
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
1
--- m=524285 '1333333331'_4 ------------------
1333333331
33333333000000001
3333333200000001
333333300000001
33333320000001
3333330000001
333332000001
33333000001
3333200001
333300001
33320001
3330001
332001
33001
3201
301
21
--- m=524293 '2000000011'_4 ------------------
2000000011
100000001000000001
10000000200000001
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
--- m=524297 '2000000021'_4 ------------------
2000000021
10000000200000001
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
--- m=524305 '2000000101'_4 ------------------
2000000101
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524308 '2000000110'_4 ------------------
200000011
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524310 '2000000112'_4 ------------------
200000011
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524311 '2000000113'_4 ------------------
200000011
1000000100000001
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524321 '2000000201'_4 ------------------
2000000201
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524324 '2000000210'_4 ------------------
200000021
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524326 '2000000212'_4 ------------------
200000021
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1
--- m=524327 '2000000213'_4 ------------------
200000021
100000020000001
10000010000001
1000002000001
100001000001
10000200001
1000100001
100020001
10010001
1002001
101001
10201
1101
121
21
1

Another try with numbers near the odd powers of $\sqrt2$: $x_k=\sqrt 2 ^k $ where $k=2j+1$. Let $a_k=\lfloor x_k \rfloor $ and $b_k=\lceil x_k \rceil $ the two neighboured integers.
I expected, that in cases where $x_k$ is "extremely" near to one of the bounds we have possibly special behaviour, like for instance if $m=a_{15} = 181$ and indeed this value seems to have a divergent trajectory while for $k$ in the near of that the trajectories approach zero. Unfortunately it seems that this is not so significant as expected; for $k>80$ I didn't find any convergent trajectory at all.

Here is some part of the table:

Part 1: take that number of $a_k$ and $b_k$ which is odd as argument $m$:

these converge:
k=7  m=11------------------
23
121
21
1

k=9  m=23------------------
11
1

k=11  m=45------------------
231
1321
3201
301
21
1

k=13  m=91------------------
11
1

this doesn't seem to converge
k=15  m=181------------------  ( likely divergent !)
2311
133221
33220021
3310030322001
3220330213031221021
31033320111230303300302001313223101
223320031033333201331222232232023120303121021311312301030210223221

these converge 
k=17,19,21,23,25,27,29,35,39,47,55,63,67,71 
k=75  m=194368031999 ------------------
2311001
13333321
333332000001
33333000001
3333200001
333300001
33320001   --- known convergent pattern

these don't seem to converge:
k=31,33,37,41,43,45,49,51,53,57,59,61,65,69,73,77... 255

For the selections of the even number of $a_k$ and $b_k$ we have a similar picture.

Part 2: take that number of $a_k$ and $b_k$ which is even as argument $m$:

these converge
k=7  m=12 ---------------
30
1321
3201
301
21
1

k=9  m=22 ---------------
11
1

k=13  m=90 ---------------
11
1

k=15  m=182 ---------------
231
1321
3201
301
21
1

these converge too
k=17,21,25,29,31,33,37,43,51,59,75,79 

k=83  m=3109888511976 ---------------
2311001
13333321
333332000001
33333000001
3333200001
333300001
33320001   // this is known to be a convergent pattern 

These don't seem to converge
k=11,19, 23, 27, 35,39,41,45 .. 49,53 ..57 ,61..73 ,77, 81 ,85 ...255
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .