a^2+b^2+c^2=45
a+b+c=11
how do I find abc ?
what is the method??
and how can i apply it when the sequence goes up to Z?
can somebody help me ?
Printable View
a^2+b^2+c^2=45
a+b+c=11
how do I find abc ?
what is the method??
and how can i apply it when the sequence goes up to Z?
can somebody help me ?
Welcome to the forums.
Interesting problem. There are more unknowns than equations, so there could be multiple solutions. Re how to find a, b, c, it depends on how formal you want to be. Combining the equations results in a single equation with 2 unknowns. I was able to obtain 6 whole number only solutions in 5 minutes playing around with the Excel solver. If you wanted to be more formal, it looks like this could be approached as a optimization problem with 2 parameters.
thanks, i was hoping there could be some type of formula that could show me all the possible combinations that the variables can be. By the way, the equation does not have to stop at C. It can go on up to Z, so you can have 26 different variables.
Impossible?
Well, here's another possibility. Rearrange the 2nd equation to this, for example: a = 11 - c - b and substitute into the first. Expand a2 and collect terms. You have a quadratic equation in b and c. Solve for either and the result could provide insight as to the possible solutions.
Expanding to more variables if you don't add more equations, such as:
a2 + b2 + c2 + d2 + e2 = 364
a + b + c + d + e = 42
makes it much more difficult - I can't think of anything other than the optimization approach. The problem as stated makes the analytic approach at least reasonable.
I confirmed that there is an analytic solution to the form of the problem as you stated. By substituting a = 11 - b - c and collecting terms, you get a single equation that is quadratic in both b and c. Solve it for b using the quadratic formula. The discriminant is a quadratic equation in c. Solving for the roots of the discriminant using the quadratic formula gives you the upper and lower bounds on c, which, in turn, allows you to find the bounds on b and a.
And here is the solution. The x-axis represents c and the y-axis b and a. The blue curve is b, and the red curve is a. The circles at intersections of the lines are the whole number solutions.
Hmmmm, the thought just occurred to me that as you add more variables, the layers of quadratic equations increases. The original problem had 3 variables that resulted in 2 nested quadratic equations. I'm guessing that for n variables, you'd end up with n-1 nested quadratic equations that when solved successively will yield the complete solution. May be a promising approach? Naw, can't be that simple........
.
Interesting little graph you have there, VBAhack... check out the graph of y = x3 - 11x2 + 38x on the range 1 < x < 6
The question doesn't appear to be what the values of a, b, and c are. Rather, the question is what is the product of a, b, and c. The simplest approach would be to let a = b, then solving for c gives you both the upper and lower bounds for the individual variables. With that, solve for a (and b) to find the upper and lower bounds of the product.
thanks guys..... neat stuff....
a^2+b^2+c^2+d^2+e^2+f^2+g^2+h^2+i^2+j^2=1826
a+b+c+d+e+f+g+h+i+j=114
a<b
b<c
c<d......and so on.
i guess this is what i should have posted originally. The aim is to find abcdefghij. I desperately need to know the formula how to find the values. The number of variables can vary. Any easy way to do this one?
Wow, I missed that totally. Though, if you can find a, b, c you certainly can compute a*b*c. The question is, can you determine a*b*c without finding a, b, c? Don't know.......Quote:
Originally Posted by Logophobic
a2 + b2 + c2 = 45
a + b + c = 11
(a + b + c)2 = 121
a2 + b2 + c2 + 2(ab + ac + bc) = 121
ab + ac + bc = 38
ab = (11 - b - c)(11 - a - c)
ab = 112 - 11(a + b + c) - 11c + (ab + ac + bc) + c2
ab = c2 - 11c + 38
abc = c3 - 11c2 + 38c
ac = b2 - 11b + 38
abc = b3 - 11b2 + 38b
bc = a2 - 11a + 38
abc = a3 - 11a2 + 38a
It looks simple enough... try it with 4 variables.
The attached image is the graph of y = x3 - 11x2 + 38x.
As for the ten-variable sums, I wrote a simple recursive subroutine which found 492 unique integer-only solutions. The products from those solutions range from 800 million to 7.5 billion. Is there anything practical about this?
Nice one Logophobic :thumb:
Lucia333 should be happy.
It never fails that I end up down the most difficult path on problems like this.:sick:
I just went through the 4 variable case using the nested quadratic equation method and eventually solved it for the ranges of a, b, c, d but not the product. It was horrible.
One thing I'm curious about:
.Quote:
The simplest approach would be to let a = b, then solving for c gives you both the upper and lower bounds for the individual variables
Looking at my plot it makes sense, because b=c at the extremes of a, but how would one have known or deduced that this would be true?
Good question. Looking at the graph in my previous post my give some insight. Two variables are equal at either vertex, and the third is at maximum or minimum. I stumbled upon it myself, but I suppose someone might have seen it from the start, that a, b, and c are the roots of a cubic function where their product (abc) is the constant coefficient. Or maybe I'm out of touch with reality. Boom boom, ain't it great to be cra-zy. :)Quote:
Originally Posted by VBAhack
(x - a)(x - b)(x - c) = 0
x3 - (a + b + c)x2 + (ab + ac + bc)x - abc = 0
x3 - 11x2 + 38x - abc = 0
abc = x3 - 11x2 + 38x
Thanks guys... you are the best...
but what would be the maximum number of variables that we could do with this solution. The product of abcdefghijklmnopqrstuvwxyz......etc etc... is not important. What I need is a way to actually determine the values of the variables. This way works great but i dont see it working for 1000 variables. :eek2: The numbers would be too large. I was hoping there was a solution that would allow me to do unlimited variables. :bigyello:
Dreaming?
oh and by the way, This problem is not just to tickle our brains. There is a very real-life application to this which I am will not reveal for now :p
It took me a looooong time scratching my head and staring at your plot to finally figure out what you were saying. A horizontal line at any value of y (a*b*c) intersects the curve at 3 points, the intersections representing a, b, and c. This is wild! That's why I like math - it never ceases to be fascinating! :pQuote:
Originally Posted by Logophobic
So, if you have the polynomial expression for a*b*c in terms of only a and you know the bounds of a, you can easily calculate the bounds of a*b*c.
Assumming the trick of setting all variables equal to each other except for 1 works in general, I managed to figure out the expression for the bounds of a for the general case of n numbers. Let:
a2 + b2 + ... n2 = t
a + b + ... + n = w
Then, the bounds of a are:
(1/n)*(w +/- sqrt[(n-1)(tn-w2)])
Coming up with an expression for a*b*c*..*n is another story.......
I have managed to reduce the problem to something that i hope is a little more manageable.
a^2+b^2+c^2+d^2+e^2+f^2+g^2+h^2+i^2+j^2=1378
a+b+c+d+e+f+g+h+i+j=102
from here, thanks to logophobic, we get to
(a+b+c+d+e+f+g+h+i+j)^2=10404
which is
b(a)
+c(a+b)
+d(a+b+c)
+e(a+b+c+d)
+f(a+b+c+d+e)
+g(a+b+c+d+e+f)
+h(a+b+c+d+e+f+g)
+i(a+b+c+d+e+f+g+h)
+j(a+b+c+d+e+f+g+h+i)=4513
now lets assume that we are also given the value of
(a)
+(a+b)
+(a+b+c)
+(a+b+c+d)
+(a+b+c+d+e)
+(a+b+c+d+e+f)
+(a+b+c+d+e+f+g)
+(a+b+c+d+e+f+g+h)
+(a+b+c+d+e+f+g+h+i)
which would be 293
then that would mean
9a+8b+7c+6d+5e+4f+3g+2h+i=293
From here, is it any easier to get a,b,c,d,e,f,g,h,i ?
Hmmm, I get a different result for (a+b+c+d+e+f+g+h+i+j)2:Quote:
Originally Posted by Lucia333
a2+b2+c2+d2+e2+f2+g2+h2+i2+j2
+ 2a(j+i+h+g+f+e+d+c+b)
+ 2b(j+i+h+g+f+e+d+c)
+ 2c(j+i+h+g+f+e+d)
+ 2d(j+i+h+g+f+e)
+ 2e(j+i+h+g+f)
+ 2f(j+i+h+g)
+ 2g(j+i+h)
+ 2h(j+i)
+ 2i(j)=10404
or
(a2+b2+c2+d2+e2+f2+g2+h2+i2+j2) + 2(the rest) = 10404
since a2+b2+c2+d2+e2+f2+g2+h2+i2+j2 = 1378 it follows that (the rest) = (10404-1378)/2 =4513.
where I get hung up is trying to evaluate bcdefghij using logophobic's idea:
bcdefghij = (1378-a-c-d-e-f-g-h-i-j)(1378-a-b-d-e-f-g-h-i-j)(1378-a-b-c-e-f-g-h-i-j)(etc)
There must be a pattern. I tried it the tedious way with 4 variables and got really bogged down. The result was 64 terms that I couldn't figure out how to combine within my attention span. That multiplication results in nn-1 terms, which grows very rapidly as n increases. There has got to be a pattern.
Logophobic, can you reveal the trick?
That's what i keep saying to myself,
there's got to be a pattern
there's got to be a pattern
there's got to be a pattern
there's got to be a pattern
:eek2:
because this means that with our current computer technology, it is impossible to get a result when n=10000 cause the number would be out of this world
Shame really, because there is a very practical use for this, if it can be solved.
Don't forget that there are extended precision packages that allows computations on v-e-r-y large numbers. I once used a variable-precision fortran package to invert a 60x60 Hilbert, which involved some pretty large numbers. The good news, the code is public domain. Food for thought.....Quote:
Originally Posted by Lucia333
This approach works when n = 3 because you have only 1 independent variable, once chosen, uniquely determines the other 2. In the case of 4 variables, 2 need to be chosen arbitrarily (within their bounds of course) in order to uniquely determine the other 2. In other words, the bounds on 'a' can be easily determined. The bounds on 'b', howerver, are different depending on the specific value of 'a' chosen and 'b' can be freely chosen within those bounds.Quote:
Originally Posted by Logophobic
What this means (I think) is that for n=3 the entire solution is described by cubic equation (1 independent variable) as both you and I have shown, whereas for n=4 the solution would be surface (2 independent variables), for n=5 a hyper(?) surface, etc. Each n adds one more independent variable and geometric dimension to the solution. Does this make sense?:ehh:
What I have been working on:
(x - a)(x - b)(x - c)(x - d) = 0
(x4 - (a + b + c + d)x3 + (ab + ac + ad + bc + bd + cd)x2 - (abc + abd + acd + bcd)x + abcd = 0
abcd = -x4 + (a + b + c + d)x3 - (ab + ac + ad + bc + bd + cd)x2 + (abc + abd + acd + bcd)x
We are given (a + b + c + d) and (a2 + b2 + c2 + d2), and can show that 2(ab + ac + ad + bc + bd + cd) = (a + b + c + d)2 - (a2 + b2 + c2 + d2)
I am having trouble evaluating (abc + abd + acd + bcd), though. I've just been running in circles trying to isolate it against the known sums.
Hmm...
a + b + c = P
a2 + b2 + c2 = Q
d + e + f = R
d2 + e2 + f2 = S
a + b + c + d + e + f = P + R
a2 + b2 + c2 + d2 + e2 + f2 = Q + S
In this situation, for any value a within the bounds of a, there is exactly one value for abc. The other 3 variables and their product are entirely independent of this, such that for any value a within the bounds of a, there are finitely many values for abcdef. That this product cannot be expressed as a function of any single variable gives merit to VBAHack's previous post.
I tried the same thing and ran into the exact same problem.
I've actually solved the 4 variable case numerically using the nested quadratic equation approach I mentioned in an earlier post (it wasn't fun). The area plot of the domain of the independent variables (let's say a and b) looks identical to the plot I posted, with 'a' along the x-axis and 'b' is along they y-axis. The domain is any interior point to the oblique elipse. The product abcd would then be a surface using that domain.
I think I solved the 4 variable case. Considering my last 2 posts, what we need is an expression for cd since a and b are more or less independent variables.
a + b + c + d = w
a2 + b2 + c2 + d2 = t
(a + b + c + d)2 = w2
(a2 + b2 + c2 + d2) + 2(ab + ac + ad + bc + bd + cd) = w2
t + 2(ab + ac + ad + bc + bd + cd) = w2
(ab + ac + ad + bc + bd + cd) = (w2 - t)/2
c = w - a - b - d
d = w - a - b - c
cd = w2 -w(a + b + c + d) - w(a + b) + a2 + b2 + ab + (ab + ac + ad + bc + bd + cd)
cd = w2 - w2 - w(a + b) + a2 + b2 + ab + (w2 - t)/2
cd = a2 + b2 + ab - w(a + b) + (w2 - t)/2
abcd = ab[a2 + b2 + ab - w(a + b) + (w2 - t)/2]
abcd = a3b + b3a + a2b2 - w(a2b + b2a) + ab(w2 - t)/2
We also know that the bounds on 'a' are:
abounds = (1/n)*(w +/- sqrt[(n-1)(nt-w2)]) = (1/4)(w +/- sqrt[3(4t - w2)] = (1/4)[w +/- sqrt(12t -3w2)]
and it can be shown that bounds on 'b' are:
bbounds = [(w-a) +/- sqrt(h)]/3 where h = (w - a)2 - 3(w2 - 2wa - 2t + 3a2)
So, we have expressions for the product abcd, the bounds of 'a', and the bounds of 'b', but no easy way to evaluate the bounds of abcd.:o
Progress for sure, but the real killer is having so many quasi independent variables as n increases.
The thought occurred to me that an unrefutable fact is that we have 2 equations in n unknowns. This really boils down to a constrained optimization problem in n-2 variables, where the constraints are interdependent. In the 4 variable case, since we know the limits on a=f(w,t) and b=f(a,w,t), we could do the following:
let:
b1 = lower bound of b
b2 = upper bound of b
a1 = lower bound of a
a2 = upper bound of a
we can then create new functions a = f(x,a1,a2) and b=f(y,b1,b2):
Now, having an objective function abcd = f(a,b,w,t) with a=f(x), b=f(y), and the limits of x & y between 0 and 1 we can use standard optimization techniques (e.g. simplex) to find x & y (and therefore a & b) that make abcd a minimum or maximum. It also means that the domain of a & b has been mapped parametrically to x & y, each with bounds of 0,1. Makes function evaluation and plotting easier. :DCode:a = (a2-a1)x + a1 0 <= x <= 1
b = (b2-b1)y + b1 0 <= y <= 1
Low and behold the problem exhibits the same exact characteristic as the 3 variable case, where the min of abcd occurs where a is a minimum and the max of abcd occurs where a is a maximum.
Thus, it would appear (unless I'm totally wrapped around the axle) that using the expression for abcd in my last post, we can find the min/max just by using the limits of a, since the upper and lower limits of b are equal at the extremes of a and thus uniquely determined. This would appear to mean that the max/min of abcd is, in fact, a function of a single variable. Of course, abcd is a function of 2 variables (can't get around 2 equations in n unknowns), but the min/max seems to be a function of a single variable.
I invite you guys to check my work (to make sure I'm still playing with a full deck:rolleyes:). I used a specific case of w = 20 and t = 120. The max value of abcd = 452.73 and min value of abcd = 280.6
This is wild - I hope I haven't blown a gasket..........
P.S. attached is a plot (side view) showing abcd with respect to the parametric x (i.e. a) axis. Looks a lot like Logophobic's plot for the 3 variable case. Btw, anybody have a good (and free) 3-D plotting package they'd recommend? I just use Excel which isn't very good.:mad:
.
This sounds way too simple to be true, but I think I figured out the n variable case for the min/max of the product of the variables. What seems to be true for the 3 and 4 variable cases is the following:
- min/max of a occurs when all other variables are equal to each other
- min/max of the product occurs when a is at min/max
- b (and therefore all remaining variables) are uniquely determined when a is at its min/max
Therefore, I believe the following to be true (extending the above to n variables):
(min/max of a) = (w +/- sqrt[(n-1)(tn-w2)])/n
(b at each a) = (w-a)/(n-1)
(product min/max) = abn-1
Seems to hold true for n = 3 and n = 4. Can't be this simple..........:eek:
Alas, it would seem I lost track of the objective. :sick: It wasn't to find the min/max of the product at all, but rather the actual values of a, b, c, d, etc.Quote:
Originally Posted by Lucia333
I think we're back to the beginning. The only way I can think of is the nested quadratic equation approach, which would entail deriving (n-2) quadratic formulas....:(
I've solved the problem up to n = 5 and think I see a pattern for how to determine a, b, c, d, etc. It's getting very tedious so I don't think I'll go any further. Here is what I've determined so far:
a: [w +/- sqrt(P)]/n
P = (n - 1)(nt - w2)
b: [(w-a) +/- sqrt(P)]/(n-1)
P = (w-a)2 - (n-1)[w2 - 2wa - (n-2)t + (n-1)a2]
c: [(w-b-a) +/- sqrt(P)]/(n-2)
P = (w-b-a)2 - (n-2)[w2 - 2w(a+b) - (n-3)t + (n-2)(a2+b2) + 2ab]
d: [(w-c-b-a) +/- sqrt(P)]/(n-3)
P = (w-c-b-a)2 - (n-3)[w2 - 2w(a+b+c) - (n-4)t + (n-3)(a2+b2+c2) + 2(ab+ac+bc)]
Even if you were able to form an algorithm for aribtrary n (appears possible) I'm not sure what it would accomplish because you've got (n-2) independent variables. There are an infinite number of combinations of values of the independent variables.
Fun problem, though. Hope this thread has helped your cause.:)
Thanks VBAHack
It appears you are the last one standing with this problem.. :)
So in a nutshell, what you are saying is...
"it's impossible to get all values for a,b,c,d,e,f,g,h,i.......etc where n=10000"
do I follow you correctly?
Check this out:
a2 + b2 + c2 + d2 = 87
a + b + c + d = 17
what the.... :eek: :eek2:
Every point on the surface of that object (an oblate spheroid) is a solution to the system of equations.
The small black circle is d=1. The other three visible black rings are d=2, d=3, and d=4. The blue ring in the foreground is c=7. The next two blue rings are c=6 and c=5. The visible red and green rings are, from right to left and bottom to top, a=2 through a=7 and b=2 through b=7.
The intersections on the nearest blue ring, clockwise from bottom left, are (5, 2, 7, 3), (5, 3, 7, 2), (3, 5, 7, 2), and (2, 5, 7, 3).
logophobic.. i got three questions for you
1. Can this technique of yours be somehow turned into a script that will automatically determine the points at which the lines on the spheroid intersect to get the integer values of a,b,c,d,e...etc?
2. Can this technique be used for very large n. Example n=10000?
3. Those calculations that you and VBAhack do are out of this world. How do you guys do it? What do you all do for living? Nuclear physics? :ehh:
So, what you really want is just one (integer) solution? I didn't gather that from previous posts. Maybe you need to re-state the objective more clearly. Somehow we went down the path of thinking it was the product abcd, then the max/min of the product abcd, then the actual values of a, b,c,d, then only integer values of a,b,c,d. By the way, how do you know there even is a solution of integer values only?Quote:
Originally Posted by Lucia333
Anyway, Logophobic is the real expert here. I'm just a ...........well.......hack............having some fun when I should be doing other stuff.:o
P.S. Logophobic, I'd like to know what you use for your plots. They are cool.:cool:
Me? An expert? I guess so - my expertise is in convincing others that I know what I'm talking about.
The object was modeled using POV-Ray. The best thing about this software is that it is totally free. I have done little more than the most basic CSG, barely a drop of water in an ocean. Just look at some of the images in their Hall of Fame
The oblate speroidal shape of the object is mainly a function of how I originally created it. After studying it a bit, I have remodeled the object as a sphere with 4 axes. It is completely symmetrical, such that a, b, c, and d are all interchangeable. I'll get some images in my photobucket showing some of the progress. It may be several hours before I put anything up.
I was surprised at how easy it was to model. Soon after I started toying with POV_Ray on this, I realized something quite obvious:
a2 + b2 = n | x2 + y2 = r2
Hey, that's a circle!
a + b = m | x + y = c
And, by golly, that's a line!
There is no solution if the line does not intersect the circle, one solution if the line is tangent to the cirlce (a = b), and two solutions if it is a secant line of the circle.
a2 + b2 + c2 = n | x2 + y2 + z2 = r2
That's a sphere, no doubt about it.
a + b + c = m | x + y + x = c
And that must be a plane.
Similar to the first, there is no solution if the plane does not intersect the sphere, and one solution (a = b = c) if the intersection is a single point. Otherwise, the intersection defines a circle, and every point on that circle is a solution.
Having solved the 3-variable system, which I modeled as a torus with neglible minor radius, I realized I could approximate the 4-variable system as a series of tori (incrementing d and solving the resulting 3-variable system). The result was obviously speroidal.
Finding any and all integral solutions is a matter of brute force. As I stated earlier, there are 492 such solutions to the 10-variable system given in post #7.
Objective: Get integer values for a,b,c,d,e,f,g,h,i,j,k,l,m,....... etc etc etc ... where number of values =n... and n is very large... like maybe 1000 or 10000. I just need to know if there is any simple way for us to determine what those values are. From logophobic's spheroid, it seemed to me that it is just a simple matter of plotting the lines on the spheroid and seeing where they all intersect. :D
Of course, I know there is a lot more to it than that. I am just not sure if the spheroid technique can be turned into some type of mathematical formula would would allow us to get the values.
How do i know there is an integer solution?.... well, I am only working with equations which do have integer solutions. I just need a way to determine those values.
Hope that makes it a little more clear
To chip in two cents, and effectively summarising what has already been said:
1) You have two equations with n unknowns.
2) Therefore you can't uniquely determine all of the variables.
3) Therefore you need to solve for them to find if any solutions exist.
4) A basic way is to write nested loops and just iterate through all possibilities until you find an answer.
5) Clearly this is not a good solution; a better one is to write an optimization and minimise some objective function.
6) The time and computing power it will take to solve will depend on the number of variables you are trying to solve for. Solving for 10,000 variables is not going to be an easy task.
I'm afraid there isn't any way to avoid the facts.
What zaza said...
Here is an example of nested loops. Not a good solution with a large number of variables. For the 10-variable system, I used a recursive subroutine to increment the values in an array. With a little bit of optimizing, it didn't take very long. With many more variables, it could take much longer.
Code:Dim a As Long
Dim b As Long
Dim c As Long
Dim d As Long
Dim SumOfNumbers As Long
Dim SumOfSquares As Long
Dim CalcSum As Long
Dim CalcSquares As Long
SumOfNumbers = 17
SumOfSquares = 87
For a = 0 To SumOfNumbers
For b = a To SumOfNumbers
For c = b To SumOfNumbers
For d = c To SumOfNumbers
CalcSum = a + b + c + d
CalcSquares = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2
If CalcSum = SumOfNumbers And CalcSquares = SumOfSquares Then
Debug.Print a; b; c; d; "is a solution"
End If
Next d
Next c
Next b
Next a
Funny, I just did the same thing with 10 variables and got a few more gray hairs waiting for it to complete - I stopped it after 15 minutes (no patience).
A couple of time saving observations wrt to the nested loop method:
1. You can forget the last loop since the last variable is just the number you want minus the sum of the other variables. With this, all you need to check is the sum of squares.
2. I think my expression for the bounds on 'a' can also be considered the bounds on all variables, thus limiting the values used in the loops.
I still think the only way to go is some sort of constrained optimization approach, especially if (2) is true, which I think it is. I've heard of optimization problems involving thousands of variables, though I don't have any specific reference. Optimization using derivatives won't work becuase the Hessian (second partial derivative w/ respect to each variable) is constant (i.e. doesn't allow iterative solution methodology), but there are several derivative free optimization methods around (I'm thinking of people like Brendt or Powell). Might be worth exploring. The question is whether they can be applied to integer only situations. Don't know.
Logophobic, thanks for the plotting tip. I l-o-v-e free stuff.:D
also, dont forget. Each variable is smaller than the next.
so you can never a situation where A is 4 and B is 3.
The numbers go up, from left to right.
Just thought I would remind everyone again, so that we all don't spin off in the wrong direction again.
Possibly. You are making the assumption that you already know that there are a) integer solutions and b) that they are not all the same.
For example, suppose we had the situation:
a+b+..+y+z = 260
a^2 + b^2 + ... + y^2 + z^2 = 2600
Under the approach above, the maximum number of iterations would be needed to find the solution. It sounds to me as though you are thinking of this from some sort of cryptographic perspective; you already know that you require integers, that they are all different etc.
However, from a computational perspective it doesn't matter. There isn't a way to determine what the best iterative method would be in order to find the solution for different sets of variables, because that would imply that you already know the answer. Ultimately, all we know is the format of the variable addition and the two sums.
I agree with VBAhack that an optimization approach would be best- however it is still likely to be a non-trivial matter when using this vast number of variables.
zaza
15 minutes?Quote:
Originally Posted by VBAhack
I have just spend the last hour or so recoding the recursive subroutine I mentioned, optimizing the code to avoid unnecessary calculations. Given 10 variables with sum 114 and sum of squares 1826, I have these results:
0 < a < b < c... 492 solutions in 0.16 seconds
0 < a ≤ b ≤ c... 12672 solutions in 4.8 seconds
0 ≤ a ≤ b ≤ c... 17459 solutions in 8.1 seconds
Obviously, there are a great many permutations of those solutions when the restriction of a ≤ b ≤ c is removed. This, however, is entirely independent of the number of unique solutions. Whether or not this restriction actually applies is a moot point. Any solution in which b < a is a permutation of some solution in which a < b.
Hmmm, all I did was write 10 nested do loops in VBA taking care that each successive variable was larger than the previous one. Basically, the same as you posted in your response to Zaza. Did you write yours in VB, C, Fortran?Quote:
Originally Posted by Logophobic
[Edit: I tried it again and it was much quicker - must be my laptop was in a funk the first time]
Even if, with code optimization, you could solve the 10 variable problem in 0.01 sec, computation time would probably scale by what, n2, which means 10,000 variables would take about 3 hours.
One thought I had for further optimization was that for each a, you can calculate the limits on b, for each b, you can calculate the limits on c, etc. Including this (if you already haven't) might speed things up, but I doubt that it would be possible to do a 10,000 variable problem in a reasonable amount of time.......
Questions for Lucia333:
1. Are negative integers allowed?
2. Are you satisifed with just one integer solution or do you need them all?
negative integers are not allowed.
I require all solutions.
If it could somehow be possible to get one solution and then from there calculate the rest of the solutions with respect to the first solution. But it seems that there is no way you can relate the first solution to any subsequent solutions.
When I initially approached this problem, i was expecting that there would be some sort of pattern that could be identified in the integers that would alllow us to then automatically get values for a different set of equations. But it seems there is no predictable pattern.
Kind of line with 1, 2, 3, 4, 5, 6 etc
This sequence is simple, you always know the next integer. Just add one from the last. but when you square things, the pattern disappears, or becomes a whole lot more complex.
OK, I think this pretty much eliminates the optimization approach - that would only provide the solution closest to the initial guess, much like Newton Raphson for finding roots.Quote:
Originally Posted by Lucia333
So, it seems we need ALL solutions for:
a + b + c + d .... = t
a2 + b2 + ..... = w
where
0 < a < b < c < d ..... are integers.
I've run out of ideas. I think the brute force all possible combinations approach is the only way, perhaps optimized to eliminate many out of bounds combinations. Maybe there is some sort of stastically based search that could help limit things, but that's beyond me.
i guess its beyond me too.
It looks like we should put this one to rest :(
not currently possible to do...
I think it can be done - it's just a question of how much computation time (seconds, minutes, hours) is needed depending on problem size. If this is a 'real time' application, then you'd probably want fractions of a second......just use massively parallel computers!:D
This problem looks like a good candidate for a PhD thesis.