Collatz Conjecture: An Odd Number Of Steps

Computer Science Level 4

The Collatz Conjecture is a famous problem in number theory. It corresponds to the following function:

\[ f(n) = \begin{cases} \frac{n}{2} & \text{ if } n \equiv 0 \pmod{2} \\ 3n+1 & \text{ if } n \equiv 1 \pmod{2} \\ \end{cases} \]

The conjecture states that for every \(n>1\) there exists a \(k\) such that \(f^k(n)=1\). In other words, given an \(n\) to start with, after iterating this function over and over again we will eventually get \(1\), no matter the starting number.

How many \(1<n<10^7\) are there such that \(k\) is odd?

Note: We are looking for \(k\) to be minimal. There are technically infinitely many \(k\) because \(f(1)=4\), \(f(4)=2\) and \(f(2)=1\).

Clarification: \(f^k(n) = \underbrace{ f(f(f(\ldots (f(x))\ldots)}_{k \text{ number of times}} \).


Problem Loading...

Note Loading...

Set Loading...