# 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}}$$.

×