# Euler.java

Below is the syntax highlighted version of Euler.java from §5.6 Cryptography.

```/******************************************************************************
*  Compilation:  javac Euler.java
*  Execution:    java Euler N
*
*  Tests whether there are any four positive integers that satisfy
*  a^4 + b^4 + c^4 = d^4. Euler conjectured that no such solutions
*  exists, but his conjecture was later disproved.
*
*  Mathematical shortcut: can assume
*     - a is a multiple of 8
*     - b is a multiple of 40
*     - d-1 is a multiple of 8
*     - either c+d is a multiple of 1024 or d-c is a multiple of 1024
*     - d is not a multiple of 5
*
*  % java -Xmx900MB -Xms900MB Euler 500000
*  95800^4 + 414560^4 + 217519^4 = 422481^4
*  109208^4 + 367120^4 + 259225^4 = 481433^4
*  137992^4 + 167600^4 + 32639^4 = 246913^4
*  138688^4 + 332520^4 + 330537^4 = 421673^4
*  414560^4 + 95800^4 + 217519^4 = 422481^4
*
*  This takes approximately 75 minutes and used 736MB of memory.
*
*  Known bugs:
*  -----------
*  -  Only the first solution actually is valid, the others
*     satisfy a^4 + b^4 = d^4 - c^4 (mod 2^64). These numbers should
*     be checked with extended precision arithmetic.
*  -  It is possible, but extremely unlikely, that we miss a solution.
*     This could happen if two values of d^4 - c^4 are equal (mod 2^64)
*     AND d^4 - c^4 is equal to a^4 + b^4 (mod 2^64)  AND the first
*     (d, c) pair does not form a valid solution with (a, b) AND
*     the second (d, c) pair does. We could modify the hash search
*     function to return all items with a given sum, but this seems
*     like overkill.
*
*
******************************************************************************/

public class Euler {
static long[] four;       // table of fourth powers
static Item[] st;         // symbol table - hash table

static int hash(long sum) { return (int) (sum) >>> 7; }

/***************************************************************************
*  Insert item into ST.
***************************************************************************/
static void insert(Item x) {
int i = hash(x.sum);
while (st[i] != null) {
i++;
if (i >= st.length) i-= st.length;
}
st[i] = x;
}

/***************************************************************************
*  Search ST for given key.
***************************************************************************/
static Item search(long sum) {
int i = hash(sum);
while (st[i] != null) {
if (st[i].sum == sum) return st[i];
i++;
if (i >= st.length) i-= st.length;
}
return null;
}

/***************************************************************************
*  Item to store in hash table.
***************************************************************************/
private static class Item {
int d, c;
long sum;    // d^4 - c^4  (mod 2^64)

Item(int d, int c, long sum) { this.d = d; this.c = c; this.sum = sum; }
}

public static void main(String[] args) {
int N = Integer.parseInt(args);
long a4, b4, c4, d4;
st = new Item;   // 2^25

/**************************************************************
* Precompute i^4 (mod 2^64) by relying on fact that overflow
* of long in Java is automatically done this way.
**************************************************************/
long[] four = new long[N+1];
for (int i = 0; i <= N; i++) {
four[i] = i;
four[i] *= four[i];
four[i] *= four[i];
}
StdOut.println("Done precomputing table of fourth powers");

/**************************************************************
* Enumerate of all pairs (c, d) and put d^4 - c^4 (mod 2^64)
* in a hash table along with c and d.
**************************************************************/
for (int d = 1; d < N; d += 8) {
if (d % 5 == 0) continue;
d4 = four[d];
for (int c = d % 1024; c < d; c += 1024) {
c4 = four[c];
insert(new Item(d, c, d4 - c4));
}
for (int c = 1024 - d % 1024; c < d; c += 1024) {
c4 = four[c];
insert(new Item(d, c, d4 - c4));
}
}

StdOut.println("Done building hash table");

/**************************************************************
* Enumerate of all pairs (a, b) and search in a hash table
* for a^4 + b^4 (mod 2^64). If match, perform full precision
* check to see if a^4 + b^4 = d^4 - c^4
**************************************************************/
for (int a = 8; a < N; a += 8) {
a4 = four[a];
if (a % 10000 == 0) StdOut.println(a);
for (int b = 40; b < N; b += 40) {
b4 = four[b];
if (search(a4 + b4) != null) {
Item item = search(a4 + b4);
StdOut.print(a + "^4 + " + b + "^4 + ");
StdOut.println(item.c + "^4 = " + item.d + "^4");
}
}
}

}
}
```