Ranch Hand

Is there an f(n) to compute this in one shot instead of the loop?

This is important because I'm only 9 caps from finishing the darned thing, proving that I've been sitting at this desk for one year.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

Originally posted by Stan James:

I made a triangle of bottle caps 10 on a side, another triangle of 9 on top of that and so on to the solo cap on the top. It takes (n*(n+1))/2 caps to make each layer. I made a little loop to compute 55+45+36 etc for 220 bottle caps.

Is there an f(n) to compute this in one shot instead of the loop?

This is important because I'm only 9 caps from finishing the darned thing, proving that I've been sitting at this desk for one year.

Am not sure I understand you entirely (in fact, I suspect I don't understand at all).

Are you asking how to sum a series, the difference between successive terms of which are in an arithmetic progression?

- Anand

PS: Some photographs of your project will be nice!

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery

Ranch Hand

This works:

A triangle fills half of a rectangle ... a 10 sided triangle fills half a 10x11 rectangle, so 10*11/2 gets me 55 caps. I compute and sum those for all layers.

I was rather hoping my pyramid fills some fraction of a solid that looks to be 10x10x11. 10*10*11/5 = 220. Must be coincidence ... doesn't work for other sizes.

I have a photo of the last one ... I'll see if I can find it.

[ November 16, 2007: Message edited by: Stan James ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

f(n) = n * (n + 1) * (n + 2) / 6

- Anand

[Edit: Removed post script]

[ November 27, 2007: Message edited by: Anand Hariharan ]

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery

Ranch Hand

I bet from two simpler ones:

sum(x) from x=1 to n = n(n+1)/2

sum(x^2) from x=1 to n = n(n+1)(2n+1)/6

Your pyramid is...

f(m)=sum(sum(x) from x=1 to n) from n=1 to m, where m is the length of the base

f(m)=sum(n(n+1)/2) from n=1 to m

f(m)=sum((n^2 + n)/2) from n=1 to m

f(m)=(sum(n^2 + n) from n=1 to m)/2

f(m)=(sum(n^2) from n=1 to m + sum(n) from n=1 to m)/2

f(m)=(((2m^3 + 3m^2 + m)/6) + ((m^2 + m)/2)) /2

f(m)=(((2m^3 + 3m^2 + m)/6) + ((3m^2 + 3m)/6)) /2

f(m)=((2m^3 + 6m^2 + 4m)/6) /2

f(m)=((m^3 + 3m^2 + 2m)/6)

f(m)=m(m+1)(m+2)/6

f(10) = 220 bottle caps.

f(11) = 286

f(12) = 364 Which would be pretty close to a year if you worked weekends and holidays.

[ November 23, 2007: Message edited by: Ryan McGuire ]

It's not very hard to determine from observation that...

f(0) = 0

f(1) = 1

f(2) = 4

f(3) = 10

f(4) = 20

1. Initialize a temporary series d0() to be equal to your f().

2. Find the first delta between each pair of values. Keep finding deltas until all the values are the same. (This is a while(){} loop, not a do {} while(). It might just be that d0() already satisfies the stopping condition.)

d[n](x) = d[n-1](x+1) - d[n-1](x)

d1(0) = 1

d1(1) = 3

d1(2) = 6

d1(3) = 10

Notice that you can get one fewer values for d1() than you had for d0(). Likewise for d2() compared to d1(), etc.

d2(0) = 2

d2(1) = 3

d2(2) = 4

d3(0) = 1

d3(1) = 1

Cool. All the values for d3() are the same so we can stop.

3. Look at the highest order of delta you calculated (we got to d3() so the highest order is 3). That is the highest power of x in out final equation. The coefficient for x^3 is that single value (all our d3() values == 1) divided by the power factorial (remember 0! = 1). 1/3! = 1/6, so the first term for our final polynomial is x^3/6.

4. Subtract that term (x^3/6) from each value of d0(). If d0() has any non-zero values, go back to step 2.

NEW...

d0(0) = 0 - 0^3/6 = 0 - 0 = 0

d0(1) = 1 - 1^3/6 = 1 - 1/6 = 5/6

d0(2) = 16/6

d0(3) = 33/6

d0(4) = 56/6

d1(0) = 5/6

d1(1) = 11/6

d1(2) = 17/6

d1(3) = 23/6

d2(0) = 1

d2(1) = 1

d2(2) = 1

So the next term of for our final function has a power of 2 (because we went to d2()) and a coefficient of 1/2! = 1/2. So far we have x^3/6 + x^2/2

Subtract that new term out again and start over...

d0(0) = 0 - 0^2/2 = 0

d0(1) = 5/6 - 1^2/2 = 2/6

d0(2) = 16/6 - 2^2/2 = 4/6

d0(3) = 33/6 - 3^2/2 = 6/6

d0(4) = 56/6 - 4^2/2 = 8/6

d1(0) = 2/6

d1(1) = 2/6

d1(2) = 2/6

d1(3) = 2/6

The next term is x/3.

d0(0) = 0

d0(1) = 0

d0(2) = 0

d0(3) = 0

d0(4) = 0

The last term is 0.

This means out polynomial expression for f is....

f(x) = x^3/6 + x^2/2 + x/3 = (x^3 + 3x^2 + 2x)/6 = x(x+1)(x+2)/6

You could use this "algorithm" to re-derive the formulae...

f(x) = sum(n) from n=1 to x

f(x) = sum(n^2) from n=1 to x

Exercise for the interested reader: What's the formula for...

f(x) = sum(n^3) from n=1 to x

I'd guess it has a x^4 term and you would therefore have to start with at least 5 values.

There... how about that for more information than needed! :-)

[ November 26, 2007: Message edited by: Ryan McGuire ]

[ December 18, 2007: Message edited by: Ryan McGuire ]

Originally posted by Ryan McGuire:

There's another option for deriving the polynomial coefficients from a series when you know some number of consecutive values.

(...)

You could use this "algorithm" to re-derive the formulae...

(...)

Awesome stuff, Ryan.

Originally posted by Ryan McGuire:

There... how about that for more information than needed! :-)

Never more than needed, Ryan.

thank you,

- Anand

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery