# Find Nth Term of Sum Of Digits

The series below is given:

$1, 1, 2, 4, 8, 16, 23, 28, 38, 49, \ldots$

I know that the $n^{\text{th}}$ term in the series is:

For $n>1$ , $t(n) = t(n-1) + \sum(t(n-1))$, where $\sum(n)$ is the sum of $n$'s digits.

I also found the series in oeis.org. What I am looking is a formula for finding nth term or even approximately estimating the $n^{\text{th}}$ term.

I want to implement this formula in a programming language, so I need a solution that does not need iteration or recursion.

As @barrycarter noted probably there is not any formula but I'm sure there is a faster algorithm than simple iteration. How can I find the $n^{\text{th}}$ term with minimum iterations?

I'm an engineer not Mathematician.

• I hope that you realize that programming the recursion is possible and probably easier, too – vrugtehagel Mar 15 '16 at 11:55
• It's definitely easier but no computer can calculate n(10 ^ 15) by iteration or recursion! @vrugtehagel – Seifolahi Mar 15 '16 at 11:58
• How does $t(1)$ become $1$ rather than $2$, then? – Henning Makholm Mar 15 '16 at 12:01
• @HenningMakholm, he wrote the numbers in a sequence where $s_n$ is the sum of the digits of all previous terms. Omitting the first $1$ will give you the sequence the OP is saying it is. – vrugtehagel Mar 15 '16 at 12:02
• If OEIS doesn't have a closed form, I'm guessing you'll be hard pressed to find one. – barrycarter Mar 15 '16 at 13:51

I would just compute terms up a ways until you get tired. Python makes it pretty easy because you can convert a number to a string, getting the base $10$ digits, then convert the digits back to numbers and add them up. Once you get reasonably large numbers, you can use the heuristic that the digits average $4.5$ to say it takes about $\frac {9 \cdot 10^{k-1}}{4.5k}$ terms to go from $k$ digits to $k+1$ digits, or from $10^{k-1}$ to $10^k$.

• Thanks, this should be the best solution. – Seifolahi Mar 15 '16 at 21:53

For an estimation, we can assume that the digits are roughly uniformly distributed, with a number $t_n$ contributing roughly $\log_{10}t_n$ digits with expected value $\frac92$ each. Then we have roughly

$$\Delta t=\frac92\log_{10}t=\frac9{2\log10}\log t\;.$$

As $\Delta p=\log p$ is the growth law of the primes, this yields roughly $t_n\approx p_{\lfloor9n/(2\log10)\rfloor}\approx p_{\lfloor1.954n\rfloor}$.

• Sorry but i didn't get your answer. is p[n] nth prime number? what is the relation between primes and sum of digits? – Seifolahi Mar 15 '16 at 22:07
• @Seifolahi: I didn't use the notation $p[n]$. I used $p_n$ for the $n$-th prime number, and $\lfloor x\rfloor$ for the floor of $x$, the greatest integer not greater than $x$. The relation between primes and the sum of digits is developed in the answer -- the estimate (very similar to Ross's) leads to a growth law for the $t_n$ that differs from that of the primes only by a constant factor; hence the $t_n$ grow like the primes up to that constant factor. – joriki Mar 16 '16 at 1:05
• Wow. aha. thanks. :-) – Seifolahi Mar 16 '16 at 2:14