saurabhs1206's blog

By saurabhs1206, history, 4 years ago, In English

Link to the problem

Since the constraints of this problem are lenient enough to allow brute force i.e. compute the power of each integer separately without any memoization for all integers in the range l to r, I could pass the test cases easily. But I still wasn't able to find any formal or even intuitive proof that the power of a certain number x would definitely be finite. Please help me towards an intuitive or a mathematical proof that a certain number would definitely reach 1, and if it reaches then what is the approximate upper bound on the number of steps that would be taken for all integers in the range 1 — 10^5.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

This problem involves the famous Collatz Conjecture which don't have concrete time complexity yet, I guess.