Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question
It's false as stated since, e.g. 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13, ... – Bill Dubuque Dec 16 '10 at 20:21
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. – Adrian Petrescu Dec 16 '10 at 21:44

3 Answers 3

up vote 34 down vote accepted

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

share|cite|improve this answer
Related (I was not aware of the existence of your post when writing that). – 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.

share|cite|improve this answer
$n=7$ gives a pretty long cycle I believe. – Aryabhata Dec 16 '10 at 23:11
Does n=7 cycle or is it divergent? – mhum Jan 4 '11 at 2:32
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. – Gottfried Helms Mar 29 '12 at 10:44
$n=17$ gives a cycle of length 10. – MJD Jun 3 at 15:17
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. – mhum Jun 4 at 3:24

you have the wrong problem, it is solved by 13. The generalization next is:

if n = 3k then k
if n = 2k then k
else 5n+1
share|cite|improve this answer
You have a point, that map does exhibit rather more Collatz-like behavior. I suppose we can define a similar map for any prime $p$: divide out all prime factors less than $p$, multiply by $p$ and add one. I wonder if there's anything interesting to say about such maps in the limit as $p \to \infty$... – Ilmari Karonen Mar 29 '12 at 5:59
Does that map have a name? – smci Nov 17 '14 at 21:48
But if n = 6k , you divide it by 3 not 2? Why should 3 take precedence? – smci Nov 17 '14 at 21:51
@smci: It doesn't matter since once you've divided out all the threes, you'll divide out the twos as well. It just changes the order your sequence goes in, and not the eventual destination of that sequence. – Kevin Oct 21 at 18:31
@quanta, Kevin: it's unclear which/both if -clause the else attaches to. Depending on how we parse this it could make a difference. In any case it adds redundant intermediate steps. – smci Oct 21 at 21:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.