🔒 Locked

Incredibly difficult math pattern...

Started by Aphelion Apr 4, 2002 at 8:43 PM 54 replies 1.8k views

Original Post

Apr 4, 2002 at 8:43 PM

Okay this has nothing to do with gaming, but I figure I''m bound to have some bit of luck with this here since this is the smartest gathering of people I can think of... Anyway, the task is to find a formula that can compute the sum of all the elements in a list that increases at a rate of number + element_number * static_step_size... Example: (The step here is 2) 0, 2, 6, 12, 20, 30, 42, ... (0 + 2) = 2, 2 + (2 * 2) = 6, 6 + (2 * 3) = 12, ... So if I asked for the sum to number 12, it''d be (0 + 2 + 6 + 12) = 20, the number 30 would be (0 + 2 + 6 + 12 + 20 + 30) = 70 As for the formula, it must be a mathematical formula and not an algorithm, and it should (but if you can find anyway to do it, that''s a start) be in terms of the variables: step and number. Here''s some info you may find useful (or not): For a static step (i.e. number + static_step_size), the formula is (number^2)/(2 * static_step_size) + (number / 2). Example: Step size (3) 0, 3, 6, 9, 12 For 9, (9^2)/(2*3) + (9/2) = 13.5 + 4.5 = 18 Proof : (0 + 3 + 6 + 9) = 18 18 = 18 I''ve tried every method I can think of for the the 1st problem (it took me long enough to find the 2nd), and I''m hoping someone else will have better luck than I have, because I''ve thrown probably 10+ hours down the drain trying to find the solution. The purpose of all this crap is I have an idea on how to solve cubic equations using pattern anylsis, and I''ve got it all down except for this last pattern... So any help is appreciated, Thanks, -Jesse

Ronin_54

Apr 5, 2002 at 2:52 AM

Errr... Somehow, you got me confused. Well, anyway, it can be done using sigma-notation... Don''t know if the forum can do it, but here it goes:

y = sigma (for n = 1 to max) n * step_size

  
       n = 1
y =    SIGMA  (n * step_size)
       n = max

Colin Jeanne

Apr 5, 2002 at 4:02 AM

Aphelion, I suggest you look in your math book about arithmetic sequences and series. It should have the information you need.

Invader X
Invader''s Realm

mikael_j

Apr 5, 2002 at 6:43 AM

Well, I''ll give you a quick hint, not how to get the sum but rather formula for how to get each number a(n)...


n = 1 2 3  4  5  6...
a = 0 2 6 12 20 30...

to me this means that a(n) = n*(n-1) (= n^2-n)
if we test this then we will see that it is correct.

That''s all the math for now since I want to take a shower...

/Mikael

Captain Insanity

Apr 5, 2002 at 11:32 AM

Once you''ve got a sigma notation, can''t you just integrate that into a formula for the nth term? Or am I thingking of something else? (don''t flame me, I''m too tired to think straight)

Ronin_54

Apr 5, 2002 at 12:46 PM

Well, the trouble with this thingy, is that it is indeed a *discrete* situation, not a *continual* one. Anwsers only exist for whole numbers above 0 (1, 2, 3, etc. ), not for fractions (1.5).

So, you can''t get a normal formula, though you can get a sigma notation, or perhaps even a differential equation...

Aphelion

Apr 6, 2002 at 10:44 PM

So is there an actual formula to this thing or not? Mathematically, it''d make sense for a formula to not exsist because in the end, this should be a redefinition of a n^3 and ultimately cubed root of n, which hasn''t been found in the past few 100 years, so...
-Jesse

Ronin_54

Apr 7, 2002 at 1:34 AM

Duh! Off course you can create a formula that, when you input the integers you get the right values. The only problem with this baby is, that there *aren''t* anwsers for non-integer input! This problem only uses integers. Therefor, you need to create a mathematical row, and you usually do that with sigma formula''s

Programmer One

Apr 7, 2002 at 3:35 AM

It can too be done with fractions the are not recursive. It just needs a little extra computation to restructure the fraction after calculation. You can maybe get this to work with recursive fractions, but the end value won''t be very exact - you would have to round.

It''s 12:28 AM here, so exuse me if I just wrote a pile of bullshit

_____________________________________________________

ICQ #: 149510932

Google - OpenGL - DirectX - Windows Guide Network - MSDN - Symantec Virus Info

"Imagination is more important than knowledge." - Albert Einstein

asd_de

Apr 7, 2002 at 4:49 AM

For me, the sum up to the nth member is 1/6*x*n*(n+1)*(n+2), where x is the step size and n is the last member to be calculated into the sum... It seems to work as well...

Aphelion

Apr 7, 2002 at 10:07 AM

Hmm, asd_de:
According to your formula, in the listing:
0,2,6,12 (step size is 2, but increases by 2 everytime as well)
12 equals: (2+6+12) = 20
but in the formula you gave:
1/6 * 2 * 12 * (12 + 1) * (12 + 2) = 728 ?!?

Or maybe you didn''t mean a list where the step increases itself every time?

asd_de

Apr 7, 2002 at 1:03 PM

0,2,6,12,...

12 is No. 3

=> n=3; x=2

(1/6)*2*3*4*5=20

I meant the number of the sum member, not the value, sorry if it was unclear :-(

[edited by - asd_de on April 7, 2002 2:03:32 PM]

Ronin_54

Apr 7, 2002 at 1:15 PM

I''ll test with my GR ^_^

-Maarten Leeuwrik
=================
Thanks to Cone3D:

Ronin_54

Apr 7, 2002 at 1:21 PM

hmmm... Loop ends at 2.

(2 * 0) + (2 * 1) + (2 * 2) =
0 + 2 + 4 =
6

1/6 * 2 * 2 * (2 + 1) * (2 + 2)=
1/6 * 4 * 3 * 4=
1/6 * 48 =
8

Sorry, it doesnt work buddy

-Maarten Leeuwrik
=================
Thanks to Cone3D:

Ronin_54

Apr 7, 2002 at 1:26 PM

Err....

Damn, I got it I think...

y = x * (x + 1) ^_^

y is the anwser, x is the element you seek.

0 -> 0 * 1 = 0
1 -> 1 * 2 = 2
2 -> 2 * 3 = 6
3 -> 3 * 4 = 12
4 -> 4 * 5 = 20
5 -> 5 * 6 = 21 [EDIT: DOH! 5 * 6 = 30

]
6 -> 6 * 7 = 42

Muahahahahaha....

You are just adding the table of 2, up till the n'th number :D

-Maarten Leeuwrik
=================
Thanks to Cone3D:

[edited by - Ronin_54 on April 7, 2002 2:26:50 PM]

asd_de

Apr 7, 2002 at 1:30 PM

I kind of do not really get what you are calculating, sorry :-) (But I do think it will be a mistake of mine):
My formula was for the sum of the first n+1 members, mikael_j has already given a formula for the members themselves...

Now for the sums:

n=0: Sum=0

1/6*2*0*1*2=0

n=1: Sum=0+2=2

1/6*2*1*2*3=2

n=2: Sum=0+2+6=8

1/6*2*2*3*4=8

n=3: Sum=0+2+6+12=20

1/6*2*3*4*5=20

???
I can''t see why it should be wrong?

Ronin_54

Apr 7, 2002 at 1:33 PM

Or you can use the simples approach:

Since you are adding up every number in the table of 2 up till the n''th element, and the difference between those elements is always 2...

You can simply multiply n by 2, that gives you the largest number... That you devide by 2, gives you the average of the whole list... That should be multiplied by n to add everything up... And then you are but one n short of the anwser...

So:
((( n * 2 ) / 2 ) * n ) + n =
((n) * n) + n =
(n * 2) + n =
n * n + n

And in the end that is just ( n + 1 ) * n...

Okay, your choice:

Either you pick y = x * (x + 1) or y = x^2 + x ^_^

asd_de

Apr 7, 2002 at 1:45 PM

Sure, this is correct for step x=2. For a general step, you can calculate that

a(n)=sigma(for i=0 to n) of x*i

You can simplify that using the sum formulas to

a(n)=x*sigma...

this in turn is

a(n)=x*n*(n+1)/2

which gives exactly your formula for step=2.

My sum formula for those members should still be correct (Aphelion DID want the sum of all the list members up to some one???). If not, point me to the error... :-)

Ronin_54

Apr 7, 2002 at 2:00 PM

Okay, my approach for dummies:

Step 2: x elements, x = 5 for easy calculating

We add all numbers together:

(0 x 2) + (1 x 2) ... + (5 x 2)
0 + 2 + 4 + 6 + 8 + 10

Now we need an algorithm. And there is a really easy one:
5 * 2 = 10

00 + 02 + 04 + 06 + 08 + 10 = 30
10 + 08 + 06 + 03 + 02 + 00 = 30
---------------------------
10 + 10 + 10 + 10 + 10 + 10 = 60

And (2 * 5) * (5 + 1) = 60. 5 + 1 ''cause 0 is also an element, making for a total of 6.

We are too big though. We counted everything double. We need to devide by 2.

((2 * 5) * (5 + 1)) / 2 = (10 * 6) / 2) = 30

What we did was (2 * x) * (x + 1)) / 2
And that leads to x * (x + 1)

Now for step 3:

5 * 3 = 15

00 + 03 + 06 + 09 + 12 + 15 = 45
15 + 12 + 09 + 06 + 03 + 00 = 45
---------------------------
18 + 18 + 18 + 18 + 18 + 18 = 90

Calculating:
(x * n) * (x + 1) ->
(5 * 3) * (5 + 1) ->
15 * 6 ->
90

Twice too big, so devide by 2.

Giving us the formula ((n * x) * (x + 1 )) / 2

There is the formula for step size n, with x elements:
sum = .5(nx(x+1))

asd_de

Apr 7, 2002 at 2:06 PM

That''s the same result that I get for the formula for each member, so it seems to be correct. BTW, if you REALLY want to calculate the sum of your list up to some given member''s value, not up to his index, it works as well (but is a lot more complicated) - a is the member VALUE this time:

1st solution: 1/12*(-x+sqrt(x^2+8*x*a))*(1/2/x*(-x+sqrt(x^2+8*x*a))+1)*(1/2/x*(-x+sqrt(x^2+8*x*a))+2)

2nd solution: 1/12*(-x-sqrt(x^2+8*x*a))*(1/2/x*(-x-sqrt(x^2+8*x*a))+1)*(1/2/x*(-x-sqrt(x^2+8*x*a))+2)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.