The Diophantine equations have long attracted the attention of mathematicians an
ID: 3681734 • Letter: T
Question
The Diophantine equations have long attracted the attention of mathematicians and computer scientists. Some problem instances were conjectured for centuries to be without any integral solution. For example, the 2-1 third-order Diophantine equation A3 + B3 = C 3 , a special instance of Fermat’s Last Theorem, which was proved in 1994, does not have any positive integral solution. The conjecture that a 3-1 fourthorder Diophantine equation A4 + B4 + C 4 = D4 does not have any positive integral solution, however, was disproved in 1987 by a solution 95, 8004 + 217, 5194 + 414, 5604 = 422, 4814 , thanks largely to the compute power by modern supercomputers. Many fifth-order Diophantine equations do have integral solutions. For example, the 5-1 fifth-order equation A5 +B5 +C 5 + D5 +E5 = F 5 has exactly one integral solution that satisfies 0 < A B C D E F N, where N is as small as 75. A straightforward approach to solving such equations is to first precompute all values of X5 and store them in an array. Then for each possible 5-tuple (A, B, C, D, E), check whether there exists some F such that the equation holds. To obtain a solution more efficiently, one may first sort all possible values of A5 + B5 + C 5 and F 5 (D5 + E5 ), and then determine if a number in the first group is equal to a number in the second group. This allows to asymptotically reduce the runtime from O(N5 ) to O(N3 log N). For this assignment, you will implement the (more efficient) algorithm to solve the 5-1 fifth-order equation given above for a given value for N. Your program should generate all correct solutions. Implement the MergeSort algorithm discussed in class as the sorting procedure. Name your main class EquationSolver.
Explanation / Answer
import java.util.Comparator;
import java.util.Scanner;
public class EquationSolver
{
/***********************************************************************
class EquationSolver - solves fth-order Diophantine equations smaller
than the given N in the format shown below.
input: java EquationSolver 75
output: 19 43 46 47 67 72
***********************************************************************/
public static void main(String[] args)
{
if(args.length == 0)
{
System.out.println("Proper Usage is: java EquationSolver integer");
System.exit(0);
}
Integer limit = Integer.parseInt(args[0]);
SLinkedList<Triple> abcList = new SLinkedList<Triple>();
for(int a = 1; a <= limit; a++)
{
for(int b = a; b <= limit; b++)
{
for(int c = b; c <= limit; c++)
{
long sum = (long)a*a*a*a*a + (long)b*b*b*b*b + (long)c*c*c*c*c;
Triple trip = new Triple(a, b, c, sum);
abcList.addToHead(new Node<Triple>(trip, null));
}
}
}
SLinkedList<Triple> defList = new SLinkedList<Triple>();
for(int d = 1; d <= limit; d++)
{
for(int e = d; e <= limit; e++)
{
for(int f = e; f <= limit; f++)
{
long sum = (long)f*f*f*f*f - (long)d*d*d*d*d - (long)e*e*e*e*e;
Triple trip = new Triple(d, e, f, sum);
defList.addToHead(new Node<Triple>(trip, null));
}
}
}
mergeSort(abcList, new TripleComparator());
mergeSort(defList, new TripleComparator());
findDupes(abcList, defList, new TripleComparator());
}
public static <E> void mergeSort (SLinkedList<E> in, Comparator<E> c)
{
/***********************************************************************
mergeSort() - sorts the elements of list in in nondecreasing order
according to comparator c, using the merge-sort algorithm.
***********************************************************************/
int n = in.size;
if (n < 2)
{
return; // the in list is already sorted in this case
}
// divide
SLinkedList<E> in1 = new SLinkedList<E>();
SLinkedList<E> in2 = new SLinkedList<E>();
int i = 0;
while(i < n / 2)
{
in1.addToTail(in.removeFromHead()); // move the first n/2 elements to in1
i++;
}
while(in.size != 0)
{
in2.addToTail(in.removeFromHead()); // move the rest to in2
}
// recur
mergeSort(in1, c);
mergeSort(in2, c);
// conquer
merge(in1, in2, c, in);
}
public static <E> void merge(SLinkedList<E> in1, SLinkedList<E> in2, Comparator<E> c, SLinkedList<E> in)
{
/***********************************************************************
merge() - merges two sorted lists, in1 and in2, into a sorted list in.
***********************************************************************/
while (in1.size != 0 && in2.size != 0)
{
if (c.compare(in1.head.getElement(), in2.head.getElement()) <= 0)
{
in.addToTail(in1.removeFromHead());
}
else
{
in.addToTail(in2.removeFromHead());
}
}
while(in1.size != 0) // move the remaining elements of in1
{
in.addToTail(in1.removeFromHead());
}
while(in2.size != 0) // move the remaining elements of in2
{
in.addToTail(in2.removeFromHead());
}
}
public static <E> void findDupes(SLinkedList<Triple> in1, SLinkedList<Triple> in2, Comparator<Triple> c) {
/***********************************************************************
findDupes() - finds duplicate values in two sorted lists, in1 and in2.
***********************************************************************/
int counter = 0;
while (in1.size != 0 && in2.size != 0)
{
if (c.compare(in1.head.getElement(), in2.head.getElement()) < 0)
{
in1.removeFromHead();
}
else if (c.compare(in1.head.getElement(), in2.head.getElement()) == 0)
{
if(in1.head.getElement()._z <= in2.head.getElement()._x)
{
System.out.print(in1.head.getElement()+" ");
System.out.println(in2.head.getElement());
counter++;
}
in1.removeFromHead();
}
else
{
in2.removeFromHead();
}
}
while(in1.size != 0) // remove the remaining elements of in1
{
in1.removeFromHead();
}
while(in2.size != 0) // remove the remaining elements of in2
{
in2.removeFromHead();
}
if(counter == 0)
{
System.out.println("no solution");
}
}
}
SLinkedList.java
public class SLinkedList<E>
{
/***********************************************************************
class SLinkedList - contains references to the linked list of nodes and
contains methods to operate on the linked list
***********************************************************************/
public Node<E> head; //head node
public Node<E> tail; //tail node
public int size; //size of linked list
public SLinkedList()
{
/***********************************************************************
SLinkedList() - constructor that creates an empty linked list
***********************************************************************/
head = null;
tail = null;
size = 0;
}
public void addToHead(Node<E> newHead)
{
/***********************************************************************
addToHead() - adds a node to the head of the linked list
***********************************************************************/
newHead.setNext(head);
if(head == null)
{
tail = newHead;
}
head = newHead;
size++;
}
public void addToTail(Node<E> newTail)
{
/***********************************************************************
addToTail() - adds a node to the tail of the linked list
***********************************************************************/
newTail.setNext(null);
if(tail == null)
{
head = newTail;
}
else
{
tail.setNext(newTail);
}
tail = newTail;
size++;
}
public Node<E> removeFromTail()
{
/***********************************************************************
removeFromTail() - removes a node from the tail of the linked list
***********************************************************************/
Node<E> oldTail = tail;
if(size == 1)
{
head = null;
tail = null;
}
else
{
Node<E> currentNode = head;
for(int i = 1; i < size - 1; i++)
{
currentNode = currentNode.getNext();
}
currentNode.setNext(null);
tail = currentNode;
}
size--;
return oldTail;
}
public Node<E> removeFromHead()
{
/***********************************************************************
removeFromHead() - removes a node from the head of the linked list
***********************************************************************/
Node<E> oldHead = head;
if(size == 1)
{
head = null;
tail = null;
}
else
{
head = head.getNext();
}
size--;
return oldHead;
}
@Override
public String toString()
{
/***********************************************************************
toString() - overrides the toString() method with one that prints every
element in the linked list
***********************************************************************/
String returnString = "";
Node<E> cNode = head;
while(cNode != null)
{
returnString += cNode.getElement()+" ";
cNode = cNode.getNext();
}
return returnString;
}
}
Node.java
public class Node<E>
{
/***********************************************************************
class Node - a element of a data structure that contains an char and a
reference to the next element of the data structure
(linked list)
***********************************************************************/
private E element; //integer value in the node
private Node<E> next; //next node
public Node()
{
// Node() - constructor that creates a node null values
this(null, null);
}
public Node(E s, Node<E> n)
{
// Node() - constructor that creates a node with element s and next node n
element = s;
next = n;
}
public void append(Node<E> newNode)
{
// append() - sets the next node to a different node
next = newNode;
}
public E getElement()
{
// getElement() - returns the element of the node
return element;
}
public Node<E> getNext()
{
// getNext() - returns the next node
return next;
}
public void setElement(E newElem)
{
// setElement() - sets the value of the element
element = newElem;
}
public void setNext(Node<E> newNext)
{
// setNext() - sets the next node
next = newNext;
}
}
TripleComparator.java
import java.util.Comparator;
public class TripleComparator implements Comparator<Triple>
{
/***********************************************************************
class TripleComparator - compares two triples by the value of the sums.
***********************************************************************/
@Override
public int compare(Triple o1, Triple o2)
{
/***********************************************************************
compare() - compares two triples and returns 1, 0, and -1 if the o1 is
greater than, equal to, and less than o2, repspectively
***********************************************************************/
long difference = o1._sum - o2._sum;
if(difference > 0){
return 1;
}
else if(difference == 0)
{
return 0;
}
else
{
return -1;
}
}
}
Triple.java
public class Triple
{
/***********************************************************************
class Triple - object that contains three integers, _x, _y, _z, and a
long number, _sum.
***********************************************************************/
public int _x, _y, _z;
public long _sum;
public Triple()
{
/***********************************************************************
Triple() - constructs an empty Triple.
***********************************************************************/
_x = 0;
_y = 0;
_z = 0;
_sum = 0;
}
public Triple(int x, int y, int z, long sum)
{
/***********************************************************************
Triple() - constructs a Triple with values x, y, z, and sum.
***********************************************************************/
_x = x;
_y = y;
_z = z;
_sum = sum;
}
@Override
public String toString()
{
/***********************************************************************
toString() - prints our the values of _x, _y and _z.
***********************************************************************/
return String.valueOf(_x) + " " + String.valueOf(_y) + " " + String.valueOf(_z);
}
}
sample
java EquationSolver 75
output: 19 43 46 47 67 72
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.