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:


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.


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.

  • $\begingroup$ 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 $\endgroup$ – Stijn Sanders Feb 10 '12 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Feb 10 '12 at 14:21
  • $\begingroup$ 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. $\endgroup$ – Stijn Sanders Feb 10 '12 at 17:00
  • $\begingroup$ Oh, I see -- your comment crossed my last edit. Sorry for the confusion. $\endgroup$ – hmakholm left over Monica Feb 10 '12 at 17:58
  • $\begingroup$ Hmm, shouldn't that last $+ \frac 12 n$ be $+ \frac 14 n$? $\endgroup$ – Stijn Sanders Feb 13 '12 at 7:14

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


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.