#include <cassert>
#include <iostream>

// Discovering the growth of a recurrence
//
// We have considered recurrences in which the
// argument decreases by one:
//
//     T(n) = T(n - 1) + 1
//
// and:
//
//     T(n) = T(n - 1) + n.
//
// Now consider a very different recurrence:
//
//             /
//            (   1                 n = 1
//             )
//     T(n) = <
//             )
//            (   T(n/2) + 1       n > 1.
//             \
//
// Recall that n is an unsigned integer, and
// therefore n/2 uses integer division:
//
//     7/2 = 3
//     6/2 = 3
//
// Author the function T(n), asserting that:
//
//     n >= 1.
//
// Then, in main(), write a loop that calculates:
//
//     T(1), T(2), T(3), ...
//
// until you can determine a formula for T(n).
//
// Pay particular attention to powers of two.

// Function declarations
int main();

unsigned int T(
    unsigned int const n
);

// Function definitions
int main() {
    // Your implementation here.

    return 0;
}


// unsigned int T( ... )
//
// @param n
//     A positive integer.
//
// @returns
//     The value defined recursively by:
//
//         T(1) = 1
//
//     and:
//
//         T(n) = T(n/2) + 1
//
//     for n > 1.

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    // Your implementation here.

    return 1;
}














































// Hint
//
// Begin by printing:
//
//     T(1)
//     T(2)
//     T(3)
//     ...
//
// For example:
//
//     for ( unsigned int k{ 1 };
//           k <= 20;
//           ++k ) {
//         std::cout << "T(" << k << ") = "
//                   << T( k )
//                   << std::endl;
//     }
//
// What pattern do you observe?
//
// In particular, examine:
//
//     T(1)
//     T(2)
//     T(4)
//     T(8)
//     T(16)
//
// What do these arguments have in common?














































// Solution

/*
int main() {
    for ( unsigned int k{ 1 };
          k <= 20;
          ++k ) {
        std::cout << "T(" << k << ") = "
                  << T( k )
                  << std::endl;
    }

    return 0;
}

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    if ( n == 1 ) {
        return 1;
    } else {
        return T( n/2 ) + 1;
    }
}
*/














































// What is the pattern?
//
// Here is the output:
//
//     T(1)  = 1
//     T(2)  = 2
//     T(3)  = 2
//     T(4)  = 3
//     T(5)  = 3
//     T(6)  = 3
//     T(7)  = 3
//     T(8)  = 4
//     T(9)  = 4
//     T(10) = 4
//     T(11) = 4
//     T(12) = 4
//     T(13) = 4
//     T(14) = 4
//     T(15) = 4
//     T(16) = 5
//     T(17) = 5
//     T(18) = 5
//     T(19) = 5
//     T(20) = 5
//
//
// Notice where the value changes:
//
//     T(1)  = 1
//
//     T(2)  = 2
//
//     T(4)  = 3
//
//     T(8)  = 4
//
//     T(16) = 5.
//
// We can therefore predict:
//
//     T(32)  = 6
//
//     T(64)  = 7
//
//     T(128) = 8.
//
//
//
// Powers of two
//
// Recall:
//
//     2^0 = 1
//     2^1 = 2
//     2^2 = 4
//     2^3 = 8
//     2^4 = 16
//     2^5 = 32
//
// Therefore:
//
//     log_2(1)  = 0
//     log_2(2)  = 1
//     log_2(4)  = 2
//     log_2(8)  = 3
//     log_2(16) = 4.
//
// Compare this with:
//
//     T(1)  = 1
//     T(2)  = 2
//     T(4)  = 3
//     T(8)  = 4
//     T(16) = 5.
//
// Thus, for powers of two:
//
//     T(n) = log_2(n) + 1.
//
//
//
// What about numbers that are not powers of two?
//
// Consider:
//
//     n = 13.
//
// The recursive calls are:
//
//     T(13)
//        |
//        v
//     T(6)
//        |
//        v
//     T(3)
//        |
//        v
//     T(1).
//
// Therefore:
//
//     T(13) = 4.
//
// But:
//
//     log_2(13)
//
// is approximately:
//
//     3.700.
//
// Taking the floor:
//
//     floor(log_2(13)) = 3.
//
// Thus:
//
//     T(13)
//       = floor(log_2(13)) + 1
//
//       = 4.
//
//
//
// Consider another example:
//
//     n = 7.
//
// The recursive calls are:
//
//     7
//     |
//     v
//     3
//     |
//     v
//     1.
//
// Therefore:
//
//     T(7) = 3.
//
// Also:
//
//     log_2(7) is approximately 2.807,
//
// so:
//
//     floor(log_2(7)) + 1
//
//       = 2 + 1
//
//       = 3.
//
//
//
// Thus, the exact formula is:
//
//     T(n) = floor(log_2(n)) + 1.
//
//
//
// Why does the floor appear?
//
// Recall that we are using integer division.
//
// For example:
//
//     15/2 = 7
//      7/2 = 3
//      3/2 = 1.
//
// The fractional parts are discarded.
//
// Consequently, all values from one power of two
// up to just before the next power of two have the
// same value of T(n):
//
//     n                    T(n)
//
//     1                      1
//
//     2 through 3            2
//
//     4 through 7            3
//
//     8 through 15           4
//
//     16 through 31          5
//
//     32 through 63          6
//
//     64 through 127         7
//
//
// More generally:
//
//     if
//
//         2^k <= n < 2^(k + 1),
//
//     then:
//
//         T(n) = k + 1.
//
// But:
//
//         k = floor(log_2(n)).
//
// Therefore:
//
//         T(n) = floor(log_2(n)) + 1.
//
//
//
// How quickly does this grow?
//
// We have found the exact formula:
//
//     T(n) = floor(log_2(n)) + 1.
//
// For asymptotic analysis, the floor and the
// additional 1 do not affect the growth.
//
// Therefore:
//
//     T(n) = Theta(log(n)).
//
// The base of the logarithm is also irrelevant for
// asymptotic analysis.
//
// For example:
//
//     log_2(n)
//
// and:
//
//     log_10(n)
//
// differ only by a constant factor.
//
// Thus, we usually simply write:
//
//     Theta(log(n)).
//
//
//
// Why is logarithmic growth so important?
//
// Consider what happens when n doubles.
//
// Suppose:
//
//     n = 1024.
//
// Since:
//
//     1024 = 2^10,
//
// we have:
//
//     T(1024) = 11.
//
// Now double the input:
//
//     n = 2048 = 2^11.
//
// Then:
//
//     T(2048) = 12.
//
// Doubling the size of the problem adds only ONE
// additional level of work.
//
//
//
// Consider much larger values.
//
//     n                 floor(log_2(n)) + 1
//
//     1                              1
//
//     10                             4
//
//     100                            7
//
//     1000                          10
//
//     1000000                       20
//
//     1000000000                    30
//
//
// An input can become enormous while the number of
// repeated halvings remains surprisingly small.
//
//
//
// Compare our recurrences
//
// So far:
//
//     T(n) = T(n - 1) + 1
//
//         Theta(n)
//
//
//
//     T(n) = T(n - 1) + n
//
//         Theta(n^2)
//
//
//
//     T(n) = n*T(n - 1) + n
//
//         Theta(n!)
//
//
//
//     T(n) = T(n/2) + 1
//
//         Theta(log(n))
//
//
// Notice something interesting.
//
// The last recurrence performs one additional unit
// of work at each step, just like:
//
//     T(n) = T(n - 1) + 1.
//
// The enormous difference comes from the size of
// the next problem.
//
//
//
// Subtracting one:
//
//     n
//     n - 1
//     n - 2
//     n - 3
//     ...
//     1
//
// requires approximately n steps.
//
//
//
// Dividing by two:
//
//     n
//     n/2
//     n/4
//     n/8
//     ...
//     1
//
// requires approximately log_2(n) steps.
//
// This is the source of logarithmic runtime in many
// algorithms.
//
//
//
// Where does this occur?
//
// Recall binary search.
//
// Suppose we are searching a sorted array containing:
//
//     501
//
// entries.
//
// We examine the middle entry:
//
//     index 250.
//
// If that is not the value we seek, we do NOT need
// to continue searching all 500 remaining entries.
//
// Because the array is sorted, we can determine
// which half could contain the value.
//
// Thus, the next search contains at most:
//
//     250
//
// entries.
//
// After examining its middle entry, the next search
// contains at most:
//
//     125
//
// entries.
//
// Then approximately:
//
//     62
//
// then:
//
//     31
//
// then:
//
//     15
//
// then:
//
//     7
//
// then:
//
//     3
//
// then:
//
//     1.
//
//
//
// Visually:
//
//     501
//      |
//      v
//     250
//      |
//      v
//     125
//      |
//      v
//      62
//      |
//      v
//      31
//      |
//      v
//      15
//      |
//      v
//       7
//      |
//      v
//       3
//      |
//      v
//       1
//
//
// Each unsuccessful comparison eliminates
// approximately HALF of the remaining possibilities.
//
// That is why binary search has logarithmic runtime.
//
//
//
// Another interpretation: binary digits
//
// There is another interesting interpretation of:
//
//     floor(log_2(n)) + 1.
//
// This is exactly the number of binary digits
// required to represent a positive integer n.
//
// For example:
//
//     decimal        binary       digits
//
//        1              1           1
//
//        2             10           2
//
//        3             11           2
//
//        4            100           3
//
//        7            111           3
//
//        8           1000           4
//
//       15           1111           4
//
//       16          10000           5
//
//
// Compare:
//
//     T(1)  = 1
//     T(2)  = 2
//     T(3)  = 2
//     T(4)  = 3
//     T(7)  = 3
//     T(8)  = 4
//     T(15) = 4
//     T(16) = 5.
//
// Thus:
//
//     T(n)
//
// is also the number of bits required to represent
// the positive integer n.
//
// This is not a coincidence.
//
// Repeatedly dividing an integer by two is closely
// connected with its binary representation.
//
//
//
// A useful question to ask
//
// When examining a recursive algorithm, do not look
// only at:
//
//     How much work occurs during each call?
//
// Also ask:
//
//     How much smaller is the recursive problem?
//
//
// Compare:
//
//     T(n - 1)
//
// with:
//
//     T(n/2).
//
// That apparently small difference can change a
// linear algorithm into a logarithmic algorithm.
//
//
//
// Questions:
//
// 1. What values do you obtain for T(1) through
//    T(20)?
//
// 2. At which values of n does T(n) increase?
//
// 3. What is special about these values?
//
// 4. Why does:
//
//        T(2^k) = k + 1?
//
// 5. Why do all integers from 8 through 15 have
//    the same value of T(n)?
//
// 6. Why does the exact formula require the floor
//    function?
//
// 7. What is the exact formula for T(n)?
//
// 8. Why is:
//
//        floor(log_2(n)) + 1
//
//    described asymptotically as:
//
//        Theta(log(n))?
//
// 9. What happens to T(n) when n is doubled?
//
// 10. How does this recurrence model binary search?
//
// 11. Why is dividing the problem size by two so
//     much more powerful than subtracting one?
//
// 12. What is the relationship between T(n) and the
//     number of bits required to represent n?
//
//
//
// The progression now includes an especially
// important contrast:
//
//     T(n) = T(n - 1) + 1
//
//              Theta(n)
//
//                 versus
//
//     T(n) = T(n/2) + 1
//
//              Theta(log(n)).
//
//
// In the first case, we make progress by:
//
//     subtracting one.
//
// In the second case, we make progress by:
//
//     dividing by two.
//
//
// This idea:
//
//     solve a problem by repeatedly reducing its
//     size by a constant factor
//
// appears throughout computer science.
//
// Binary search is one example.
//
// Soon, we will see algorithms that divide a problem
// into multiple smaller problems.
//
// That will lead us to another important family of
// recursive algorithms:
//
//     divide-and-conquer.