6

Consider the following variant of the Collatz function: $f:\mathbb N\rightarrow\mathbb N$ is defined by \begin{equation} f(n):=\begin{cases} n/2 & \text{if $n$ is even}\\ 5n+1 & \text{if $n$ is odd}\\ \end{cases} \end{equation} Contrary to the Collatz function with $3n+1$, many orbits of this function seem to diverge. The smallest one is probably 7. After 32282 iterations, $f^k(7)$ is already larger than $10^{1000}$. Can one prove that this orbit diverges to infinity?

Here is the Python code that I used:

from decimal import *
getcontext().prec=1001

def collatz5(n):
    if n%2 == 0:
        return Decimal(n)/Decimal(2)
    else:
        return Decimal(5)*Decimal(n)+Decimal(1)


n=7
for i in range(100000):
    if n>10**1000:
        print("bound exceeded")
        print("number of steps: ",i)
        break
    n=collatz5(n)
Riemann
  • 537
  • 11
    Just to clarify: the reason why one heuristically expects many orbits to diverge is because $5/2 = 2.5 > 2$ while in the Collatz case one has $3/2 = 1.5 < 2$. – Stanley Yao Xiao Jan 16 '24 at 19:04

2 Answers2

9

As far as I understand it, under the current state of things we cannot prove that any orbit of 5k+1 diverges. In fact, as far as I'm aware we cannot even prove that there exists an odd $a>1$ such that the function

\begin{equation} f(n):=\begin{cases} n/2 & \text{if $n$ is even}\\ an+1 & \text{if $n$ is odd}\\ \end{cases} \end{equation}

contains a divergent orbit even though we suspect that these exists for any $a>3$. Edit: See comments below that we can almost but not fully prove this for $a=1093$.

JoshuaZ
  • 6,090
  • 6
    For $a=1093$ R.Crandall in 1978 made a specific argument: "The third solvable case, $a = 1093$, is rather peculiar. In this problem, a number $n$ has height one if and only if it is of the form $n = (2^{364p} - 1)/1093 $ ; but, as it turns out, all other $n$ have infinite height. This follows from the fact that in the $1093 n + 1$ problem, no $n$ can have height $2$, since Eq. (7.2), with $3$ replaced by $1093$, $n = 1$, and $k$ set equal to two, is easily seen to be impossible." (cntd...) – Gottfried Helms Jan 17 '24 at 10:48
  • 8
    (...cntd) "This case is the only one for which it is known that almost all $n$ have infinite height." So it seems, that for the Wieferich-prime $a=1093$ divergence has been proven, and I think the same argument should be valid for the second Wieferich-prime $a=3511$ [R.E.Crandall, 1978, On the "3x + 1" Problem] – Gottfried Helms Jan 17 '24 at 10:51
  • 1
    @GottfriedHelms Thanks. Corrected. – JoshuaZ Jan 17 '24 at 13:03
  • 1
    @GottfriedHelms Interesting! Could you perhaps also tell what Crandall considers as the first two solvable cases? I'm curious. – Max Muller Jan 17 '24 at 17:54
  • 2
    @MaxMuller - that are the cycles for $a=5$ and $a=181$ "The status of Conjecture (8.1) is unsettled for most of the remaining "$ax + 1$" problems. It is known that the conjecture is true for $a = 5, 181,$ and $1093$; but all other cases remain elusive." (pg 1291; I changed his variable $q$ to fit with $a$ here). (I could send you the pdf if you don't find it online.) – Gottfried Helms Jan 17 '24 at 18:16
  • 2
    I see, thank you! I've found it - initially I thought it was a book (of which the contents are usually harder to find on the internet), but it's a paper (p. 11): https://www.jstor.org/stable/2006353 – Max Muller Jan 17 '24 at 18:46
  • 2
    For a substantial extension of Crandall's observation, see this paper of Franco and Pomerance: https://math.dartmouth.edu/~carlp/PDF/paper101.pdf ("On a conjecture of Crandall concerning the qx +1 problem") – so-called friend Don Jan 18 '24 at 00:23
  • 4
    I have looked at the papers linked and I don't think that they prove existence of infinite trajectory. Crandall shows that for $a=1093$ the trajectory cannot reach $1$ unless it gets there in one step, but that doesn't preclude existence of cycles, so unless I'm missing something, for all we know all such trajectories might eventually end in a cycle. – Wojowu Jan 18 '24 at 01:21
  • Yes, that's right: There's nothing in the Crandall work (or the extensions) about divergence to infinity --- just about failing to reach 1. – so-called friend Don Jan 18 '24 at 03:08
  • @Wojowu - ah, that's the point why I've always felt to have been trapped in that related arguments of R. Crandall, but didn't resolve (just recently in a comment to https://mathoverflow.net/q/372733/7710) . "The trajectory cannot reach $1$" - that's the focus there, nothing explicite about divergence or cycling. Thank you! – Gottfried Helms Jan 18 '24 at 08:08
1

I can't prove that an orbit diverges, but we would expect there to be many because the average growth factor is $\frac{1}{2}(\frac{5}{2})^{2-1} = 1.25>1$. This in contrast to the normal function where the growth factor is $\frac{1}{2}(\frac{3}{2})^{2-1} = 0.75<1$

A reasonable generalization and conjecture for the Collatz problem is:

$f_{pq}(n):= \begin{cases} n/p & \quad \text{if } n \text{ is divisible by }p\\ qn \text{ rounded up to the nearest multiple of }p & \quad \text{if } n \text{ is not divisible by }p\\ \end{cases}$

We can also express this function as (for ease of computation)

$ f_{pq}(n):= \begin{cases} n/p & \quad \text{if } n \text{ mod }p=0\\ qn + p - (qn\text{ mod }p) & \quad \text{otherwise}\\ \end{cases} $

Define the expected growth factor after $p$ iterations as $\frac{1}{p}(\frac{q}{p})^{p-1}$. I conjecture that when $p,q$ are relatively prime, $f_{pq}$ contains divergent orbits if and only if the expected growth factor is greater than 1.

Brady Gilg
  • 111
  • 4