Possibility challenge in c,c++ or Matlab

Question

I’m in need of a program that gives me the possibilities of the following equation:

x*y = 1700/57

Whereas x and y are positive reals resulting from two integers ("a" and "b") different from 1 to 300.

I tried but it didn’t work out and I don’t know where the mistake is.

int main(int argc, char *argv[]) {
    int x, i, a, b, res, xa=0, xb=0;
    int vetorA[300];
    int vetorB[300];

    for (a=0; a<=300; a++){

        for(b=0;b<=300; b++){

            if(a%b==0){// o resultado tem que ser um numero inteiro// nao sendo decimal

                xa++;
                xb++;
                a=vetorA[xa];   
                b=vetorA[xb];

            }// end if      

        }
    }


    for(i=0;i<=xa; i++){

        printf("valores de a === %d\n", vetorA[i]);

    }

    for(i=0;i<=xb; i++){

        printf("valores de b === %d\n", vetorB[i]);

    }

    return 0;
}

Answer 1

The equation to which you want to find the roots is:

x * y = 1700/57

You need, for your solution space, two real numbers x and y. But x and y are not any real numbers, they are positive reals and can be represented by the fraction of two integers a/b, whereas 1 <= a,b <= 300. Note also that x = a_x/b_x and that y = a_y/b_y, there is no equality or difference between a_x, b_x, a_y, b_y, the four integer variables being independent of each other.

It means that:

As we are assured that a_x, b_x, a_y, b_y are integer between 1 and 300 (closed), this means two things:

1. a_x * a_y = 1700
2. b_x * b_y = 57

What is basically restricted to find two splitters of 1700 both between 1 and 300, and two splitters of 57 between 1 and 300.

Splitters of 57

To find all pairs of 57 divisors between 1 and 300, we need to check which are the numbers in this range that divide 57 and then check if their counterpoint is less than 300.

I won’t demonstrate, but just go through the whole numbers in the interval [1, 57] for the variable b_x, then b_y = 57/b_x. No additional need to check b_y.

Code to find all factors b_x:

int bx_candidato;
for (bx_candidato = 1; bx_candidato <= 57; bx_candidato++) {
    if (57 % bx_candidato == 0) {
        printf("b_x %d, b_y %d\n", bx_candidato, 57/bx_candidato);
    }
}

Storing the results in a vector is for a later time

Splitters of 1700

The idea is the same as the 57 divisors, but here it is necessary to verify whether a_y <= 300. It is also necessary to search only in the interval [1,300], because it has no mathematical device to reduce the search scope.

Therefore:

int ax_candidato;
for (ax_candidato = 1; ax_candidato <= 300; ax_candidato++) {
    if (1700 % ax_candidato == 0 && 1700/ax_candidato <= 300) {
        printf("a_x %d, a_y %d\n", ax_candidato, 1700/ax_candidato);
    }
}

Storing the results in a vector is for a later time

Resolving the issue

Note that find a_x implies the existence of only one a_y, as well as b_x and b_y.

The heart of your problem you can find here:

int divisores_1700[300];
int divisores_encontrados_1700 = 0;

int divisores_57[57];
int divisores_encontrados_57 = 0;
int ax_candidato;
int bx_candidato;

for (bx_candidato = 1; bx_candidato <= 57; bx_candidato++) {
    if (57 % bx_candidato == 0) {
        divisores_57[divisores_encontrados_57] = bx_candidato;
        divisores_encontrados_57++;
    }
}

for (ax_candidato = 1; ax_candidato <= 300; ax_candidato++) {
    if (1700 % ax_candidato == 0 && 1700/ax_candidato <= 300) {
        divisores_1700[divisores_encontrados_1700] = ax_candidato;
        divisores_encontrados_1700++;
    }
}

On top of the values found, any combination of divisores_57 with divisores_1700 meets the problem. To find all these combinations:

int i, j;

for (i = 0; i < divisores_encontrados_57; i++) {
    for (j = 0; j < divisores_encontrados_1700; j++) {
        int a_x, a_y, b_x, b_y;

        a_x = divisores_1700[j];
        a_y = 1700/a_x;

        b_x = divisores_57[i];
        b_y = 57/b_x;

        printf("(%d/%d) * (%d/%d) == 1700/57\n", a_x, b_x, a_y, b_y);
    }
}

See working on ideone.

Answer 2

Despite being a computationally inefficient technique, equality (xa * xb) / (ya * yb) = 1700 / 57 can be verified by força bruta.

Are approximately 8 Bilhões of possibilities that need to be tested:

300 * 300 * 300 * 300 = 8.100.000.000

In my tests on a Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz I was able to test all possibilities in just 30ms, using the optimization flag -O3 of GCC and avoiding floating point operations (divisions) in the comparison of equality:

#include <stdio.h>

int main(void){
    int n = 0;
    int xa, xb, ya, yb;

    for( xa = 1; xa <= 300; xa++ )
        for( xb = 1; xb <= 300; xb++ )
            for( ya = 1; ya <= 300; ya++ )
                for( yb = 1; yb <= 300; yb++ )
                    if( (xa * xb == 1700) && (ya * yb == 57) )
                        printf( "[%d] ( %d * %d ) / ( %d * %d ) = 1700 / 57\n", ++n, xa, xb, ya, yb );

    return 0;
}

Compiling:

$ gcc -O3 teste.c -o teste

Testing:

$ time ./teste 
[1] ( 10 * 170 ) / ( 1 * 57 ) = 1700 / 57
[2] ( 10 * 170 ) / ( 3 * 19 ) = 1700 / 57
[3] ( 10 * 170 ) / ( 19 * 3 ) = 1700 / 57
[4] ( 10 * 170 ) / ( 57 * 1 ) = 1700 / 57
[5] ( 17 * 100 ) / ( 1 * 57 ) = 1700 / 57
[6] ( 17 * 100 ) / ( 3 * 19 ) = 1700 / 57
[7] ( 17 * 100 ) / ( 19 * 3 ) = 1700 / 57
[8] ( 17 * 100 ) / ( 57 * 1 ) = 1700 / 57
[9] ( 20 * 85 ) / ( 1 * 57 ) = 1700 / 57
[10] ( 20 * 85 ) / ( 3 * 19 ) = 1700 / 57
[11] ( 20 * 85 ) / ( 19 * 3 ) = 1700 / 57
[12] ( 20 * 85 ) / ( 57 * 1 ) = 1700 / 57
[13] ( 25 * 68 ) / ( 1 * 57 ) = 1700 / 57
[14] ( 25 * 68 ) / ( 3 * 19 ) = 1700 / 57
[15] ( 25 * 68 ) / ( 19 * 3 ) = 1700 / 57
[16] ( 25 * 68 ) / ( 57 * 1 ) = 1700 / 57
[17] ( 34 * 50 ) / ( 1 * 57 ) = 1700 / 57
[18] ( 34 * 50 ) / ( 3 * 19 ) = 1700 / 57
[19] ( 34 * 50 ) / ( 19 * 3 ) = 1700 / 57
[20] ( 34 * 50 ) / ( 57 * 1 ) = 1700 / 57
[21] ( 50 * 34 ) / ( 1 * 57 ) = 1700 / 57
[22] ( 50 * 34 ) / ( 3 * 19 ) = 1700 / 57
[23] ( 50 * 34 ) / ( 19 * 3 ) = 1700 / 57
[24] ( 50 * 34 ) / ( 57 * 1 ) = 1700 / 57
[25] ( 68 * 25 ) / ( 1 * 57 ) = 1700 / 57
[26] ( 68 * 25 ) / ( 3 * 19 ) = 1700 / 57
[27] ( 68 * 25 ) / ( 19 * 3 ) = 1700 / 57
[28] ( 68 * 25 ) / ( 57 * 1 ) = 1700 / 57
[29] ( 85 * 20 ) / ( 1 * 57 ) = 1700 / 57
[30] ( 85 * 20 ) / ( 3 * 19 ) = 1700 / 57
[31] ( 85 * 20 ) / ( 19 * 3 ) = 1700 / 57
[32] ( 85 * 20 ) / ( 57 * 1 ) = 1700 / 57
[33] ( 100 * 17 ) / ( 1 * 57 ) = 1700 / 57
[34] ( 100 * 17 ) / ( 3 * 19 ) = 1700 / 57
[35] ( 100 * 17 ) / ( 19 * 3 ) = 1700 / 57
[36] ( 100 * 17 ) / ( 57 * 1 ) = 1700 / 57
[37] ( 170 * 10 ) / ( 1 * 57 ) = 1700 / 57
[38] ( 170 * 10 ) / ( 3 * 19 ) = 1700 / 57
[39] ( 170 * 10 ) / ( 19 * 3 ) = 1700 / 57
[40] ( 170 * 10 ) / ( 57 * 1 ) = 1700 / 57

real    0m0.030s
user    0m0.030s
sys 0m0.000s