Take the 2-minute tour ×
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|improve this question
23  
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
10  
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 28 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|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|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

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|improve this answer
2  
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

Your Answer

 
discard

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.