Time complexity of calculating the final digit sum of a number

Question

I want to calculate the time complexity of calculating the "final" digit sum of a number n: sum of the digits until I get A single digit number.

I know that in the first iteration an algorithm will perform O(log n) actions, in the second iteration it will be O(log log n) and so on, up until log(log(...(log(n))...)) < 10. Thus the number of iteration is O(log* n), where log* n is the log-star value of n.

Is there a closed form for this sum?

Answer 1

This sum works out to ?(log n). One way to see this is to notice that log n < n / 2 for all but tiny values of n, so we have that

log n + log log n + log log log n + …

? log n + (log n) / 2 + (log n) / 4 + (log n) / 8 + …

? log n (1 + 1/2 + 1/4 + 1/8 + …)

= 2 log n

= O(log n).

To see that the sum is ?(log n), note that the first term itself is log n, so the sum is at least log n.