mercredi 2 janvier 2019

Given (a, b) compute the minimum value of k such that a^{1/k} and b^{1/k} are whole numbers

I'm writing a program in C++ that tries to find the minimum value of k > 1 such that the kth root of a and b (which are both given) equals a whole number.

Here's a snippet of my code, which I've commented for clarification.

int main()
{
    // Declare the variables a and b.
    double a;
    double b;
    // Read in variables a and b.
    while (cin >> a >> b) {

        int k = 2;

        // We require the kth root of a and b to both be whole numbers.
        // "while a^{1/k} and b^{1/k} are not both whole numbers..."
        while ((fmod(pow(a, 1.0/k), 1) != 1.0) || (fmod(pow(b, 1.0/k), 1) != 0)) {

        k++;

        }

Pretty much, I read in (a, b), and I start from k = 2 and increment k until the kth roots of a and b are both congruent to 0 mod 1 (meaning that they are divisible by 1 and thus whole numbers).

But, the loop runs infinitely. I've tried researching, and I think it might have to do with precision error; however, I'm not too sure.

Another approach I've tried is changing the loop condition to check whether the floor of a^{1/k} equals a^{1/k} itself. But again, this runs infinitely, likely due to precision error.

Does anyone know how I can fix this issue?

EDIT: for example, when (a, b) = (216, 125), I want to have k = 3 because 216^(1/3) and 125^(1/3) are both integers (namely, 5 and 6).

Aucun commentaire:

Enregistrer un commentaire