Collatz pseudo-sequences (1) P91173


Statement
 

pdf   zip

html

Let us define sequences similar to those of Collatz with two parameters x and y. Given a number n, the algorithm to get the next number is:

  • if n is even, we move to n/2 + x;
  • otherwise, we move to 3n + y.

The standard Collatz sequence corresponds to x = 0 and y = 1.

Given x, y and a starting number n, compute the length of the cycle reached by applying the above algorithm. For example, if x = 1, y = 5 and n = 8, then the defined sequence is 8, 5, 20, 11, 38, 20, 11, 38, … so the cycle has length 3.

Since numbers can become very large, and we have no mathematical guarantee that we will reach a cycle, we will stop if at some point the sequence reaches a number greater than 106.

Input

Input consists of several cases, each with three natural numbers x, y and n. Assume that both x and y do not exceed 1000, that y is odd (for the sequence to have some interest), and that the initial n is not larger than 106.

Output

For every case, print the length of the cycle, or the first number that strictly exceeds 106.

Public test cases
  • Input

    1 5 8
    0 5 0
    10 11 3
    7 3 6
    1 999 1000000
    433 805 215476
    0 1 333333
    

    Output

    3
    1
    1
    35
    1501002
    490
    3
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Java Python
    User solutions
    C++