I thought up a math problem and want to know if my weird answer is correct. Here it is
Suppose a set of n elements. Each element is a real number.(I think I’m using the term elements correctly) What is the number of calculations needed to find if the product of 3 different elements is the same to another product of 3 different elements?
@Moonbeam , we need help with a math problem.
I’m not very good at math, but 3x3x3=27 27x27=729 (almost certainly the wrong answer).
48 x 2 x 1 = 96 3 x 4 x 8 = 96. Took me 4 calculations to think of it. But maybe you mean it’s 2 calculations.
This is probably not the most efficient algorithm… it is just brute force… But here it is.
Given three elements x, y, z in a set of n elements find three other elements a, b, c, such that:
xyz=abc
First find the product xyz - it requires two multiplication operations.
Next, there are n-3 different possibilities for a, n-4 different possibilities for b, and n-5 different possibilities for c. This is because three numbers from the set of size n where used up for x, y, z leaving n-3 elements that could be chosen for a, and so on for b and c.
Each combination requires two multiplication operations to compute. That would be (n-3)(n-4)(n-5) calculations.
Don’t know if you are counting a comparison operation as an operation. I will not since it takes a lot less time (via computer) than multiplication.
So the total number of multiplication problems to do with the brute force method is:
(n-3)(n-4)(n-5)+2
A much simpler method is to factor all of the set members. look at the factors in xyz and make the product: abc have the same factors. I don’t know how to count factorization in number of operations.
My answer was a little wierd and I don’t know if it is right which is why I was asking moonbeam as she usually is good at this stuff. First off I did n!/(3!(n-3)!) = L. Then I thought up (L-1)+(L-2)+(L-3)+…1 = (L-1)(L)/2. So I got (n^2(n-1)^2(n-2)^2-n(n-1)(n-2)6)/72.
The first part is the number of possibilities of 3 pairs that are unique. Unless I messed it up. Then the next is the number of times you need to check to see if 2 numbers in the new set are equal.
The problem is that I was expecting it to be in exponential time. It turned out to be in polynomial time. So I am wondering if I did it wrong. I came up with the problem to help me understand a more difficult problem. I don’t know where I can check to see if this is okay.
Fellow Nerdzzzz! You will have to solve this one without me. I have faith in you!
I just got home from work and am too tired to think straight. 