cycle length of n

consider the following algorithm :
    if n = 1 then STOP

    if n is odd then  tex2html_wrap_inline44 

else tex2html_wrap_inline46
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value.
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

Sample Input (1<n<1000000)

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

Comments

  1. sir plz tell the approach
    I can't think of anything except brute-force.
    plzz help ??

    ReplyDelete
  2. @above if you will see the pattern you will find that you don't need to recompute values for all n.
    please see the code below

    #include
    #include

    using namespace std;

    typedef unsigned int uint;
    typedef unsigned short ushort;
    #define SIZE 1000001
    static unsigned short table[SIZE];
    ushort print(uint n)
    {
    if(n < SIZE && table[n])
    return table[n];
    if(n & 1)
    {
    if( n < SIZE)
    {
    table[n] = 2 + print( (3*n+1) >> 1 );
    return table[n];
    }
    else
    {
    return 2 + print( (3*n+1) >> 1 );
    }
    }
    else
    {
    if( n < SIZE)
    {
    table[n] = 1 + print( n >> 1 );
    return table[n];
    }
    else
    {
    return 1 + print( n >> 1 );
    }
    }
    }


    int main()
    {
    //read and write inputs and outputs to file
    freopen("INPUT","r",stdin);
    freopen("OUTPUT","w",stdout);

    uint x,y,i;
    ushort max_count=0,count=0;
    table[1] = 1;

    while(cin>>x>>y)
    {
    max_count = 0;
    if(x < y)
    {
    for(i=x;i<=y;i++)
    {
    count = print(i);
    if (count > max_count)
    max_count = count;
    }
    }
    else
    {
    for(i=y;i<=x;i++)
    {
    count = print(i);
    if (count > max_count)
    max_count = count;
    }
    }
    cout<<x<<" "<<y<<" "<<max_count<<endl;
    }
    return 0;
    }

    ReplyDelete

Post a Comment

Popular posts from this blog