Introduction to Computers : IDC101

A perhaps weaker question is whether this map eventually loops.

We can explain this better as follows. Let $x_0=n$ and define $x_{k+1} = x_{k}/2$ if $x_k$ is even and $x_{k+1}=3x_k+1$ if $x_k$ is odd. We can now ask if this map "loops". In other words, is there always a pair of natural numbers $p$ and $q>0$ so that $x_{p+q}=x_p$? It is not obvious that this question is the same as the Collatz sequence question.

In fact, we can define more general maps as follows. Fix a "base" $b$. Starting with $x_0=n$ we put $x_{k+1}=x_k/b$ if $x$ is divisible by $b$; other wise, let $r$ be the remainder of $x_k$ on division by $b$ and put $x_{k+1}=(b+1)*x_k+(b-r)$. Note that in the second case $x_{k+1}$ is divisible by $b$. So every two steps $x_{k+2}$ is at most about $(b+1)/b$ times $x_k$. We can ask the same question about this map.

Write a program to find "loops".