32
$\begingroup$

The Collatz Conjecture is a famous conjecture in mathematics that has lasted for over 70 years. It goes as follows:

Define $f(n)$ to be as a function on the natural numbers by:

$f(n) = n/2$ if $n$ is even and $f(n) = 3n+1$ if $n$ is odd

The conjecture is that for all $n \in \mathbb{N}$, $n$ eventually converges under iteration by $f$ to $1$.

I was wondering if the "5n+1" problem has been solved. This problem is the same as the Collatz problem except that in the above one replaces $3n+1$ with $5n+1$.

$\endgroup$
6
  • 34
    $\begingroup$ It's false as stated since, e.g. 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13, ... $\endgroup$ Commented Dec 16, 2010 at 20:21
  • 23
    $\begingroup$ A more interesting version of this question may be "How can we generalize the $kn+1$ problem to higher values of $k$ ?" since the naive way obviously doesn't quite work. $\endgroup$ Commented Dec 16, 2010 at 21:44
  • 1
    $\begingroup$ @Adrian: if $k=2^j-1$ we have "trivial cycle" at 1 and if $k=2^j+1$ at -1. The only "nontrivial" cycle that I've found besides $k=3$ and n in the negative and $k=5$ and n in the positive numbers is with $k=181$ where it gives two short cycles, each with smallest element below 100 - I think one has $n=33$ and the second one has $n=83$ , have it not at the top of my mind. (It seems that $k=181$ solution is not widely known so far - using the common literature and internet search) $\endgroup$ Commented Apr 7, 2017 at 21:47
  • 1
    $\begingroup$ @AdrianPetrescu: To complete my previous comment: in his 1978 paper R.E.Crandall reports, that for a large number of $k$ the existence of cycles for the $kn+1$-problem was tested, finding none except one for the $k=181$ problem (he was missing the second cycle). I'd recomputed such a program and ended up in: no cycle in $a_{\min} \lt 10000$ testing many lengthes for $k \le 1000 000$ except two cycles for $k=181$ with smallest elements $\lt 100$ . $\endgroup$ Commented May 5, 2017 at 16:22
  • $\begingroup$ @AdrianPetrescu even more generalised, if we have $n -> an + 2b + 1 for n odd; n -> 1/2 n for n even$, will $n$ end in a 4 2 1 loop? $\endgroup$
    – Someone
    Commented Jul 30, 2021 at 18:16

3 Answers 3

53
$\begingroup$

You shouldn't expect this to be true. Here is a nonrigorous argument. Let $n_k$ be the sequence of odd numbers you obtain. So (heuristically), with probability $1/2$, we have $n_{k+1} = (5n_k+1)/2$, with probability $1/4$, we have $n_{k+1} = (5 n_k+1)/4$, with probability $1/8$, we have $n_{k+1} = (5 n_k+1)/8$ and so forth. Setting $x_k = \log n_k$, we approximately have $x_{k+1} \approx x_k + \log 5 - \log 2$ with probability $1/2$, $x_{k+1} \approx x_k + \log 5 - 2 \log 2$ with probability $1/4$, $x_{k+1} \approx x_k + \log 5 - 3 \log 2$ with probability $1/8$ and so forth.

So the expected change from $x_{k}$ to $x_{k+1}$ is $$\sum_{j=1}^{\infty} \frac{ \log 5 - j \log 2}{2^j} = \log 5 - 2 \log 2.$$

This is positive! So, heurisitically, I expect this sequence to run off to $\infty$. This is different from the $3n+1$ problem, where $\log 3 - 2 \log 2 <0$, and so you heurisitically expect the sequence to decrease over time.

Here is a numerical example. I started with $n=25$ and generated $25$ odd numbers. Here is a plot of $(k, \log n_k)$, versus the linear growth predicted by my heuristic. Notice that we are up to 4 digit numbers and show no signs of dropping down.

alt text

$\endgroup$
1
  • 2
    $\begingroup$ Related (I was not aware of the existence of your post when writing that). $\endgroup$
    – Did
    Commented Aug 18, 2013 at 15:42
23
$\begingroup$

In Part I of Lagarias' extensive, annotated bibliography of the 3x+1 problem, he notes a 1999 paper by Metzger (reference 112) regarding the 5x+1 problem:

For the 5x + 1 problem he shows that on the positive integers there is no cycle of size 1, a unique cycle of size 2, having smallest element n = 1, and exactly two cycles of size 3, having smallest elements n = 13 and n = 17, respectively.

It is unclear from the notes whether the paper shows that these are the only cycles of the 5x+1 problem or whether there may exist longer cycles.

$\endgroup$
5
  • $\begingroup$ $n=7$ gives a pretty long cycle I believe. $\endgroup$
    – Aryabhata
    Commented Dec 16, 2010 at 23:11
  • 3
    $\begingroup$ Does n=7 cycle or is it divergent? $\endgroup$
    – mhum
    Commented Jan 4, 2011 at 2:32
  • $\begingroup$ 7 is element of a sequence which begins at 35 and has no more predecessor. It seems, that most of the sequences which begin at odd numbers, divisible by 5, have divergent trajectories (except, for instance, 65). It is also easy to prove for many short lengthes that there cannot be cycles of that lengthes. $\endgroup$ Commented Mar 29, 2012 at 10:44
  • $\begingroup$ $n=17$ gives a cycle of length 10. $\endgroup$
    – MJD
    Commented Jun 3, 2015 at 15:17
  • 3
    $\begingroup$ It's not clear from the excerpt I quoted, but in that article the "size" of a cycle refers to the number of distinct odd elements in the cycle, not the length. $\endgroup$
    – mhum
    Commented Jun 4, 2015 at 3:24
0
$\begingroup$

Using a Python program, I calculated the orbit starting at 7. It seems to diverge to infinity with exponential speed. I calculated till the numbers exceeded $10^{1000}$. So probably, not every number will end up at 1. And not all numbers will end up in a cycle.

Initially, my program returned to 7 after a large number of steps. However, it turned out that the program made small errors when the numbers became very large. Using the decimal module resolved this problem.

Here is the 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)
$\endgroup$
2
  • 1
    $\begingroup$ A267970 is relevant, it gives a conjectured list of numbers that never loop $\endgroup$
    – Sil
    Commented Jan 16 at 21:53
  • $\begingroup$ You don't need the decimal module for this--you can just Python's native integer arithmetic, which is exact and works for arbitrary-size integers. Just make sure to use integer division: when you divide by 2, you should use the // operation to get an integer output (rather than / which will give a floating-point output). Your program will be much faster if you let Python use its native int type! (Also, I noticed that your program is re-calculating 10**1000 each time through the loop; it would be more efficient to calculate that value once, before the loop.) $\endgroup$
    – mathmandan
    Commented Jun 12 at 15:11

You must log in to answer this question.

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