P0017. Siracusa attacks again P14410


Statement
 

pdf   zip

thehtml

Being n a natural number greater than zero. Consider this algorithm:

  • If n = 1, stop.
  • If n is an even number, divide it by 2.
  • If n is an odd number, multiply it by 3 and add 1.

For instance, starting with 6 we obtain 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

The conjecture 3n + 1 says that starting with any natural number n > 0, it always arrives to 1. Although it has not still been proved, using computers we know that is true for numbers n ≤ 4035225266123964416.

Your task is to write a program that reads two natural numbers m and p and prints which natural numbers between 1 and m arrive to 1 in p or more steps. It must print also which is the greatest number contained in their steps.

Your program must implement and use the procedure

void converge(int n, int& k, int& far);

that, given an integer strictly positive |n|, stores at the parameter |k| the number of steps that needs |n| to arrive to 1, and at the parameter |far| the greatest number seen in the process. For instance, |converge(6, k, far);| stores an 8 at |k| and a 16 at |far|. Similarly, |converge(4, k, far);| stores a 2 at |k| and a 4 at |far|, and |converge(1, k, far);| stores a 0 at |k| and an 1 at |far|.

Input

The input is two natural numbers m and p, with 1 ≤ m ≤ 50000.

Output

Your program must print all the numbers between 1 and m that arrive to 1 in p or more steps, one per line. Besides, print also the greatest produced number, following the format of the instances.

Public test cases
  • Input

    6 7
    

    Output

    3
    6
    The greatest reached number is 16.
    
  • Input

    16 0
    

    Output

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    The greatest reached number is 160.
    
  • Input

    1 0
    

    Output

    1
    The greatest reached number is 1.
    
  • Input

    2 1
    

    Output

    2
    The greatest reached number is 2.
    
  • Input

    30 200
    

    Output

    The greatest reached number is 9232.
    
  • Input

    50000 323
    

    Output

    35655
    The greatest reached number is 121012864.
    
  • Input

    447 140
    

    Output

    327
    The greatest reached number is 39364.
    
  • Information
    Author
    Professorat de P1
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Haskell