aspose file tools*
The moose likes Programming Diversions and the fly likes Help with math Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Help with math" Watch "Help with math" New topic
Author

Help with math

Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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.


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
Anand Hariharan
Rancher

Joined: Aug 22, 2006
Posts: 257

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
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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

Joined: Aug 22, 2006
Posts: 257

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)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Thanks!

And, sorry, they're 20 oz soda bottle caps.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
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

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 ]
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
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.

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 ]
Anand Hariharan
Rancher

Joined: Aug 22, 2006
Posts: 257

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Help with math
 
Similar Threads
all confused about scope....
need help figuring this out.
serializable
For loop Pyramid Program
Nested Loops