Let the $3x+1$ map

$$ f(n) = \begin{cases} 3n+1 & \text {if $n$ is odd} \\ \frac{n}{2} & \text {if $n$ is even} \end{cases} .$$

Now we read the Wikipedia's page for the Collatz problem, also known by several names.

Example. Since $f(1)=4$, $f(4)=2$ and $f(2)=1$, the integer $n=1$ is not a counterexample for the Collatz conjecture (in other words, is the easier example of an integer satisfying the conjecture).

In the other hand we know that the pentagonal numbers of the form $$\omega(n)=\frac{3n^2-n}{2}$$ (related with partitions) are defined as $$\omega(n)=\sum_{k=0}^{n-1}(3k+1).$$

Thus if $n-1$ is odd (this is the first case of two, the second case with $n-1$ even) one can deduce easily combining previous and the definition of the $3x+1$ map that $$\omega(n)=1+\sum_{k\in \left\{ 1,3,5,\ldots,n-1 \right\}}f(k)+6\left(\sum_{k\in \left\{ 2,4,6,\ldots,n-2 \right\}}f(k)\right)+\sum_{k\in \left\{ 2,4,6,\ldots,n-2 \right\}}1.$$

Question. I am stuck to get the best concise formula ( I say the previous last identity, if it is neccesary by cases to get also the case $n-1$ is even) with the right notation. I don't know if I should be to use counting funtions to count the number of odd positive integers $\leq n-1$ (respectively even positive integers) or ceil and floor functions. Can you help to get this simple proposition, both cases, with a good notation Thanks in advance.

  • 1
    $\begingroup$ I think it would help you much, when you expand the $f(k)$ -terms into their simple explicite expressions $3k+1$ and $k/2$ respectively and separate then the additive terms in the sums into separate sum-expressions. Moreover: what is the benefit of expressing a natural number n as sum-of-ones as in your last sum? $\endgroup$ May 29, 2016 at 9:10
  • $\begingroup$ One of purpose was to obtain a simple proposition, as the viewpoint of an amateur, but the main was clarify how get good identities with its corresponding concise notations. There is no a mathematical reasoning in this post, we take as a soft question about notation. Very thanks much @GottfriedHelms $\endgroup$
    – user243301
    May 29, 2016 at 10:43
  • 1
    $\begingroup$ @user243301: Note, that in case of odd $n$ the index notation $k\in\{1,3,5,\ldots,n-1\}$ is not correct, since in this case $n-1$ is even. It is more convenient to write $1\leq k\leq n-1; k \text{ odd}$. A similar correction should be done in the index notation with $k$ even. $\endgroup$ May 29, 2016 at 16:39

1 Answer 1


At first some notes: We usually regard the closed formula \begin{align*} \omega(n)=\frac{3n^2+n}{2}\qquad\qquad\qquad\qquad\qquad n\geq 1\tag{1} \end{align*} as simpler than the summation formula \begin{align*} \omega(n)=\sum_{k=0}^{n-1}(3k+1)\qquad\qquad\qquad\qquad\quad n\geq 1\tag{2} \end{align*} So, if we want to represent $\omega(n)$ by the function \begin{align*} f(n)=\begin{cases} 3n+1\qquad & n \text{ odd}\\ \frac{n}{2}\qquad & n \text{ even} \end{cases}\qquad\qquad n\geq 1 \end{align*} we would rather try to avoid sums and start from (1). Another aspect is there is no best notation. An appropriate notation is usually application dependent and may vary according to different needs. But we can try to do some simplifications which are typically useful.

First variant: Expressing $f(n)$ by (2)

We start similar as OP did.

We obtain \begin{align*} \omega(n)&=\sum_{k=0}^{n-1}(3k+1)\\ &=\sum_{{k=0}\atop{k \text{ odd}}}^{n-1}(3k+1)+\sum_{{k=0}\atop{k \text{ even}}}^{n-1}(6\cdot\frac{k}{2}+1)\tag{3}\\ &=\sum_{{k=0}\atop{k \text{ odd}}}^{n-1}f(k)+\sum_{{k=0}\atop{k \text{ even}}}^{n-1}(6f(k)+1)\tag{4}\\ &=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}f(2k-1) +\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(6f(2k)+1)\tag{5}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}f(2k+1) +6\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}f(2k)+\left\lfloor\frac{n-1}{2}\right\rfloor+1\tag{6}\\ &=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\left(f(2k+1)+6f(2k)\right)\\ &\qquad\qquad+\left\lfloor\frac{n-1}{2}\right\rfloor+1-f(2\left\lfloor\frac{n-1}{2}\right\rfloor+1)\cdot\frac{1-(-1)^n}{2}\tag{7}\\ \end{align*}


  • In (3) we split the sum in odd and event parts of the index $k$

  • In (4) we use the function $f(n)$

  • In (5) we use the floor function to set the upper limit of $k$. For the odd part we use the substitution $k \rightarrow 2k-1$ and for the even part we use the substitution $k \rightarrow 2k$.

  • In (6) we shift the index of the left sum by one to start with $k=0$ and we extract the constant $1$ from the right sum and get $\left\lfloor\frac{n-1}{2}\right\rfloor+1$.

  • In (7) we can further reduce the number of summation symbols (if we like) by observing that \begin{align*} \left\lfloor\frac{n-1}{2}\right\rfloor=\begin{cases} \left\lfloor\frac{n}{2}\right\rfloor &\qquad n \text{ odd}\\ \left\lfloor\frac{n}{2}\right\rfloor-1 &\qquad n \text{ even}\\ \end{cases} \end{align*} So, we can use one summation symbol and a common upper limit $\left\lfloor\frac{n-1}{2}\right\rfloor$. Since in the odd case we have one more than in the even case we have to subtract the last element. We do this by subtracting $f(2\left\lfloor\frac{n-1}{2}\right\rfloor+1)$ and multiplying it with \begin{align*} \frac{1-(-1)^n}{2}=\begin{cases} 1\qquad& n\text{ odd}\\ 0\qquad& n\text{ even} \end{cases} \end{align*}

Second variant: Expressing $f(n)$ by (1)

Since it is usually more convenient to avoid summation symbols if possible at all we start now from (1). Here is one from many different possibilities.

We obtain \begin{align*} \omega(n)&=\frac{3n^2-n}{2}\\ &=(3n+1)\frac{n}{2}-n\\ &=\begin{cases} f(n)\frac{n}{2}-n\qquad & n\text{ odd}\\ (3n+1)f(n)-2f(n)\qquad& n\text{ even} \end{cases}\tag{8}\\ &=\begin{cases} f(n)\frac{n}{2}-n\qquad\qquad\qquad & n\text{ odd}\\ (3n-1)f(n)\qquad\qquad\qquad& n\text{ even} \end{cases}\\ &=(3n-1)f(n)\cdot\frac{1+(-1)^n}{2}+\frac{n}{2}\left(f(n)-2\right)\frac{1-(-1)^n}{2}\tag{9}\\ &=\frac{1}{4}\left(7n-2+(5n-2)(-1)^n\right)f(n)-\frac{n}{2}\left(1-(-1)^n\right)\tag{10} \end{align*}


  • In (8) we use $f(n)$ according to odd and even $n$

  • In (9) we put odd and even cases together using a technique as we did in (7)

  • In (10) we do some final rearrangement

  • $\begingroup$ Very thanks much, I 'm surprised. In the first variant you get lot of particular values (and I will remember for general partial series how define the upper limits) and in the second only one (you say that you find many different but this is so curious) Now your nice computations and approach can be read by users. $\endgroup$
    – user243301
    May 29, 2016 at 19:49
  • $\begingroup$ @user243301: You're welcome! Thanks for your nice comment. :-) $\endgroup$ May 29, 2016 at 19:52
  • 1
    $\begingroup$ Very thanks to you for your attention. $\endgroup$
    – user243301
    May 29, 2016 at 19:56

You must log in to answer this question.