I want to generate the nth term of the sequence 1,3,8,22,60 ,164 in Order(1) or order of (nlogn)

by

You can calculate values of sequences with a linear recurrence relation in O(log n) steps using the matrix method. In this case, the recurrence matrix is

2 2
1 0

The n-th term of the sequence is then obtained by multiplying the n-th power of that matrix with the two initial values.

The recurrence immediately translates to

|x_n    |   |2 2|   |x_(n-1)|
|x_(n-1)| = |1 0| * |x_(n-2)|

thus

|x_(n+1)|   |2 2|^n   |x_1|
|x_n    | = |1 0|   * |x_0|.

In this case the initial conditions give, x_1 = 1, x_2 = 3 lead to x_0 = 0.5, a non-integer value, hence the calculation should rather be

|x_(n+1)|   |2 2|^(n-1)   |x_2|
|x_n    | = |1 0|       * |x_1|.

To get the value modulo some number, calculate the power of the matrix modulo that number.

More Related Contents:

  1. Sequence-zip function for c++11?
  2. Modular Exponentiation for high numbers in C++
  3. Avoid memory leaks in C++ Pointers [closed]
  4. How can I pad an int with leading zeros when using cout
  5. Why does C++11’s lambda require “mutable” keyword for capture-by-value, by default?
  6. How do I concatenate multiple C++ strings on one line?
  7. Why is initialization of a new variable by itself valid? [duplicate]
  8. Why is the destructor of the class called twice?
  9. Template partial ordering – why does partial deduction succeed here
  10. Why are there digraphs in C and C++?
  11. Portability of binary serialization of double/float type in C++
  12. Why is this code trying to call the copy constructor?
  13. Bigint (bigbit) library
  14. How do you convert CString and std::string std::wstring to each other?
  15. When should I use typedef in C++?
  16. How to use SQLite in a multi-threaded application?
  17. How to make G++ preprocessor output a newline in a macro?
  18. Why are empty expressions legal in C/C++?
  19. C++ method only visible when object cast to base class?
  20. What are some better ways to avoid the do-while(0); hack in C++?
  21. Does delete work with pointers to base class?
  22. Program can’t find libgcc_s_dw2-1.dll [duplicate]
  23. Converting bool to text in C++
  24. How can i estimate memory usage of std::map?
  25. How can I use std::imbue to set the locale for std::wcout?
  26. Fastest way to Convert String to Binary?
  27. When a float variable goes out of the float limits, what happens?
  28. OpenMP: What is the benefit of nesting parallelizations?
  29. Deleted Function in std::pair when using a unique_ptr inside a map
  30. Getting a list of user profiles on a computer in C++ Win32

Leave a Comment