Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm sorry this looks a lot like a do my homework question, but it's something I came across at work and though 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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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 –  Stijn Sanders Feb 10 '12 at 13:59
    
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. –  Henning Makholm Feb 10 '12 at 14:21
    
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. –  Stijn Sanders Feb 10 '12 at 17:00
    
Oh, I see -- your comment crossed my last edit. Sorry for the confusion. –  Henning Makholm Feb 10 '12 at 17:58
    
Hmm, shouldn't that last $+ \frac 12 n$ be $+ \frac 14 n$? –  Stijn Sanders Feb 13 '12 at 7:14
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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