19
$\begingroup$

Let's consider the following variant of Collatz $(3n+1) : $

If $n$ is odd then $n \to n^2-1.$

$1\to 0.$

$3\to 8\to 1\to 0.$

$5\to 24\to 3\to 0.$

$7\to 48\to 3\to 0.$

$9\to 80\to 5\to 0.$

$11\to 120\to 15\to 224\to 7\to 0.$

$\color{red}{13\to 168\to 21\to 440\to 55\to 3024\to 189\to 35720\to 4465\to 19936224\to 623007\to\ldots\ ?}\ $

Does the sequence starting with $13$ go off to infinity? If yes, what is a proof? If no, is there a starting number whose sequence does go off to infinity, and how do we prove either that such a number must exist, or even better that a specific starting number goes off to infinity?

Here is some Python code I ran, which suggests that the numbers in the sequence starting at $13$ quickly become large:

n=13
num_loops=0
print(n)
while n!=0:
    if n%2==0:
        n//=2
    else: n=n**2-1
    print('\n', n)
    num_loops+=1
    if num_loops==70:
        print("too many loops")
        break
$\endgroup$
17
  • 5
    $\begingroup$ You may get better performance out of your code if you use if n%2==0 (rather than if math.floor((n/2))==n/2); and n //=2 (rather than n/=2)...then you will never get into floats at all. $\endgroup$
    – paw88789
    May 20 at 22:27
  • 4
    $\begingroup$ You get provably unbounded orbits if you replace $n^2 - 1 $ by $n^2 + 1 $ $\endgroup$
    – Will Jagy
    May 20 at 23:18
  • 7
    $\begingroup$ $n^2+1$ never divides by $4$ so at each step you divide by two and then square and that obviously goes to infinity with any odd from $3$ on; $n^2-1$ always divides by $4$ and of course many times by more so you have big reductions and big increases so numerics may not be that conclusive $\endgroup$
    – Conrad
    May 20 at 23:23
  • 8
    $\begingroup$ All odd numbers except $2^k \pm 1$ will lead to greater next odd number, and also $2^k \pm 1$ will spiral down to $0$ afterwards, so a sequence will increase forever iff it avoids integers of this form $\endgroup$
    – Sil
    May 20 at 23:40
  • 4
    $\begingroup$ @EricSnyder I think you have found the key to it. Very nice. $\endgroup$
    – Will Jagy
    May 21 at 19:14

2 Answers 2

7
$\begingroup$

The set of solutions can be written as table, segmented by e'th powers of $2$ :

  t |     e=0                  |       e=1                  |       e=2                  |    e=3                      |    e=4                       |   ...
----+--------------------------+----------------------------+----------------------------+-----------------------------+------------------------------+---- 
    |         ...              |           ...              |           ...              |           ...               |            ...               |
  -4|  56*2^2  =  (-15)^2-1    |   105*2^3  =  (-29)^2-1    |   203*2^4  =  (-57)^2-1    |   399*2^5  =  (-113)^2-1    |    791*2^6  =  (-225)^2-1    | 
  -3|  30*2^2  =  (-11)^2-1    |    55*2^3  =  (-21)^2-1    |   105*2^4  =  (-41)^2-1    |   205*2^5  =   (-81)^2-1    |    405*2^6  =  (-161)^2-1    | 
  -2|  12*2^2  =   (-7)^2-1    |    21*2^3  =  (-13)^2-1    |    39*2^4  =  (-25)^2-1    |    75*2^5  =   (-49)^2-1    |    147*2^6  =   (-97)^2-1    | 
    |
  -1|   2*2^2  =   (-3)^2-1    |     3*2^3  =   (-5)^2-1    |     5*2^4  =   (-9)^2-1    |     9*2^5  =   (-17)^2-1    |     17*2^6  =   (-33)^2-1    | 
   0|   0*2^2  =    (1)^2-1    |     1*2^3  =    (3)^2-1    |     3*2^4  =    (7)^2-1    |     7*2^5  =    (15)^2-1    |     15*2^6  =    (31)^2-1    | 
    |
   1|   6*2^2  =    (5)^2-1    |    15*2^3  =   (11)^2-1    |    33*2^4  =   (23)^2-1    |    69*2^5  =    (47)^2-1    |    141*2^6  =    (95)^2-1    | 
   2|  20*2^2  =    (9)^2-1    |    45*2^3  =   (19)^2-1    |    95*2^4  =   (39)^2-1    |   195*2^5  =    (79)^2-1    |    395*2^6  =   (159)^2-1    | 
   3|  42*2^2  =   (13)^2-1    |    91*2^3  =   (27)^2-1    |   189*2^4  =   (55)^2-1    |   385*2^5  =   (111)^2-1    |    777*2^6  =   (223)^2-1    | 
   4|  72*2^2  =   (17)^2-1    |   153*2^3  =   (35)^2-1    |   315*2^4  =   (71)^2-1    |   639*2^5  =   (143)^2-1    |   1287*2^6  =   (287)^2-1    | 
    |         ...              |           ...              |           ...              |           ...               |            ...               |
----+--------------------------+----------------------------+----------------------------+-----------------------------+------------------------------+---- 

meaning always $$n_2 \cdot 4\cdot 2^e = n_1 ^2 -1 \tag 1 $$

Here $n_2=f_e(t)$ can be written as a quadratic and $n_1=g_e(t)$ as a linear polynomial in $t \in \mathbb Z$. The shown data would have rowindices $t$ in the interval $t=-4..+4$.

We can construct the polynomials in $t$ from the values in a column with the rowindex taken as $t$ in the interval $-4...4$ and can then write $$ \begin{array} {} f_e(t) &= 4 \cdot 2^e \cdot t \cdot (t+1)-2 \cdot t+2^e-1 \\ g_e(t) &= 4 \cdot 2^e \cdot t+2 \cdot 2^e-1 \end{array} \tag 2$$

A better memorizable version is this:
$$ \begin{array} {} f_e(t) = 2^e \cdot (2 t +1)^2-(2 t+1) \\ g_e(t) = 2^e \cdot 2 \cdot (2 \cdot t+1 )-1 \end{array} \tag 3$$ and replacing the odd values $2t+1$ by $u \in \mathbb Z $ \ $ 2 \mathbb Z $ gives the even shorter: $$ \begin{array} {} f_e(u) = u \cdot (2^e \cdot u-1) \\ g_e(u) = 2 \cdot (2^e \cdot u-1)+1 \end{array} \tag 4$$

To prove equality according to (1) it suffices to expand and insert this into the equation (1): $$ 4 \cdot 2^e \cdot f_e(u) = g_e(u)^2 - 1 \tag 5$$ We find the equality in a few steps.


Relation to Sil's and EricSnyder's comments and @WillJagy's analysis: in the table the $4$'th and $5$'th rows contain the cases, where $n_2 \lt \mid n_1 \mid $, which has been problematized by Will Jagy's answer; his notation $(2^k,x,y)$ there is my notation $(4 \cdot 2^e,n_1,n_2)$ here.

Update: This idea seems to allow to proceed to a proof, that there are only finitely many other orbits towards zero than that of $n_1=2^k \pm 1$ with $k>2$ (or $4 \cdot 2^e$ with $e>0$), and that there are no cycles and that thus all other orbits diverge infinitely.

The critical two types of $n_1$ occur regularly in row $t=-1$ and $t=0$, so we need only find $n_1$ where the related $n_2$ has the form $2^k \pm 1$ in the other rows $t<-1 $ or $t>0$, which would iterate then to the center rows and thus to zero.

(a): Searching the rectangle $(t,e)=(-800...800,1..31)$ we find only three solutions: $$ (t,e,n_1,n_2) \in \{ (1,2,23,33), (-23,1,-181,4095), (1,1,11,15) \} \tag 6$$ so $n_1=11$, $n_1=23$ and $n_1=181$ iterate towards zero.

(b): Now it could happen, that the $n_1$ values $(23),(181),(11)$ occur as $n_2$ values elsewhere, with three other values $n_1$ and are thus themselves iterates.
But this does not happen, and fortunately we need only a finite searchspace to prove this: using the ordering of the $n_2$ values in a column and along the rows.

So if we could prove, that indeed the three cases (a) are the only ones, we had solved the problem in the OP. It seems to me, that an "A. Baker"-style proof might be possible to limit the search-space to a finite rectangle, but I've not so much expertise to do that on my own, at least at the moment. But there are results about the distance of squares and powers of $2$ available, so maybe we need only refer to one of that results.
See for instance this recent question in MSE and especially Mike Bennet's answer.

Update2: Proof for (eq.6)
The case is indeed solvable; there is an article of Laszlo Szalai, 2001 who deals with a slightly generalized form of the question, from which by

  • Theorem1 (Szalay) "if the positive integers n,m, and x with $n \gt m$ satisfy $$2^{n-m} + 1 = {x^2-1\over 2^m} $$ then (...uninteresting cases omitted...) (iii) $(n,m,x) \in \{(5,4,7),(9,4,23) \}$." The case $x=23$ is exactly that cases where $x$ is not of the form $2^k - 1$ and yet $f_e(x)$ is of that form and thus $x$ can iterate towards zero.
  • Theorem2 (Szalay) "if the positive integers n,m, and x with $n \gt m$ satisfy $$2^{n-m} - 1 = {x^2-1\over 2^m} $$ then (...uninteresting cases omitted...) (iii) $(n,m,x) \in \{(5,3,5),(7,3,11),(15,3,181) \}$." The cases $x=11$ and $x=181$ are exactly that cases where $x$ is not of the form $2^k + 1$ and yet $f_e(x)$ is of that form and thus both $x$ can iterate towards zero.

Thus: we have the proof, that

  • the three cases found in (eq 6) $$ (t,e,n_1,n_2) \in \{ (1,2,23,33), (-23,1,-181,4095), (1,1,11,15) \} $$ are the only solutions not in the rows $4$ and $5$ ($t=-1$ or $t=0$) in the above table, which iterate towards zero.
  • Since all other cases not in the rows $4$ and $5$ ($t=-1$ or $t=0$) increase by one iteration, all that other cases must diverge to infinity.

Szalay, László: The equations $2^N \pm 2^M \pm 2^L = z^2 $, Indag. Mathem. N.S., 131-142, 2002. See the downloadable links at the comments/answer of my earlier question in MO


Update3: Curious fact on the iteration of $a_1=13$. The fractional part of the double-log to base 2 seems to converge to some limit. See the protocol of the first 30 iterations (odd steps only):

 k   log_2(log_2(a_k))
-----------------------
[1, 1.88769671439]
[2, 2.13498231840]
[3, 2.53140883896]
[4, 2.91881409881]
[5, 3.59984673966]
[6, 4.26670326276]
[7, 5.02226916018]
[8, 5.95409288384]
[9, 6.88253436364]
[10, 7.85787043544]
[11, 8.84851166124]
[12, 9.84223857933]
[13, 10.8390917800]
[14, 11.8379099584]
[15, 12.8371215392]
[16, 13.8367271679]
[17, 14.8365299418]
[18, 15.8364559751]
[19, 16.8364066619]
[20, 17.8363820046]
[21, 18.8363727580]
[22, 19.8363681347]
[23, 20.8363658230]
[24, 21.8363635114]
[25, 22.8363627408]
[26, 23.8363623555]
[27, 24.8363622111]
[28, 25.8363621147]
[29, 26.8363620786]
[30, 27.8363620606]

Couldn't proceed further due to digit-length of occuring integers $a_k$ with finite memory... Defining $$b=2^{2^{0.836362060564583494096400006341-3}} \approx 1.1673140482117283628568828285728 ...$$ then it seems, we get approximation $a_k \to b^{2^k}$ depending on increasing precision of $b$ in the

$\endgroup$
2
  • 3
    $\begingroup$ Hi, Gottfried. Very nice! I hadn't noticed this, the detail being that @username inside an answer does not generally produce a notification for that user. Maybe same for questions... So, you appear to have proved the whole thing, including a classification. $\endgroup$
    – Will Jagy
    May 24 at 17:37
  • 3
    $\begingroup$ @Will - yes, happy that 3 or 4 days of grilling myself led to a result at all. I like it especially because it is the first case of something like collatz-iteration-style where a proof of divergence of some orbits is known to me - the "divergent"-cases seem to have little attention in general... $\endgroup$ May 24 at 18:03
2
$\begingroup$

About Eric Syder's comment: suppose $ x^2 - 1 = 2^k y$ with $x,y$ odd. We wish to investigate what happens when $y \leq x \; . \; \;$ Note that $\gcd(x+1, x-1) = 2$ because $x \equiv 1,3 \pmod 4.$ One of the $x \pm 1 $ is $\equiv 2 \pmod 4. $

Let us make the name $ \delta = \pm 1.$ Then we may demand $$ x + \delta \equiv 2 \pmod 4$$ This tells us that the integer $ \frac{x + \delta}{2} $ is odd. We also have $$ \frac{x + \delta}{2} \frac{x - \delta}{2} = 2^{k-2}y$$ By repeated division by $2$ it follows that $$ \frac{x - \delta}{2^{k-1}} = w $$ is an odd positive integer, with $$\frac{x + \delta}{2} \; \frac{x - \delta}{2^{k-1}} = y $$ IF WE ASSUME $$ w = \frac{x - \delta}{2^{k-1}} \geq 3, $$ we find $$ y = w \frac{x + \delta}{2} \geq 3 \frac{x + \delta}{2} \geq \frac{3x - 3}{2}$$ The assumption $ w \neq 1$ has led us to $y \geq \frac{3x - 3}{2}$ The hypothesis that $x \geq y$ now says $x \geq \frac{3x - 3}{2},$ or $ 2x \geq 3x - 3,$ or $3 \geq x$

If $ x \geq y$ and $ x \geq 5$ in $ x^2 - 1 = 2^k y,$ we find that $w=1$ in $ \frac{x - \delta}{2^{k-1}} = w .$ So that $ x - \delta = 2^{k-1} .$ or $$ x = \pm 1 + 2^{k=1}$$

$\endgroup$
2
  • $\begingroup$ Let’s suppose everything you’ve said is correct. Why don’t you want to also investigate when $y>x?$ For example, starting with $11,$ we get: $11\to 15=2^k-1,$ and therefore spirals down to $0.$ $\endgroup$ May 22 at 12:03
  • 2
    $\begingroup$ @AdamRubinson It's useful to focus on $x \ge y$, because that defines the cases where, with certainty, we eventually hit zero. Knowing that, we know that any other number that goes to zero (like $11$) must go through one of the others described by Will here. $\endgroup$ May 23 at 4:44

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.