How to solve recurrences with transcendental terms? Problem:


  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 =&gt; 19 =&gt; 10 =&gt; 1 =&gt; 289$ is a magic number
  but, $20 =&gt; 2 =&gt;$ 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?
The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant.

(Confusingly, in information theory the same notation is used for the function $\log + \log\log + \log\log\log + \cdots$.)