Euler's conjecture. In $1769$ Euler conjectured that there are no

positive integer solutions to a$4+$ b$4+$ c$4=$ d$4.$ Noam Elkies

discovered the first counterexample $26824404+153656394+$

$187967604=206156734$ over $218$ years later. Write a program to

disprove Euler's conjecture. The brute force method using Java

will take too long namely:

$($i$)$ it will take too much time to find the solution using

a quadruply nested loop, and

$($ii$)($ii$)$ computing a$4$ will overflow a long since the

smallest such counterexample is $958004+$

$2175194+4145604=4224814.$

b$.$ Use the following idea. Iterate over all integers a and b

between $1$ and N and insert a$4+$ b$4$ into a hash table. Then,

iterate over all integers c and d between $1$ and N and

search to see if d$4-$ c$4$ is in the hash table. Use extended

precision integers to avoid overflow.

c$.$ Using extended precision integers can be a significant

overhead over using primitive types. Instead of inserting

a$4+$ b$4$ into the hash table, insert a$4+$ b$4$ modulo p$,$ where p

is some big prime, say XYZ$.$ Then, iterate over all c and d

and search for d$4-$ c$4$ modulo p$.$ If there's a match, use

extended precision arithmetic to check that it isn't just an

coincidental collision. Hint: to avoid overflow when

computing a$4+$ b$4$ modulo p$,$ modulo out multiples of p

after each multiplication.

d$.$ You are welcome to use Python, due the nature of very

large data types, otherwise, use BigInteger,

BigDecimal, in Java