• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Help with math

 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
VI Editor C++ Debian
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
VI Editor C++ Debian
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks!

And, sorry, they're 20 oz soda bottle caps.
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 280
VI Editor C++ Debian
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
reply
    Bookmark Topic Watch Topic
  • New Topic