Solve A^4 + B^4 + C^4 + D^4 = E^4 recursively

Question

How do u write a algorythim to find what combinations of squares equate to each other

Asq + bsq + csq + dsq = esq

1+4+9+16=25 false too big

1+4+9+16=36 false too small

Answer 1

Don't raise all values by one; instead treat ABCD as if it were an Arabic numeral in base 100 (the "digits" are the integers 1-100 and 1 is your "zero" digit), and write code which generates all such numerals. Basically,

1. set A.B.C.D to 1.1.1.1;
2. work out the sum, search for a match in the array;
3. increment D;
4. if D is beyond 100, reset to one and increment C;
5. repeat steps 3-4 as necessary for B, then A;
6. stop when A overflows.

And, stop using doubles for integer arithmetic; use longs instead. double can exactly represent integers only up to 2^54 (or similar), whereas a long can take you to 2^64. Besides the range, using a double opens the door for false negatives (a combination of ABCD which has a solution, but your code misses it).

Answer 2

If you would like to use recursion, first you should start with creating a method that:

1. would get list of integers(Long) as input,
2. check if the input matches the condition
3. returns if matches the equation
4. else increases one of the input values
5. calls itself with increased value.

So it would look like this:

private void trySolutionRecursivly(final Long[] values) 
{
    System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
    if (conditionMet(values))
    {
        System.out.println("Met the condition!");
    }
    else
    {
        Long[] newValues = increaseValues(values);
        trySolutionRecursivly(newValues);
    }   
}

First call of that method would look like this (an array with 5 ones):

trySolutionRecursivly({1L, 1L, 1L, 1L, 1L});

But if you try to do that recursivly you'll get StackOverflowError as there are too many combinations, and so too many recursive calls (I've tried). So the only solution would be to call the method sequentially - in a loop, i.e. like this:

private void findSolution()
{
    Long[] newValues = {1L, 1L, 1L, 1L, 1L};
    while (conditionNotMet(newValues))
    {
        newValues = increaseValues(values);
    }
    System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
}

Now the trick is, to increase the values correctly.

Your problem is combination with repetition meaning that there would be (k+n-1)!/(k!(n-1)!) where k=5 and n=400(it cannot be 100;)) So in our case its: (5+400-1)!/(5!(399)!)=404!/(5!399!) and that is 400*401*402*403*404/120=87485400080 possible solutions. It's quite a lot and that's why recursive won't work here(program would have to store info about 87485400080 method calls in worst case scenario).

Now combination with repetition works as follows for 4 values and 3 places:

1;1;1
1;1;2
1;1;3
1;1;4
1;2;2
1;2;3
1;2;4
1;3;3
1;3;4
1;4;4
2;2;2
2;2;3
2;2;4
2;3;3
2;3;4
2;4;4
3;3;3
3;3;4
3;4;4
4;4;4

As you can notice everytime last index reaches 4(max value) then the second to last index will increase by one, and the last index would be set to the same value as second to last index. So the implementation would look something like this:

private Long[] increaseValues(final Long[] values) 
{
    boolean reindexed = false;
    for (int i = 0; i < values.length; i++)
    {
        if (values[i] == MAX_VALUE)
        {
            if (i > 0)
            {
                values[i-1]++;
                reindex(i, values);
                reindexed = true;
                break;
            }
            else
            {
                throw new IllegalStateException("No solution found.");
            }
        }
    }
    if (!reindexed)
    {
        values[values.length-1]++;
    }
    return values;
}

private Long[] reindex(final Integer startIndex, final Long[] values)
{
    Long startingValue = values[startIndex - 1];
    for (int i = startIndex; i < values.length; i++)
    {
        values[i] = startingValue;
    }
    return values;
}

SPOILER ALERT

So to sum up - this code will work and return you the answer. There is also commented recursive code if you would like to try that out and see what happens.

public class Main 
{
    final static int MAX_VALUE = 400;
    final static Long[] powers = new Long[MAX_VALUE + 1];

    public static void main(String args[])
    {
        final Long[] values = {1L, 1L, 1L, 1L, 1L};


        for (Integer i = 0; i <= MAX_VALUE; i++)
        {
            powers[i.intValue()] = Double.valueOf(Math.pow(i.doubleValue(), 4d)).longValue();
        }
        //new Main().trySolutionRecursivly(values);
        new Main().findSolution(values);
    }

    private void findSolution(final Long[] values)
    {
        Long[] newValues = values;
        while (conditionNotMet(newValues))
        {
            newValues = increaseValues(values);
        }
        System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
    }

    private void trySolutionRecursivly(final Long[] values) 
    {
        System.out.println("a = " + values[0] + "; b = " + values[1] + "; c = " + values[2] + "; d = " + values[3] + "; e = " + values[4]);
        if (conditionMet(values))
        {
            System.out.println("Met the condition!");
        }
        else
        {
            Long[] newValues = increaseValues(values);
            trySolutionRecursivly(newValues);
        }   
    }

    private boolean conditionNotMet(final Long[] values)
    {
        return !conditionMet(values);
    }

    private boolean conditionMet(final Long[] values)
    {
        return pow(values[0]) + pow(values[1]) + pow(values[2]) + pow(values[3]) == pow(values[4]); 
    }

    private Long pow(final Long value)
    {
        return powers[value.intValue()];
        //return Math.pow(value.doubleValue(), 4d);
    }

    private Long[] increaseValues(final Long[] values) 
    {
        boolean reindexed = false;
        for (int i = 0; i < values.length; i++)
        {
            if (values[i] == MAX_VALUE)
            {
                if (i > 0)
                {
                    values[i-1]++;
                    reindex(i, values);
                    reindexed = true;
                    break;
                }
                else
                {
                    throw new IllegalStateException("No solution found.");
                }
            }
        }
        if (!reindexed)
        {
            values[values.length-1]++;
        }
        return values;
    }

    private Long[] reindex(final Integer startIndex, final Long[] values)
    {
        Long startingValue = values[startIndex - 1];
        for (int i = startIndex; i < values.length; i++)
        {
            values[i] = startingValue;
        }
        return values;
    }
}

SPOILER

Output (it takes a while to get it - it took me about 15min):

a = 30; b = 120; c = 272; d = 315; e = 353

Here's the proof that it's correct.

PS It is actually good idea what you did - storing power values in an array. In the case with so many loops it really makes a difference. Moreover don't try to print every case - it slows the program down dramatically.