5
$\begingroup$

I am neither a mathematician nor do I have an idea on how to write down my problem in accurate mathematic formulas. Please feel free to edit my question into shape and remove this paragraph. Also I am unsure about that tags that apply to this question - fits, but maybe there are others?

Given a set of natural numbers: [125, 70, 55] and a total of 250 (All of these numbers may vary).

Now I need to find the integral factors to the numbers that add up to the total like this:

125*a + 70*b + 55*c = 375

Is there a mathematical solution to this problem or do I have to find out the brute force way?

For this example there is more than one valid solution:

  • a = 3, b = 0, c = 0
  • a = 2, b = 1, c = 1
  • a = 1, b = 2, c = 2
  • a = 0, b = 3, c = 3
  • a = 0, b = 1, c = 5
  • maybe others...

My goal is it to find all possible solutions - or at least more than one of them.

I already tried some brute force algorithms, but none of them is fast enough to find a solution to this problem for lager numbers.

$\endgroup$
16
  • 1
    $\begingroup$ So, you want to find the possible values of $a,b,c$? $\endgroup$
    – Prasun Biswas
    Mar 25, 2015 at 20:35
  • $\begingroup$ @PrasunBiswas yes. $\endgroup$
    – Spontifixus
    Mar 25, 2015 at 20:38
  • $\begingroup$ @Zach466920, That doesn't always work since you may get a non-integral value of $c$ that way. $\endgroup$
    – Prasun Biswas
    Mar 25, 2015 at 20:38
  • $\begingroup$ @Spontifixus, use the Extended Euclidean Algorithm $\endgroup$
    – Prasun Biswas
    Mar 25, 2015 at 20:39
  • $\begingroup$ @PrasunBiswas missed that part deleted the comment $\endgroup$
    – Zach466920
    Mar 25, 2015 at 20:40

1 Answer 1

Reset to default
0
$\begingroup$

Just to make things simpler. I'll assign each number a name: 125: a number 70: b number 55: c number 375:final number

1.Split all the number into their prime factors except for your final number:

5x5x5+2x5x7+11x5=375
  1. Take the total of their numbers away from your final number (375) and find the prime factors of that.

375-250=125

5x5x5=125

125 will be called: subtracted number

Now there are multiple 'tests' to be done.

a) Do any of the number's prime factors match the prime factors of the subtracted number

Yes, a number matches 125 once.

That collects up, meaning that number needs to occur twice for the numbers to add up to 375. Since we didn't do anything to the other numbers, they remain as value 1.

Note: If the subtracted number contained the prime factors (perfectly) of number a, b or c multiple times, a,b, or c will be equal to however many times they match up (plus 1). For example. If number a's prime factor was 5. It would take 3 a's to equate to the subtracted number

Note 2: If two or three of the numbers (a,b or c)combined match up to the subtracted number's prime factor, do the same thing you did in the test:

-2x5x7+11x5=125
-prime factors of 125=5x5x5
-therefore
5x5x5+5x5x5=375

As we know 5x5x5 matches with the prime factors of our subtracted number. So we increase the numbers b and c (we totalled together) by one. So b is and so is c.

b) If you've finished test a, re-do it except add each number to the subtracted number and give their multiplier (a,b or c) a value of 0. Once you have done that, do it with every possible pair of the three numbers

If you feel I've answered your questioo=n. Please tick the box. ALL of the combinations are below:

a=2, b=1, c=1
a=3, b=0 c=0
a=1, b=2, c=2
a=0., b=3, c=3
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .