6
$\begingroup$

The Collatz conjecture states that iteratively applying the map

$$f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

to any positive integer $n_0$ eventually yields $1$.


I'm looking for other non-obvious examples in mathematics of (proven or conjectured) statements of the form:

Take any object $x$ from a set $X$ and repeatedly apply the (not necessarily arithmetic) transformation $\sigma:X\rightarrow X$. You will eventually reach $y\in X$ after a finite number of steps.

The difference between this pattern and an attractor in physics is that here, the system is discrete and converges within a finite number of steps, and that all elements of the set are inside the "basin of attraction" (also, it is possible for even the fixed point to escape again for a cycle, as is the case with the Collatz map for $1 \rightarrow 4 \rightarrow 2 \rightarrow 1$).


Trivial examples I can think of from the top of my head:

  • Take any integer $n$ and repeatedly subtract $1$. You will eventually reach $0$.
  • Take any polygon and repeatedly cut off a triangle whose one edge connects two corners of the polygon. You will eventually be left with a triangle (though of course this triangle is only unique if you consider it through the lens of graph topology).
  • Take any permutation $a \in S_n$ in list form and repeatedly traverse it from left to right, exchanging any two adjacent elements that are in the wrong order. You will eventually reach the trivial permutation $1 \in S_n$ (Bubble sort algorithm).

The problem is that in these examples, the fact that all initial states converge and even the number of steps towards convergence are immediately obvious and predictable. I really like the way the convergence time of the Collatz map behaves pseudorandomly. Are there any more examples with that property?

$\endgroup$
2
$\begingroup$

Let the set $X$ the positive integers which are divisible by $9$. Let the transformation $\sigma$ be the operation of computing the digit sum.
Then taking any element from $X$ and applying repeatedly $\sigma$ gives $y=9$.

$\endgroup$
  • $\begingroup$ I like this one the most. $\endgroup$ – user139000 Jun 20 '14 at 21:49
2
$\begingroup$

An alternative is $$ x_{k+1} = \left\{ \begin{array} {} x_k /2 & \text{if } x_k \equiv 0 \pmod 2 \\ 3 x_k+1 & \text{if } x_k \equiv 1 \pmod 4 \\ 3 x_k-1 & \text{if } x_k \equiv 3 \pmod 4 \\ \end{array} \right. $$

This is -more than the Collatz-transformation- even guaranteed to run into the trivial cycle for every positive starting number $x_0$

If we write the trajectories displaying only the odd natural numbers and always beginning at odd multiples of 3 (because multiples of 3 cannot occur in the tail of a trajectory) we get $$ \begin{array} {} 3 &\to 1 \\ 9 &\to 7 &\to 5 & \to 1 \\ 15 &\to 11 &\to 1 \\ 21 &\to 1 \\ 27 &\to 5 &\to 1 \\ 33 &\to 25 &\to 19 &\to 7 &\to \text{(see above)}\\ ... \\ \end{array}$$

Tightly related are version like $5x+1$ where the following division is made by $2$ or $3$ depending on the modular residue class, where then apparently everything runs into the trivial cycle. (But well, these are not really qualitatively different ideas)

$\endgroup$
2
$\begingroup$

A similar recursive algorithm can be based on “good numbers”. Given any Integer n, the sum of the digits of n^2 is the “good number" of n. The relation is surjective (many Integers have the same good number)

    For example:
    2713^2 = 7360369, 
    7+3+6+0+3+6+9 = 34, 
    34 is the good number of 2713.

We can recursively calculate the good number of 34,

    34^2 = 1156,      
    1+1+5+6 = 13,    
    13 is the good number of 34, 

We carry on

    13^2 = 169
    1+6+9 = 16
    16 is the good number of 13

and so on.

So doing we see Integers connected into 3 convergent trees, respectively converging towards three “attractors” which are 1, 9, and the couple 13-16. See graph of the 3 converging trees here

COMPLEMENTARY NOTE

Given an Integer n we know that the sum of its digits S(n) is congruent to n modulo 9

    n ≡ S(n) (modulo 9)  
   (n and S(n) have the same remainder when divided by 9)

So any Integer can be written as n = 9k + r and its square n^2 = (9k + r)^2
or (81k^2 + 18kr + r^2) or (9k’ + r^2)

    The table   r   1   2   3   4   5   6   7   8
              r^2   1   4   9   16  25  36  49  64
        r^2 mod 9   1   4   0   7   7   0   4   1   

    shows that good numbers can only be of the form 
       9k,      9k + 1,     9k + 4,     9k + 7

 The first few are given below:
            9k,         9k + 1,     9k + 4,     9k + 7
    k=0      0           1           4           7
    k=1      9          10          13          16
    k=2     18          19          22          25
    k=3     27          28          31          34
    k=4     36          37          40          43
$\endgroup$
  • $\begingroup$ an amazing example, indeed! $\endgroup$ – Gottfried Helms Oct 11 '18 at 5:20
1
$\begingroup$

Hm, not sure whether this is an example in the scope of your question... What about rowwise Gaussian elimination in a matrix of $c$ columns and $r=c+a$ rows: the last $a$ rows become evantually zero-vectors?

$\endgroup$
1
$\begingroup$

Consider the following operation on an arbitrary positive integer:

If the number is divisible by 12, divide it by 12.

If the number is divisible by 10, divide it by 10.

If the number is divisible by 8, divide it by 8.

If the number is divisible by 6, divide it by 6.

If the number is divisible by 4, divide it by 4.

If the number is divisible by 2, divide it by 2.

If the number is odd, multiply it by 5 and add 1.

The tests should be performed in this order.

The conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

This can be tested by running this simple python script:

#!/usr/bin/python

for i in range(2,1000):
    x = i
    while x != 1:        
        print "{0}, ".format(x),                       
        if x % 12 == 0:
            x = x / 12
        elif x % 10 == 0:
            x = x / 10
        elif x % 8 == 0:
            x = x / 8
        elif x % 6 == 0:
            x = x / 6
        elif x % 4 == 0:
            x = x / 4
        elif x % 2 == 0:
            x = x / 2
        else: 
            x = 5 * x + 1
    print "\n"
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy