0

I've been playing with a particular function $$Q(n) = \sum_{i=1}^n i\cdot i!$$

in C++, and I'm trying to see if it is possible to find the following in an elegant way:

1) Is it possible to rewrite the above function in such a way that it admits a closed form solution?

2) Are there any number theoretic methods that can tell me how many digits are in $Q(n)$ if it written in a particular base $B$?

$\textbf{My attempt:}$ 1) I have a burgeoning suspection that $Q(n) = (n+1)!-1$ but I want to know if any other from is admissable without the factorial, since the time complexity of a factorial function is usually not cheap.

2) I'm completely stumped. I know of methods that would tell me what the last digit would be in base 10 but none that tell me what the total number of digits in a particular base would be

Jyrki Lahtonen
  • 133,153
Millardo Peacecraft
  • 1,490
  • 1
  • 12
  • 26
  • 1
    The value of the series is \begin{align} F_{n} = \sum_{k=0}^{n} k \cdot k! = (n+1)! -1 \end{align}. It also follows the difference equation $F_{n+1} = (n+2) F_{n} + n + 1$ – Leucippus Oct 05 '14 at 05:44
  • To know the number of digits in base $B$ is equivalent to knowing the approximate value of $\log_{B} Q(n)$. See Stirling's approximation. – Erick Wong Oct 05 '14 at 06:07

2 Answers2

2

Hint

Just rewrite

$$Q(n) = \sum_{i=1}^n i\cdot i!=\sum_{i=1}^n (i+1-1)\cdot i!=\sum_{i=1}^n (i+1)!-\sum_{i=1}^n i!$$ and remark how they telescope. So $$Q(n)=(n+1)!-1$$

As said in comments, there are very good approximations; in 1988, Srinivasa Ramanujan gave $$\log(n!)\approx -n+n \log (n)+\frac{1}{6} \log (n (4 n (2 n+1)+1))+\frac{\log (\pi )}{2}$$ which is simple and extremely accurate.

For example, using $n=100$, the approximation gives $9.332621538\times 10^{157}$ while the exact value is $9.332621544\times 10^{157}$.

Claude Leibovici
  • 260,315
0

Since $k\times k! = (k+1)!-k!$, we have $Q(n) = (n+1)!-n!+n!-(n-1)!+...-1!=(n+1)!-1$

wilsonw
  • 1,016