2
$\begingroup$

I'm sorry this looks a lot like a do my homework question, but it's something I came across at work and thought I'd ask you guys (and my math is rusty). In Pascal it looks like this

l:=n; for i:=1 to n do inc(l,(i*((i div 2)+1)) div 2);

If I have a go at putting it in formula I guess it looks like this:

$l=n+\sum\limits_{i=1}^n\frac{i(\frac{i}{2}+1)}{2}$

Is there a way to calculate it in a single Pascal expression without iteration?

Caveat here is ofcourse that div rounds the result down towards zero, but when using a positive $n$ the result should be on or closely above the value I'm after, and in context it's needed as a guard value to keep an eye on the maximum number of iterations of another part of the program, so perhaps it would be permissable to ignore the rounding.

2 Answers 2

3

Ignoring the rounding of each quotient, what you have is $\begin{align}&n+\sum_{i=1}^n \frac{i(\frac i2+1)}2 \\=& n + \frac 12\sum_{i=1}^n \frac 12 i^2 + i \\=& n + \frac 14\sum_{i=1}^n i^2 + \frac 12 \sum_{i=1}^n i \\=& n + \frac 14 \frac{2n^3+3n^2+n}{6} + \frac 12 \frac{n^2+n}{2} \\=& n + \frac{1}{12}n^3 + \frac{1}{8} n^2 + \frac{1}{24}n + \frac 14 n^2 + \frac 14 n \\=& \frac{31n + 9n^2 + 2n^3}{24} \end{align} $ where I've used formulas for square pyramidal numbers and triangular numbers.

  • 0
    @StijnSanders: So it should. Fixed.2012-02-13
4

Use the fact that $1+...+n=\frac{n(n+1)}{2}$ and $1^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$.