I wish to find the count of sequences of length n consisting of exactly k distinct elements. Can't think of any approach to this.

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.

I tried to understand the solutions of few people but couldn't exactly get it. Besides, couldn't find the editorial for the problem. It'd be really great if someone could help me out. Problem Link

I have been trying to solve the problem CPATTERN from SPOJ. Link: https://www.spoj.com/problems/CPATTERN/.

I store the input sequence in text[] and subgroup sequence in pattern[]. Using text[], I created another array diffText[] that stores:

diffText[i] = 1 if text[i - 1] > text[i],
diffText[i] = 0 if text[i - 1] == text[i],
diffText[i] = -1 if text[i - 1] < text[i]

In the same way, I construct the array diffPattern[] for pattern[]. Then I use KMP to search for the diffPattern[] in diffText[]. It shows wrong answer. Is this incorrect approach? Please help.