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
    So trying to putting it back to Pascal it could like like this: `l:=n+n*((((2*n+3)*n+1) div 6)+(n+1)) div 4`2012-02-10
  • 1
    Possibly, though I haven't cross-checked the algebra -- but why write it so convolutedly? Compared to plain `n*(37+n*(9+2*n)) div 24` you have one division and two additions more.2012-02-10
  • 0
    hey you added two lines! It was kind of what I was trying to do, but didn't work on them factors. Also by keeping one or more div's up front we might just keep the rounding differences smaller, but that's work for a whole different part of the brain.2012-02-10
  • 0
    Oh, I see -- your comment crossed my last edit. Sorry for the confusion.2012-02-10
  • 0
    Hmm, shouldn't that last $+ \frac 12 n$ be $+ \frac 14 n$?2012-02-13
  • 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}$.