Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wonder what is known about variations of Collatz where $3n+1$ is replaced by $3n + 2k + 1$ where k is a fixed positive integer. In the OP ' about Collatz $3n+3$ ' it was confirmed that $3n+3$ behaves like Collatz itself. About Collatz 3n+3?

I wonder about other values of $k$.

share|cite|improve this question
The title and body have conflicting versions of $k$. – joriki Oct 11 '12 at 17:02
The first stop for this kind of question is The 3x+1 problem and its generalizations by Lagarias. – lhf Oct 11 '12 at 17:07
Did a comment get romoved ?? I got a message of another comment ... – mick Oct 11 '12 at 20:08
Not exactly. Consider the case $3n+3$. There $Coll_{3n+3}(2^{m}k)$ behave $2^{m-1}k,\ldots,k,3(k+1),3Coll_{3n+1}(k+1)$. For the general case $Coll_{3n+3l}(2^{m}k)$ behave $2^{m-1}k,\ldots,k,3(k+l),3Coll_{3n+l}(k+l)$. So $Coll_{3n+15}(k)$ behaves like $3Coll_{3n+5}(k+5)$ for odd $k$. – P.. Oct 22 '12 at 20:44
@mick If you can find $k$ such that $\operatorname{Coll}_{3n+2k+1}$ give only one cycle then you proved Collatz conjecture.Of course if there is such a $k$ then necessary $2k+1=3^a$. See my answer. – P.. Oct 26 '12 at 19:05
up vote 4 down vote accepted
  1. (Collatz Conjecture) $\operatorname{Coll}_{3n+1}=\operatorname{Coll}$ (the original Collatz function) give only one cycle.
  2. For $\ell=3^ar, \ a\geq 1$ with $3 \nmid r , \ \operatorname{Coll}_{3n+\ell}$ behave like $\operatorname{Coll}_{3n+r}$ (meaning that iteration of $\ \operatorname{Coll}_{3n+\ell}$ beginning at $x$ terminates, for each $x \in \mathbb{N}$ iff iteration of $\operatorname{Coll}_{3n+r}$ beginning at $x$ terminates, for each $x \in \mathbb{N}$). In particular if $\ell=3^a$ then $\ \operatorname{Coll}_{3n+\ell}$ behave like $\operatorname{Coll}$.
  3. For $\ell$ such that $3 \nmid \ell , \ \operatorname{Coll}_{3n+\ell}$ give at least two cycles, the one being iteration of $\operatorname{Coll}_{3n+\ell}$ beginning at $1$, and the other iteration of $\operatorname{Coll}_{3n+\ell}$ beginning at $\ell$. Further for $k \in \mathbb{N}$ such that $\ell | k$ iteration of $\operatorname{Coll}_{3n+\ell}$ at $k$ behave like $\operatorname{Coll}$ (and eventually reach $\ell$, assuming the truth of Collatz conjecture).

For (2):

if $x=2^bk$ with $2 \nmid k$ then iteration of $\operatorname{Coll}_{3n+\ell}$ at $x$ goes: $$2^bk\rightarrow 2^{b-1}k\rightarrow \ldots\rightarrow k \rightarrow 3k+l=3k+3^ar=3(k+3^{a-1}r)\rightarrow \ldots $$ so whatever $x$ is, iteration of $\operatorname{Coll}_{3n+\ell}$ beginning at $x$ will give at some point $3y$, for some $y \in \mathbb{N}$.

If $2 \nmid y$ then $\operatorname{Coll}_{3n+\ell}(3y)=3\cdot 3y+\ell= 3( 3y+\frac{\ell}{3}) = 3\operatorname{Coll}_{3n+\frac{\ell}{3}}(y)$.

If $2|y$ then $\operatorname{Coll}_{3n+\ell}(3y)=3 \frac{y}{2}=3\operatorname{Coll}_{3n+\frac{\ell}{3}}(y)$.

And so on.

So $\ \operatorname{Coll}_{3n+\ell}$ behave like $\operatorname{Coll}_{3n+r}$.

For (3):

Let $x \in \mathbb{N}$. If $x=\ell k$ with $2 \nmid k$ then $\operatorname{Coll}_{3n+\ell}(x)=3\cdot \ell k+\ell= \ell( 3k+1) = \ell \operatorname{Coll}(y)$, while if $x=2\ell k$ then $\operatorname{Coll}_{3n+\ell}(x)=\frac{x}{2}=\ell k= \ell \operatorname{Coll}(2k)$.

So for $x \in \ell \mathbb{N}$ the iteration of $\operatorname{Coll}_{3n+\ell}$ at $x$ behave like $\operatorname{Coll}$.

This give at least one cycle and shows that for $x \in \ell \mathbb{N}$, iteration of $\operatorname{Coll}_{3n+\ell}$ at $x$ will eventually reach $\ell$.

Now working $\pmod{\ell}$ we see that for $x \notin \ell \mathbb{N}$ if iteration of $\operatorname{Coll}_{3n+\ell}$ at $x$ give a cycle this cycle is disjoint from the cycle obtained by $\operatorname{Coll}_{3n+\ell}(\ell)$(Or by $\operatorname{Coll}_{3n+\ell}(y)$ for any $y \in \ell \mathbb{N}$, if we assume the truth of Collatz conjecture). This is because for $x \not\equiv 0 \pmod \ell$ we have $3x+\ell \equiv 3x \not\equiv 0 \pmod \ell$ and (for even $x$) $\frac{x}{2} \equiv x \frac{l+1}{2} \not\equiv 0 \pmod \ell$.

We see that case (2) is similar to the case (3),with the exception that the three in $3n+\ell$ makes the iteration of $\operatorname{Coll}_{3n+\ell}$ at $x$ to produce a multiple of $3$ whatever $x$ is.

In the following table I list:

In the first column values of $\ell$. In the second how many cycles $\operatorname{Coll}_{3n+\ell}$ I believe give and in third pairs $(y,z)$(see the example). The integers $y$ are those minimal integers s.t. iteration of the various $\operatorname{Coll}_{3n+\ell}(y)$ give all cycles of $\operatorname{Coll}_{3n+\ell}$. The integers $z$ are the smallest positive integers such that iteration of $\operatorname{Coll}_{3n+\ell}$ beginning at $z$ reach $y$.

$$ \begin{array}{|c|c|c|} \hline \ell & \text{Number of cycles} & (y,z) \\ \hline 1 & 1 & (1,1) \\ \hline 5 & 6 & (1,1),(19,3),(5,5),(23,23), (187,123),(347,171)\\ \hline 7 & 2 & (5,1),(7,7)\\ \hline 11 & 3 & (1,1),(13,3),(11,11) \\ \hline 13 & 10 & (1,1),(13,13),(131,19),(211,99),\\ & & (259,123),(227,147),(287,159),\\ & & (251,163),(283,283),(319,319) \\ \hline 17 & 3 & (1,1),(23,9),(17,17)\\ \hline 19 & 2 & (5,1),(19,19)\\ \hline 23 & 4 & (41,1),(5,5),(7,7),(23,23)\\ \hline 25 & 8 & (7,1),(17,3),(5,5),\\ & & (95,15),(25,25),(115,115),\\ & & (935,615),(1735,855)\\ \hline 29 & 5 & (1,1),(11,3),(29,29),\\ & & (3811,2531),(7055,5859)\\ \hline 31 & 2 & (13,1),(31,31)\\ \hline \end{array}$$

For example for $\ell=17$ we have three cycles. They are:

  • $1\rightarrow20\rightarrow10\rightarrow5\rightarrow32\rightarrow\ldots \rightarrow 1$ of length 9,
  • $23\rightarrow146\rightarrow73\rightarrow \ldots \rightarrow46\rightarrow23$ of length 49 and
  • $17\rightarrow68\rightarrow34\rightarrow17$

For the second one $19$ is the smallest integer for witch $\operatorname{Coll}_{3n+17}$ will give this cycle.

share|cite|improve this answer
Nice answer. But I believe 3n+5 gives an unbounded amount of cycles. – mick Nov 1 '12 at 20:18
That's interesting. And why do you believe that? Do you know any cycle different from the six I gave? – P.. Nov 1 '12 at 21:31
I would need to check my data again ... later ... – mick Nov 1 '12 at 22:26
For this particular case I made an exhaustive checking for all values smaller than $10000000$ and I didn't find other cycles. – P.. Nov 1 '12 at 22:33
Then I am mistaken sorry. – mick Nov 1 '12 at 23:20

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.