Блог пользователя saurabhs1206

Автор saurabhs1206, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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