Is it guaranteed that unhappy numbers will surely form a loop? Can it not form an infinite sequence of non-repeating numbers? What is the proof and mathematical intuition behind the guarantee that it always forms a loop?
Hello @Vivek_Gupta,
Thank you for sharing this query with us. To explain why unhappy numbers form a loop, we need to consider the range of possible values that f(n) can take for any positive integer n.
Statement: Given a positive integer n, let f(n) be the sum of the squares of its digits.
For example, if n = 19, then f(n) = 1^2 + 9^2 = 82.
For any positive integer n, f(n) is calculated by summing the squares of its digits. Since each digit is between 0 and 9, the maximum possible value of f(n) occurs when all the digits are 9, resulting in f(n) ≤ 9^2 + 9^2 + … + 9^2 = 81 multiplied by number of digits in n.
This means that f(n) is bounded by a constant multiple of the number of digits in n. In other words, f(n) cannot keep growing indefinitely as you apply the process; it must eventually become smaller.
Now, consider the sequence of values n, f(n), f(f(n)), f(f(f(n))), …. Since f(n) is bounded by a constant multiple of the number of digits in n, as we keep applying f to the previous result, the values in the sequence must eventually repeat.
Hope this answers your query. Please feel free to share any more feedback and suggestions, we’ll be happy to answer.
Happy learning!