A number is said to be a magic number, if the sum of its digits, taken again and again till it becomes a single digit number, is 1.
Example: $289 => 19 => 10 => 1 => 289$ is a magic number
but, $20 => 2 =>$ not a magic number.
So the simple algorithm is to keep doing the digit sums till we reach a single digit number. I tried to calculate the time complexity of this algorithm, and came up with the following recurrence:
$$T(n) = T(lg\ n) + O(1)$$
Let us say we have a number $N$ to test for magic number. The number of digits in this number is $O(lg\ n)$, so the sum of its digits is at most $9*lg\ n$ which is $O(lg\ n)$. So we have one smaller subproblem of size $lg\ n$ and some constant work to return data.
How do I solve this recurrence? The answer would be, ostensibly, the number of times I have to take $log $ of a number to get to 1. Is there a direct equation for this?