fastest counting of nested loops

Question

I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example

   read number 1
   read number 2
   read final number 3

There are 17 ways how to achieve 500 with those two numbers e.g

10*2 + 15*32

and so on , the code for this is pretty simple

 i_max=final_number/number1
 j_max=final_number/number2
for(i=0;i<i_max;i++){

     for(j=0;j<j_max;j++){
             count=number1 * i;
              count_two = number 2 * j;
               if(count+count_two==final_number){
                    //print it
}
}}

This code works fine , but the problem is when i input large numbers like

number1=100
number2=500
final_number=50000000

in this case , the computer takes very long time to count/find/print all possible ways. Is there any way to make alghoritm for this as fast for big numbers too? I have found out that the better way and fastest is not to increment i by 1 but by whole number or whole number /2 and sometimes both of them ; but how can i decide if i should add whole number or just half of the number to the i/j?

I tred to write in as much in pseudo code as i could

Also , i find out the second loop does not have to start always from 0/max number everytime it gets triggered , so

for i=0 ; i<max_number1;i++
  for j=max_number2;j>=0;j--
    if number1*i + number2*j == final number
     max_number 2 = j

But i still fail to find when should i add whole number and when just half of it, I tried to increment first number by half of number2 , and second number by 1 until it finds match and then adding whole numbers , but this didnt work as i expected it worked for larger numbers but for numbers like

10 13 100 it said there is now way to combine first two and make 100 while there is a one 10 * 10 + 13 * 0

On request / for those who got lost in my explanation = i input 3 random numbers e.g 10 13 749 and i want to find out how many combinations of first two nubmers

10
13

would get result 749 it made it with nested loops

for(j=0;j<j_max;j++){
                 count=number1 * i;
                 count_two = number 2 * j;
                   if(count+count_two==final_number){
                        //print it
    }
    }}

which works but takes very long time to calculate if i input large numbers , for things i have tried or come up with read whole post.

Full example = number 1=757 number 2=989 final number = 56899148 There is 77 way how to combine first two numbers into the final one and those are

757 * 0 + 989 * 57532
 757 * 989 + 989 * 56775
 757 * 1978 + 989 * 56018
 757 * 2967 + 989 * 55261
 757 * 3956 + 989 * 54504
 757 * 4945 + 989 * 53747
 757 * 5934 + 989 * 52990
 757 * 6923 + 989 * 52233
 757 * 7912 + 989 * 51476
 757 * 8901 + 989 * 50719
 757 * 9890 + 989 * 49962
 757 * 10879 + 989 * 49205
 757 * 11868 + 989 * 48448
 757 * 12857 + 989 * 47691
 757 * 13846 + 989 * 46934
 757 * 14835 + 989 * 46177
 757 * 15824 + 989 * 45420
 757 * 16813 + 989 * 44663
 757 * 17802 + 989 * 43906
 757 * 18791 + 989 * 43149
 757 * 19780 + 989 * 42392
 757 * 20769 + 989 * 41635
 757 * 21758 + 989 * 40878
 757 * 22747 + 989 * 40121
 757 * 23736 + 989 * 39364
 757 * 24725 + 989 * 38607
 757 * 25714 + 989 * 37850
 757 * 26703 + 989 * 37093
 757 * 27692 + 989 * 36336
 757 * 28681 + 989 * 35579
 757 * 29670 + 989 * 34822
 757 * 30659 + 989 * 34065
 757 * 31648 + 989 * 33308
 757 * 32637 + 989 * 32551
 757 * 33626 + 989 * 31794
 757 * 34615 + 989 * 31037
 757 * 35604 + 989 * 30280
 757 * 36593 + 989 * 29523
 757 * 37582 + 989 * 28766
 757 * 38571 + 989 * 28009
 757 * 39560 + 989 * 27252
 757 * 40549 + 989 * 26495
 757 * 41538 + 989 * 25738
 757 * 42527 + 989 * 24981
 757 * 43516 + 989 * 24224
 757 * 44505 + 989 * 23467
 757 * 45494 + 989 * 22710
 757 * 46483 + 989 * 21953
 757 * 47472 + 989 * 21196
 757 * 48461 + 989 * 20439
 757 * 49450 + 989 * 19682
 757 * 50439 + 989 * 18925
 757 * 51428 + 989 * 18168
 757 * 52417 + 989 * 17411
 757 * 53406 + 989 * 16654
 757 * 54395 + 989 * 15897
 757 * 55384 + 989 * 15140
 757 * 56373 + 989 * 14383
 757 * 57362 + 989 * 13626
 757 * 58351 + 989 * 12869
 757 * 59340 + 989 * 12112
 757 * 60329 + 989 * 11355
 757 * 61318 + 989 * 10598
 757 * 62307 + 989 * 9841
 757 * 63296 + 989 * 9084
 757 * 64285 + 989 * 8327
 757 * 65274 + 989 * 7570
 757 * 66263 + 989 * 6813
 757 * 67252 + 989 * 6056
 757 * 68241 + 989 * 5299
 757 * 69230 + 989 * 4542
 757 * 70219 + 989 * 3785
 757 * 71208 + 989 * 3028
 757 * 72197 + 989 * 2271
 757 * 73186 + 989 * 1514
 757 * 74175 + 989 * 757
 757 * 75164 + 989 * 0

Again this works , but with very big numbers it takes lot of time to actually calculate it.

Answer 1

With inputs $n_1,n_2,n_3$, you want to find all positive integers $(a,b)$ such that $an_1+bn_2 = n_3$ You observed that for even moderately large inputs, your two nested loops with a test to see if you come up with a solution takes a long time. It you apply a bit of number theory, there's an algorithm that is very much faster.

1. First, find the greatest common divisor of $n_1$ and $n_2$. The extended euclidean algorithm is not only very fast (using a number of steps proportional to the number of digits in the larger of the two numbers), but also provides a way to do the next step. If $g=\gcd(n_1,n_2)$ divides $n_3$, continue to the next step, otherwise there will be no solutions to your problem, so quit.
2. The extended Euclidean algorithm will give you integer solutions, $a, b$ to $$ an_1+bn_2=g $$ In what follows, we'll assume $g=1$ for simplicity. If it's not, just divide $n_1,n_2,n_3$ by $g$ and carry on as below. We'll then have $$ (an_3)n_1+(bn_3)n_2 = n_3 $$ You're getting close to a solution, but $an_3$ or $bn_3$ might not both be positive, so we'll need some other solution. Observe that for any integer $k$, $$\begin{align} & (an_3-kn_2)n_1+(bn_3+kn_1)n_2\\ =&\ (an_3)n_1-kn_2n_1+(bn_3)n_2+kn_1n_2\\ =&\ (an_3)n_1+(bn_3)n_2 = n_3 \end{align}$$ so $an_3-kn_2$ and $bn_3+kn_1$ will also be solutions, for any integer $k$.
3. Now all we have to do is pick $k$ values such that $$ an_3-kn_2\ge 0\quad\text{and}\quad bn_3+kn_1\ge 0 $$ In other words, all we have to do is loop through the integers $k$ such that $$ -\frac{bn_3}{n_1}\le k\le\frac{an_3}{n_2} $$

Edit: There's a potential problem here, though: it might be that some of the intermediate calculations might be too large to avoid integer overflow. Let's see if we can keep everything no larger than $n_3$. We could let $k=a\lfloor n_3/n_2\rfloor$ and it's not hard to show that $$ a'=an_3-kn_2=an_3-a\left\lfloor\frac{n_3}{n_2}\right\rfloor n_2>0 $$ and then let $$ b'=\frac{n_3-a'n_1}{n_2} $$ we will have found a solution, $(a',b')$ to $$ a'n_1+b'n_2=n_3 $$ which was our goal.

---

Here's how it would work for an example almost like yours with $n_1=989$, $n_2=757$, $n_3=56899150$.

First, find $\gcd(989,757)=1$, and we find from the extended Euclidean algorithm that $$ 1=(62)989+(-81)757 $$ so we let $$\begin{align} a'&=62\left(56899150-757\left\lfloor\frac{56899150}{757}\right\rfloor\right)\\ &= 62(56899150-757\cdot75164)\\ &= 62(56899150-56899148)\\ &= 62\cdot 2 = 124 \end{align}$$ and we also find that $b'=75002$, so we'll have solutions $(a',b')$ given by $$\begin{array}{cc} a' & b'\\ 124 & 75002 \\ 881 & 74013 \\ 1638 & 73924 \\ \vdots & \vdots \\ 56899 & 827 \end{array}$$ where each row in the solution is the previous row solution for $a'$ plus 757 and the previous row solution for $b'$ minus 989, stopping when the $b'$ solution is negative.