Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# Help with math

(instanceof Sidekick)
Posts: 8791
• • • • 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.

Rancher
Posts: 280   • • • • 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! Stan James
(instanceof Sidekick)
Posts: 8791
• • • • Well, get 220 bottle caps and follow along ... 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 ]

Anand Hariharan
Rancher
Posts: 280   • • • • If 'n' is same as 'layerCount', and f(n) is capsInPyramid then

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

- Anand

[Edit: Removed post script]
[ November 27, 2007: Message edited by: Anand Hariharan ]

Stan James
(instanceof Sidekick)
Posts: 8791
• • • • Thanks!

And, sorry, they're 20 oz soda bottle caps. Rancher
Posts: 1197
22
• • • • So how did Anand derive that formula?

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

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 ]

Ryan McGuire
Rancher
Posts: 1197
22
• • • • There's another option for deriving the polynomial coefficients from a series when you know some number of consecutive values.

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.

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

Anand Hariharan
Rancher
Posts: 280   • • • • 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: • 