32
$\begingroup$

This is related to Collatz sequence, which is that $$C(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

Is it possible to describe the Collatz function in one formula? (without modular conditions)

$\endgroup$
  • 22
    $\begingroup$ One thing to be noted is that even though you can, it doesn't mean you should. Either you'll introduce analytical ideas (e.g. using cosine) or you'll hide the modular condition behind something equivalent (e.g. with the fractional part function or a valuation) - neither of which really deepens our understanding of the function. $\endgroup$ – Milo Brandt Sep 24 '15 at 17:33
  • 1
    $\begingroup$ The 2-adic valuation isn't modular, it's not even periodic...keep in mind primes can be written in terms of modular function sums, so of course they are both related. $\endgroup$ – Zach466920 Sep 24 '15 at 18:03
60
$\begingroup$

$$f(n)=\frac74n+\frac12+(-1)^{n+1} \left(\frac54n+\frac12\right)$$

$\endgroup$
  • 13
    $\begingroup$ Simple and straight to the point. Excellent! Off course, there it is (-1)^n as the 'hidden modulo 2' that @MiloBrandt pointed. And the original expression is still much clearer, but this one is a great one liner $\endgroup$ – Rolazaro Azeveires Sep 24 '15 at 22:34
  • 2
    $\begingroup$ YMMV but a little clearer for me: f(n) = (7n + 2 - (-1)^n (5n + 2)) / 4 $\endgroup$ – Raidri Sep 25 '15 at 14:41
30
$\begingroup$

$$C(n)=\frac{n}{2}\cos^2\left(\frac{\pi n}{2}\right)+(3n+1) \sin^2\left(\frac{\pi n}{2}\right)$$

Continuous extension . M. Chamberland $(1996)$ observed that the entire function defined by $$f(x)=x+\frac{1}{4}-\frac{2x+1}{4} \cos (\pi x)$$ interpolates the $3n+1$ function: $$T(n)=\begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ (3n+1)/2 & \text{if } n\equiv 1 \pmod{2} \end{cases}$$ and $T(n)=f(n)$ for $n\in \mathbb{N}$. This allows him to try to apply methods of one-dimensional discrete dynamical systems to $3n+1$ iterations.

Chamberland, M., A Continuous Extension of the 3x + 1 Problem to the Real Line, Dynamics of Continuous, Discrete and Impulsive Systems 2 A996), 495-509.

$\endgroup$
10
$\begingroup$

If you are searching for any way to write this in terms of elementary functions:

$$C(n)=n \cdot \left(\frac{1}{2}+\left\lfloor \frac{n}{2} \right\rfloor-\frac{n}{2}\right)+2(3n+1) \cdot \left(\frac{n}{2}-\left\lfloor \frac{n}{2} \right\rfloor\right)$$ where $\lfloor x \rfloor$ is the floor function (that is, the largest integer less than or equal to $x$).

But probably this is not the thing you were searching for...

Nonetheless, I'm quite sure that all possible such formulas involve a hidden "modulo condition" so it is probably the best way to write this in a more direct way as it's done usually...

$\endgroup$
  • 8
    $\begingroup$ The floor function isn't really considered elementary... $\endgroup$ – Zach466920 Sep 24 '15 at 17:33
  • 2
    $\begingroup$ @Zach466920: Well, when I wrote "elementary" I had not in mind to refer to any precisely defined concept of "elementary" functions but rather use a synonym of "not too complicated". But technically, you are right of course.. $\endgroup$ – Tintarn Sep 24 '15 at 17:39
  • $\begingroup$ As you said, this wasn't what I was looking for, but still helps anyways! $\endgroup$ – Bingkongmaster Sep 25 '15 at 2:35
9
$\begingroup$

Yes. In fact, in some ways, it's easier to just use a function that gives the odd numbers in the Collatz sequence. See my question for more.

$$(1) \quad o_{n+1}={{3 \cdot o_n+1} \over {2^{v_2(3 \cdot o_n+1)}}}$$

Where $v_2(3 \cdot o_n+1)$ is the 2-adic valuation. $o_n$ is the nth odd number in the Collatz sequence.

You also have the Collatz Fractal iteration, given by,

$$(2) \quad z_{n+1}={1 \over 4} \cdot (2+7 \cdot z_n-(2+5 \cdot z_n) \cdot \cos(\pi \cdot z_n))$$

which extends the collatz function to the complex plane. I think the point to remember is that the way the Collatz function is written definitely influences how it's studied. This allows for new insights about what common threads run parallel to all the methods. We think that thread is convergence to one, but who really knows yet?

$\endgroup$
  • 4
    $\begingroup$ I've gotten to like the following notation even more. Instead of looking at the odd integers $o$ one can look at their iterates $w=3o+1$ which are all numbers $w = 6k+4$ . Then we can write the one-liner $$ w_{k+1} = 3{w_k \over 2^{v(w_k)}} + 1$$ where the number $w=4$ denotes the known cycle. (Just aside, one more feature of this substitution is, that the number $- \frac13$ (which plays the role of a limit in a collatz-tree including the rationals) is mapped to the zero) $\endgroup$ – Gottfried Helms Sep 25 '15 at 7:39
  • $\begingroup$ @GottfriedHelms Can you clarify what you mean by "the role of a limit in a collatz-tree including the rationals"? $\endgroup$ – user76284 Feb 9 '18 at 5:10
  • $\begingroup$ @user76284: consider the set of all (odd) numbers which decrease to $1$ by one "compressed" (or "Syracuse")-step: these are $a_k=\{1,5,21,85,...\}$ . The sequence of entries has a simple progression; $a_{k+1}=4a_k+1$. If we complete that set to the left side we need to compute $a_{k-1}=(a_k-1)/4$. We get now rational numbers which might be transformed by the "Syracuse"-step to $1$ as well. Letting $k \to - \infty$ the limit is $-1/3$. Similarly this can be done with the set of numbers $a_k=\{3,13,53,...\}$ which transform to $5$ by one "Syracuse"-step. And so on... $\endgroup$ – Gottfried Helms Feb 9 '18 at 7:06
8
$\begingroup$

You can always do this $$ C(n) = (n \bmod 2)(3n+1) + (1-(n \bmod 2))(n/2) $$

$\endgroup$
4
$\begingroup$

You can use floor/ceiling maps. If you let $f(n) = 2*(n/2 - floor (n/2 ))$ then this function is the indicator of whether $n$ is odd or even, (i.e. $f(n) = 1$ if $n$ is odd and $f(n) = 0$ if $n$ is even), and so then you can define $C(n) = f(n)*(3n + 1) + (1 - f(n))*(n/2)$.

However, note that looking at the floor of $n/2$ and using this in your formula by comparing to $n/2$ is basically the same as having different "cases" for the value of the function depending on whether $n$ is odd or even. I don't think there's any better way around it though, if you want one formula.

$\endgroup$
-1
$\begingroup$

There are good answers here already but this is also a good way of looking at the Collatz problem in a single formula.

Let $\Bbb N/\langle2\rangle$ be the equivalence classes of positive integers having the same odd factors, i.e. it has the equivalence class $3\cdot\langle2\rangle=\{3,6,12,24,\ldots\}$ as an element.

Then you have $f:\Bbb N/\langle2\rangle\to\Bbb N/\langle2\rangle$

$f(x)=3x+2^{\nu_2(x)}$

where $2^{\nu_2(x)}$ is the highest power of $2$ that divides $x$.

Then the Collatz conjecture states that $f$ acts transitively, or equivalently that its orbit converges to $\langle2\rangle$ for all inputs.

$\endgroup$

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.