Weird Algorithm Solution

1 September 2021

Statement

( The original statement can be found here )
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

3→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

Input
The only input line contains an integer n.

Output
Print a line that contains all values of n during the algorithm.

Constraints
1 ≤ n ≤ \(10^6\)
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
3

Output :
3 10 5 16 8 4 2 1

Solution

Note that this is the first problem in the introductory section. It should be easy right? Yes and no. The problem at hand is also known as the Collatz conjecture, and states that given any positive integer \(N\) will converge to \(1\) if we apply the algorithm mentioned in the statement.
So far, no one really knows whether the conjecture holds for any given \(N\), so it remains an unsolved problem in mathematics.

Since Collatz first stated his conjecture, a lot of computation was made to try and disprove it. It is safe to suppose, then, that any integer in the interval \([1, 10^6]\) converges to \(1\) if we apply this \(weird \:algorithm\).

This is a so-called \(implementation\) problem, which means that the solution can be obtained by simply implementing the algorithm with no clever tricks or optimizations.

If \(N\) is even we divide it by \(2\), otherwise we multiply it by \(3\) and add \(1\). We repeat this while \(N\: \ne \: 1\).

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    while (n != 1) {
        cout << n << " ";
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
    }
    cout << 1;
}

The space complexity of this solution is \(O(1)\). It is harder to find a time complexity since we don't even know if it always converges to \(1\) for any given \(N\). All we know (and you can test this) is that up to \(10^6\), the largest possible sequence you can get has size \(525\).