How to fix "largeNumber^5+1 = largeNumber^5" in Java

Question

I am searching for a, b, and c such that a^5+b^5 = c^5. My program yields 2000^5+1= 2000^5. Why is this happening and how to fix it?

public class Euler {

     public static void main(String[] args) {
        long i=0;
        int power = 5;
        int a1 = 1; 
        int a2 = 2000;

        boolean isSolved = false;
        long sumOfPowers = 0;
        double root = 0;
        long roundDown = 0;
        long roundDown2Power = 0;

            sumOfPowers = (long) (Math.pow(a1, power) + Math.pow(a2, power));
            root = Math.pow(sumOfPowers, 1.0/power);

            roundDown = (long) root;
            roundDown2Power = (long)Math.pow(roundDown, power);

            if (sumOfPowers == roundDown2Power) {
                isSolved = true;
                System.out.println(isSolved + " " + a1 + "^" + power + " + " + a2 + "^" + power + " + "  + "^" + power +  " = " + roundDown + "^" + power );
            }
        }
    }

I am searching for counterexamples of Euler's conjecture. I was successful for fifth power using this method An error searching for a counterexample to Euler's conjecture 27^5 + 84^5 + 110^5 + 133^5 = 144^5 (Lander & Parkin, 1966), it takes 6 seconds. I am trying to get 5800^4 + 217519^4 + 414560^4 = 422481^4 (Roger Frye, 1988), but when testing this module I find that my program yields 2000^5+1=2000^5. Which is a problem.

Are you aware of https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem ? — luk2302, Jun 26 '16 at 17:40
Sure, I know. I am trying to find a counterexample to https://en.wikipedia.org/wiki/Euler%27s_sum_of_powers_conjecture and I have it working for n=5, but I can't make it work for n=4 because due to rounding errors `20k^4+1=20k^4`. — sixtytrees, Jun 26 '16 at 17:47
The primitive types have a limited range of values that can be represented and in case of float/double the accuracy a value can be represented with is also limited (for integer values above n>2^52 the expression n==n+1 becomes *true*). You will need to switch to using an arbitrary precision type like e.g. BigInteger to overcome these limitations (expect a notable dip in performance, though). — Durandal, Jun 26 '16 at 18:29
BigInteger doesn't have a method to calculate roots out of the box. — sixtytrees, Jun 27 '16 at 02:06

score 0 · Answer 1 · answered Jun 26 '16 at 18:46

Your problem is a mismatch of what the types long and double can do (and are precisely defined to do) and your purely mathematical view of the equations.

The primitive types have a limited range of values that can be represented. Thats whats tripping up your calculations. The long can represent values in range Long.MAX_VALUE (2^63-1) and Long.MIN_VALUE -(2^63). The double type can represent a larger range but at the cost of accuracy. Integers represented as doubles are only accurately representable up to 2^52, above the least significant (binary) digits are dropped. Thats all because these types have a fixed size of 64 bits in memory and its impossible to represents more than 2^64 states in those bits.

The solution for your problem is not to use those types but an arbitrary precision type that can represent large number exactly without truncation or rounding. There are the BigInteger and BigDecimal classes for this purpose. Note that BigDecimal will still round (e.g. you cannot represent 1/3 with it), only you can select where to round.

Also these are object types, meaning you cannot write equations, you'll have to call their methods to perform operations with them. The available operations are also somewhat limited, requiring some problems to be rearranged to be solved.

Edit: There is nothing java specific about the behavior of the types long and double, you would have the exact same problems in any language that provides you with the same types. Double behavior is a specified standard (IEEE-754), longs properties are dictated by twos-complement rules (and its size of 64 bits).

I got it from John's comment. How do I work with BigInteger? I tried `BigInteger a = 1;` but it doesn't compile. — sixtytrees, Jun 26 '16 at 19:51
@sixtytrees As i wrote you have to call their methods, not writing equations, there is the javadoc that documents it. If that isnt enough, a simple search would find you example code like this: http://compsci.ca/v3/viewtopic.php?t=13193 — Durandal, Jun 27 '16 at 16:09

score -2 · Accepted Answer · answered Jun 26 '16 at 17:40

-2

You should try to use BigInteger lib in Java.

answered Jun 26 '16 at 17:40

John

45
2

4

That does not answer the *"why"*. And please elaborate more. (not the downvoter) – luk2302 Jun 26 '16 at 17:42
1

To get back on track @John - your answer is of very low quality. Since you did not fix that situation until now you *now* got a downvote from me too. Just shouting out a buzz word might be of help for OP but that still leaves a bad answer. Include some explanation what OP did wrong initially and how that situation can be changed by using a `BigInteger`. – luk2302 Jun 26 '16 at 20:41
@luk2302 why don't you write a good answer yourself? Just to provide an example? – sixtytrees Jun 27 '16 at 00:23
@sixtytrees because that is not what I am here for - I am / was here to moderate! I am not trying to get points or post answers. – luk2302 Jun 27 '16 at 10:54

How to fix "largeNumber^5+1 = largeNumber^5" in Java

2 Answers2