# 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 => 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?

• Note that it's not $\lg n$ but $\lceil \lg n\rceil$. If you don't restrict $n$ to be an integer, $T(n)=\infty$ for any $n$ that's not a power of $2$. – David Richerby Feb 1 '17 at 15:29
• This depends on the computational model you're using, but in most contexts, assuming numbers can grow unbounded as you imply, would be more reasonable to take the sum of digits to be a $\Theta(n)$ rather than a $\Theta(1)$ operation. – quicksort Feb 1 '17 at 15:41

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$.)
• The formula is $\log^* n$ = number of applications of $\log$ which reduce $n$ to below 1 (say). – Yuval Filmus Feb 1 '17 at 15:15
• @svineet, in theory or in practice? In theory, you don't really need a formula, any more than you need a formula for $\log$ itself. In practice, you can use this one: $\log^* 1 = 0$; $\log^* 2 = 1$; if $2 < n \leq 4$ then $\log^* n = 2$; if $4 < n \leq 16$, then $\log^* n = 3$; if $16 < n \leq 65536$, then $\log^* n = 4$; if $65536 < n \leq 2^{65536}$, then $\log^* n = 5$; otherwise, there's no way that you can even compute the input before the heat death of the universe, so you can use whatever value you want. :-) – wchargin Feb 1 '17 at 21:03