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$.

  • 28
    $\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 '10 at 20:21
  • 19
    $\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 '10 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 '17 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 '17 at 16:22

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

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

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.

  • $\begingroup$ $n=7$ gives a pretty long cycle I believe. $\endgroup$ – Aryabhata Dec 16 '10 at 23:11
  • 2
    $\begingroup$ Does n=7 cycle or is it divergent? $\endgroup$ – mhum Jan 4 '11 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 '12 at 10:44
  • $\begingroup$ $n=17$ gives a cycle of length 10. $\endgroup$ – MJD Jun 3 '15 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 '15 at 3:24

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.