0

Do you know a method to check if a value can be divided by a combination of integer value in a range?

For example let's say I have 100, and I want to divide it by a cobination of value between 20 and 24. in this case it is possible: 100 / 20 = 5.

But if I want to divide 100 by a combination of values between 21 and 22, I believe it does not work.

Is there a method to know if the case is possible given the value and the range?

Legisey
  • 101
  • What do you mean by "divided by a combination of integer value"? – Ove Ahlman Feb 18 '16 at 11:52
  • First of all, $\frac {100}{20}$ is not $4$. More importantly, though, what does "a combination of values" mean? If you are only talking about the integers $21,22$ then, yes...neither of those divide $100$. If you mean something else you need to write more clearly. – lulu Feb 18 '16 at 11:53
  • I mean, if you need to divide 10 by a combination of integer value between 2 and 5, you could do it, for instance, like this: 52, or 25, or 23 + 14. – Legisey Feb 18 '16 at 11:55
  • Again: What do you mean by a combination? Is it using the "normal" operations on the numbers? Are you allowed tu use a number more than once? $22-21 =1$ and $1$ divides 100. – Ove Ahlman Feb 18 '16 at 11:56
  • too broad to fit – Abr001am Feb 18 '16 at 11:58
  • 1
    Ok, I'll try a guess: Do you mean a linear combination of the integers in the range? Sticking with $21,22$ do you mean to ask: "Can we write $100$ in the form $21a+22b$ where $a,b$ are integers?" If so, do you want $a,b$ to be $≥0$? – lulu Feb 18 '16 at 12:00
  • By combination, I mean, in this case, that if you sum values that are in the range, will be able to get exactly to the target values. You can reuse the values in the range. I will edit the question with this clarification. – Legisey Feb 18 '16 at 12:02
  • Exactly @lulu, Yes I want a,b to be >0. Thank you for understanding me :) – Legisey Feb 18 '16 at 12:03
  • But do you want the non-negativity condition? That's what makes the problem hard. Without that, then all you need is for the target number to be divisible by the gcd. In your case $100=100\times (22-21)$, for example. But there's no non-negative solution. – lulu Feb 18 '16 at 12:05
  • @lulu Yes,I want a,b > 0. – Legisey Feb 18 '16 at 12:08
  • I think you mean $≥0$, no? In your first example, with $20,21,22,23,24$ you were willing to accept $100=5\times 20$ as a solution. – lulu Feb 18 '16 at 12:09
  • @lulu again you are totally right, and I lack precision in my questions. I want a,b ≥ 0. – Legisey Feb 18 '16 at 12:11
  • 1
    Assuming you meant $≥0$, this is known as the Change Making Problem (since you can think of it as changing a 100 value coin for coins of value 21, 22 and so on). It is closely related to the knapsack problem, in particular it is NP complete. You can read about it https://en.wikipedia.org/wiki/Change-making_problem or http://math.stackexchange.com/questions/1402382/coin-change-problem-with-fixed-coins/1402473 It's possible that requiring the coins to have sequential values helps...not sure about that. – lulu Feb 18 '16 at 12:15

0 Answers0