2

I have a number 46 which is the result of addition of 12+17+17. Is there a way, given the result 46 and 12 , 17 as the numbers used to get the result, to find out in what combination 12 and 17 was used to get the result 46

user10183910
  • 29
  • 1
  • You can relatively easy determine all solutions over the integers. If there is only one solution over the positive integers, you can recover the representation. – Peter Jan 15 '19 at 13:00
  • Not sure this is clear. For instance, If you are told you get $5$ using $2's$ and $1's$ you could have $5=2+1+1+1$ or $5=2+2+1$ , for example. – lulu Jan 15 '19 at 13:00
  • suppose the number is 169 and 12s and 17s are the numbers used.. The answer I need is its the addition of 5times17 and 7times 12.. Is there a formula to deduce this – user10183910 Jan 15 '19 at 13:04

3 Answers3

3

You could try using modulo algebra: $$n=\alpha 12 + \beta 17\implies [n]_{17}=[12]_{17}[\alpha]_{17} \implies [\alpha]_{17}=[n]_{17}([12]_{17})^{-1}=[n]_{17}[5]_{17}$$

You get $([12]_{17})^{-1}=[5]_{17}$ with the extended euclidean algorithm

This only works well because 17 is prime (or more specifically gcd(12,17)=1). So then you know $\alpha=5n + m\cdot 17$. That is already an improvement over brute force trying all whole numbers for alpha. Since 5 is a whole number (and this generalizes) $5n>n>\alpha$ so you know that m is negative and basically walk down the negative integers.

You can try playing with that approach a bit.

So pseudo algorithm:

extended euclidean algoritm yields: x,y, gcd(12,17) with 12x+12y=gcd(12,17)
if(gcd(12,17)=1)
    loop m=0,1,2... 
        try alpha=x*n-m*17 (calculate beta - is int?)
Felix B.
  • 2,425
  • Does this help, though? I can take the original, not reduce it mod $17$, and get $12 \alpha=n-17\beta$. With $n$ known, this is still $\alpha$ as a function of another unknown $\beta$. You have $\alpha$ as a function of an unknown $m$, which is still in terms of one free variable. – Randall Jan 15 '19 at 13:29
  • Yes but how would you find $\alpha$ and $\beta$ that satisfy this equation? by starting with $\alpha=1$ and incrementing and checking whether the solution for beta is an integer. With my formula you can increment over the alpha with larger steps (and also check whether beta is an integer). Or am I missing something? – Felix B. Jan 15 '19 at 13:33
  • I'm not sure that you're missing anything. It was an honest question. – Randall Jan 15 '19 at 13:35
  • And sometimes I do transformations and end up with something that just rephrases the original. Could have been my mistake too, so it is good if someone makes a sanity check. – Felix B. Jan 15 '19 at 13:39
2

If "the number is 169 and 12s and 17s are the numbers used." then you have the Diophantine equation 12x+ 17y= 169. 12 divides into 17 once with remainder 5: 17- 12= 5. 5 divides into 12 twice with remainder 2: 12- 2(5)= 2. Finally, 2 divides into 5 once with remainder 1: 5- 2(2)= 1. Replace that (2) by 12- 2(5): 5- 2(12- 2(5))= 5(5)- 2(12)= 1. Replace that (5) by 17- 12: 5(17- 12)- 2(12)= 5(17)- 7(12)= 1. Multiply by 169: 845(17)- 1183(12)= 169. So one solution is x= -1183, y= 845. But adding any multiple of 17 to x and subtracting that same multiple of 12 from y gives another solution: 12(-1183+ 17k)+ 17(845- 12k)= -14196+ 12(17)k+ 14365- 17(12)k= 169. In particular, taking k= 70 gives positive values for both x and y: x= -1183+ 17(70)= 7 and y= 845- 12(70)= 5. 169= 7(12)+ 5(17).

user247327
  • 18,710
2

Plot the line $12x+17y=46$. A point on the line with both coordinates being non-negative integers is the solution. In this case there is one such point. In general there may be none, one or many.

plot

And this solves the example from your comment:

plot2

Here the solution was not obvious. With less precision we might be led to conclusion that $(10,3)$ or $(4,7)$ was the solution. Therefore we should verify each suspected point by calculation. Still the method ruled out many values of $x$ (e.g. $12$) and many values of $y$ (e.g. $6$).

In general a problem $ax+by=c$ generates a line. You are interested in a segment from $(0, \frac c b )$ to $(\frac c a ,0)$. The larger $\frac c b$ and $\frac c a$ are, the more precise you need to be and the more points you'll find close enough to the line so you need to check them by calculation. As $\frac c b$ and $\frac c a$ grow, the method becomes unpractical.

If there are more than two solutions, they occur on the line at regular distances (exercise: why?). This observation will help you to find additional solutions (if they exist) after you find at least two.

Kamil Maciorowski
  • 2,818