31
$\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$
5
  • 32
    $\begingroup$ It's false as stated since, e.g. 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13, ... $\endgroup$
    – Bill Dubuque
    Dec 16, 2010 at 20:21
  • 22
    $\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$
    – Adrian Petrescu
    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$
    – Gottfried Helms
    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$
    – Gottfried Helms
    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$
    – Anatoly
    Jul 30, 2021 at 18:16

2 Answers 2

Reset to default
49
$\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
    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
    Dec 16, 2010 at 23:11
  • 3
    $\begingroup$ Does n=7 cycle or is it divergent? $\endgroup$
    – mhum
    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$
    – Gottfried Helms
    Mar 29, 2012 at 10:44
  • $\begingroup$ $n=17$ gives a cycle of length 10. $\endgroup$
    – MJD
    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
    Jun 4, 2015 at 3:24

You must log in to answer this question.

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