How to write this algorithm in C

Question

The equation A 5+B 5+C 5+D 5+E 5=F 5 such that 0<a<=b<=c<=d<=e<f<=75 has exactly one whole solution. write a program to find it.

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main(void){
int a=1,b=1,c=1,d=1,e=1,f=2,r,f5,ac,bc,cc,dc,ec,fc;

    for(a=1;a<=b;a++){
        for(b=1;b<=c;b++){
            for(c=1;c<=d;c++){
                for(d=1;d<=e;d++){
                    for(e=1;e<f;e++){
                        f=e+1;
                        for(;f<=75;f++){
                            r=pow(a,5)+pow(b,5)+pow(c,5)+pow(d,5)+pow(e,5);
                            f5=pow(f,5);
                            if(r==f5){
                                ac=a;
                                bc=b;
                                cc=c;
                                dc=d;
                                ec=e;
                                fc=f;
                                a=b=c=d=e=f=76;
                            }
                        }
                    }
                }
            }
        }
    }
printf("A=%d,B=%d,C=%d,D=%d,E=%d,F=%d\n\n\n",ac,bc,cc,dc,ec,fc);

system("pause");
return (0);
}

That code goes into an infinite loop, my head is stuck, someone knows where the bug is?

Answer 1

There is more than one problem in your solution. Some of them:

The function pow() returns a double and this is problematic as far as because doubles are not exact and an error may occur in converting to the int and so much so because doubles have a much larger range than int and therefore conversion is dangerous.

In your case at a given time the function pow() returns a value greater than the range of int and the variables r and f5 have an undefined value. When I tested your code, both assumed the value of -2,147,483,648

This leads to the second problem, the following passage a=b=c=d=e=f=76; does not cause the conditions of the loop to be closed. In fact, the first two loops are closed, but when it comes to this for(d=1;d <= e;d++) so much d as e are equal to 76 and the loop continues infinitely.

Anyway, I corrected the main errors, but kept, in part, the logic you adopted, check out:

#include <stdio.h>
//incluido o header stdint.h para usar o tipo int64_t 
//já que em alguns momentos os valores podem 
//ultrapassar o range do tipo int
#include <stdint.h>


//essa função substitui a pow() para evitar o uso de doubles
int64_t P(int x) {
    return x * x * x * x * x;
}

int main(){
    
    int AC, BC, CC, DC, EC, FC;
    
    //iniciar pelo F ao invés do A me pareceu mais legível
    for (int F = 1; F <= 75; F++) {     
        for (int E = 1; E <= F; E++) {
            for (int D = 1; D <= E; D++) {
                for (int C = 1; C <= D; C++) {
                    for (int B = 1; B <= C; B++) {
                        for (int A = 1; A <= B; A++) {  
                            int64_t F5 = P(F);
                            int64_t R = P(A) + P(B) + P(C) + P(D) + P(E);
                            if (F5 - R == 0){
                                AC = A;
                                BC = B;
                                CC = C;
                                DC = D;
                                EC = E;
                                FC = F;
                                A = 81;// isso garante que todos os loops serão fechados
                                B = 80; // quando  a resposta correta for encontrada
                                C = 79;
                                D = 78;
                                E = 77; 
                                F = 76;
                            }
                        }
                    }
                }
            }
        }
    }

    printf("A=%d,B=%d,C=%d,D=%d,E=%d,F=%d\n",
            AC, BC, CC, DC, EC, FC);
    
    return 0;    
}

However, even solving the problem. Something bothers me in this solution. It seems to me rather inefficient because it checks all possible combinations until it finds the correct solution and it is clear that in certain circumstances many solutions can be discarded. For example, if F = 70 and E = 10, it is completely unnecessary to verify the value of the other variables since even though they have the same value as E, A 5+...+ And 5 will be smaller than F 5. So I present a version of the optimized nested loops. Check out:

//iniciar pelo F ao invés do A me pareceu mais legível
    //os trechos com continue e break servem para otimizar o algoritmo
    //as condições com continue verificam se é possível que no restante do loop R tenha o mesmo valor que F5
    //as condições com break verificam se R já não possuí um valor mais alto que F5
    for (int F = 1; F <= 75; F++) {     
        for (int E = 1; E <= F; E++) {
            if (P(F) > 5 * P(E)) continue;
            for (int D = 1; D <= E; D++) {
                if (P(F) > P(E) + 4 * P(D)) continue;
                if (P(F) < P(E) + P(D)) break;
                for (int C = 1; C <= D; C++) {
                    if (P(F) > P(E) + P(D) + 3* P(C)) continue;
                    if (P(F) < P(E) + P(D) + P(C)) break;
                    for (int B = 1; B <= C; B++) {
                        if (P(F) > P(E) + P(D) + P(C) + 2* P(B)) continue;
                        if (P(F) < P(E) + P(D) + P(C) + P(B)) break;
                        for (int A = 1; A <= B; A++) {  
                            int64_t F5 = P(F);
                            int64_t R = P(A) + P(B) + P(C) + P(D) + P(E);
                            if (F5 - R == 0) {
                                AC = A;
                                BC = B;
                                CC = C;
                                DC = D;
                                EC = E;
                                FC = F;
                                A = 81;// isso garante que todos os loops serão fechados
                                B = 80; // qunado  a resposta correta for encontrada
                                C = 79;
                                D = 78;
                                E = 77;
                                F = 76;
                            }
                            else if (F5 - R < 0) break;
                        }
                    }
                }
            }
        }
    }

And finally, I add the optimized algorithm written recursively. Check out:

#include <stdio.h>
#include <stdint.h>

int64_t P(int x) {
    return x * x * x * x * x;
}

int compare(int* S, int index, int64_t f5, int64_t sum) {
    if (index == 1) return f5 == sum ? 0 : (f5 > sum ? 1 : -1);
    else return compare(S, index - 1, f5, sum + P(S[index - 1]));
}

int solve(int* S, int index) {
    if (index == 6)
        return (compare(S, index, P(S[0]), 0) == 0);

    if (index > 1) {
        if (compare(S, index, P(S[0]), 0) == -1) return 2;
        if (compare(S, index, P(S[0]), (6 - index) * P(S[index - 1])) == 1) return 3;
    }
    
    int max = index ? S[index - 1] : 75;

    for (int i = 1; i <= max; i++) {
        S[index] = i;
        int s = solve(S, index + 1);
        if (s == 1) return 1;
        if (s == 2) break;
        if (s == 3) continue;
    }
    return  0;
}

int main(){
        
    int S[6] = { 1, 1, 1, 1, 1, 1 };
    solve(S, 0);        
    printf("A=%d,B=%d,C=%d,D=%d,E=%d,F=%d\n",
            S[5], S[4],S[3],S[2],S[1], S[0]);   
    return 0;    
}