Problem A: コラッツ予想

自然数から新たな自然数を作る次のような関数 f を考える。

• n が奇数のとき、f(n) = 3n + 1
• n が偶数のとき、f(n) = n / 2

1 以上の自然数 m に対して、f^t(m) = 1 となるような最小の非負整数 t を t(m) と書くことにする。m が与えられるので、t(m) を求めよ。

ただし、f^t(m) とは m に f を t 回適用したものを表す。

Input

入力は 1 行のみからなり、その行には 1 つの自然数 m が含まれる。

1 ≤ m ≤ 10⁹ であり、任意の非負整数 k に対して f^k(m) ≤ 10¹⁸ であることが保証されている。

Output

t(m) を 1 行に出力せよ。もし f^t(m) = 1 となるような t が存在しない場合、"Counterexample for Collatz conjecture!" と 1 行に出力せよ。

Sample Input

42

7

1

525858345

670617279

Output for the Sample Input

8

16

0

585

986

Sample Code in C

#include <stdio.h>

int main(void) {
    int m;
    long long n;
    int t;
    scanf("%d", &m);
    for(n = m, t = 0; n > 1; t++) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;
    }
    printf("%d\n", t);
    return 0;
}

Sample Code in C++

#include <iostream>

using namespace std;

int main() {
    int m;
    cin >> m;
    int t = 0;
    for(long long n = m; n > 1; t++) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;
    }
    cout << t << endl;
    return 0;
}

Sample Code in Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int t = 0;
        for(long n = m; n > 1; t++) {
            if (n % 2 == 0)
                n /= 2;
            else
                n = n * 3 + 1;
        }
        System.out.println(t);
    }
}