0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I hope that you realize that programming the recursion is possible and probably easier, too $\endgroup$ – vrugtehagel Mar 15 '16 at 11:55
  • $\begingroup$ It's definitely easier but no computer can calculate n(10 ^ 15) by iteration or recursion! @vrugtehagel $\endgroup$ – Seifolahi Mar 15 '16 at 11:58
  • $\begingroup$ How does $t(1)$ become $1$ rather than $2$, then? $\endgroup$ – Henning Makholm Mar 15 '16 at 12:01
  • $\begingroup$ @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. $\endgroup$ – vrugtehagel Mar 15 '16 at 12:02
  • 1
    $\begingroup$ If OEIS doesn't have a closed form, I'm guessing you'll be hard pressed to find one. $\endgroup$ – barrycarter Mar 15 '16 at 13:51
3
$\begingroup$

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$.

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

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}$.

$\endgroup$
  • $\begingroup$ Sorry but i didn't get your answer. is p[n] nth prime number? what is the relation between primes and sum of digits? $\endgroup$ – Seifolahi Mar 15 '16 at 22:07
  • 1
    $\begingroup$ @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. $\endgroup$ – joriki Mar 16 '16 at 1:05
  • $\begingroup$ Wow. aha. thanks. :-) $\endgroup$ – Seifolahi Mar 16 '16 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.