public class Poly
{
	private String variableName;
	private long [] coeffs;
	private long denominator;

// Constructors

public Poly ( String polyVariableName, long [] polyCoeffs, long polyDenominator )
	{
		variableName = polyVariableName;
		coeffs = polyCoeffs;
		denominator = polyDenominator;
	}

// Debug quality printing.  Takes a polynomial and displays its coefficents.

public String debugPrint ()
	{
		String returnValue = "(";
		returnValue = returnValue + coeffs [0] + "*" + variableName + "^0";
		
		for (int i = 1; i < coeffs.length; i++)
			{ returnValue = returnValue + " + " + coeffs [i] + "*" + variableName + "^" + i; };

		returnValue = returnValue + ")/";
		returnValue = returnValue + denominator;
		return returnValue;
	}

// Special-case multiplication.  Multiplication by a coefficient.

public static Poly mulByCoeff(Poly in, long mulBy)
	{
		Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator );

		for (int i = 0; i < in.coeffs.length; i++)
			{ returnValue.coeffs[i] = mulBy * in.coeffs [i]; };

		returnValue = reduce(returnValue);

		returnValue = truncate(returnValue);

		return returnValue;
	}

// Special-case multiplication.  Division by a coefficient.

public static Poly divByCoeff(Poly in, long divBy)
	{
		Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator );

		returnValue.denominator = in.denominator * divBy;
		
		returnValue = reduce(returnValue);

		returnValue = truncate(returnValue);

		return returnValue;
	}

// Special-case multiplication.  Multiplication by "x", variableName

public static Poly mulByx(Poly in)
	{
		Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length + 1], in.denominator);
		
		returnValue.coeffs[0] = 0;
		for (int i = 0; i < in.coeffs.length; i++)
			{ returnValue.coeffs[i+1] = in.coeffs[i]; };	
		
		returnValue = reduce(returnValue);

		returnValue = truncate(returnValue);

		return returnValue;
	}

// Addition of two polynomials

public static Poly polyAdd (Poly A, Poly B)
	{
		// Determine length of coefficient array

		int lengthC = 0;

		if ( A.coeffs.length == B.coeffs.length )
			{ lengthC = A.coeffs.length; }
		else if ( A.coeffs.length > B.coeffs.length)
			{ lengthC = A.coeffs.length; }
		else
			{ lengthC = B.coeffs.length; };

		// Determine common denominator

		long denomC = A.denominator * B.denominator;

		// Create return value
		Poly C = new Poly ( A.variableName, new long [lengthC], denomC);


		// Set all coefficients to 0
		for (int i = 0; i < C.coeffs.length; i++)
				{ C.coeffs[i] = 0; };

		for (int i = 0; i < A.coeffs.length; i++)
				{ C.coeffs[i] = C.coeffs[i] + B.denominator * A.coeffs[i]; };

		for (int i = 0; i < B.coeffs.length; i++)
				{ C.coeffs[i] = C.coeffs[i] + A.denominator * B.coeffs[i]; };

		// Tidy up return value.

		C = reduce(C);

		C = truncate(C);

		return C;
	}

// Subtraction of two polynomials

public static Poly polyMinus (Poly A, Poly B)
	{
		return polyAdd(A, mulByCoeff(B,-1));
	}

// Multiplication of two polynomials

public static Poly polyTimes (Poly A, Poly B)
	{
		// Determine length of coefficient array

		int lengthC = A.coeffs.length * B.coeffs.length;

		// Determine common denominator

		long denomC = A.denominator * B.denominator;

		// Create return value
		Poly C = new Poly ( A.variableName, new long [lengthC], denomC);


		// Set all coefficients to 0
		for (int i = 0; i < C.coeffs.length; i++)
				{ C.coeffs[i] = 0; };


		for ( int i=0; i<A.coeffs.length; i++)
			{ for ( int j=0; j<B.coeffs.length; j++)
			 	{ C.coeffs[i+j] = C.coeffs[i+j] + A.coeffs[i]*B.coeffs[j];
				 };
			};

	// Tidy up return value.

		C = reduce(C);

		C = truncate(C);

		return C;
	}

// Differentiation of a polynomial

public static Poly polyDiff (Poly in)
	{
		Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length - 1], in.denominator);

		for (int i=0; i< in.coeffs.length-1 ; i++)
			{ returnValue.coeffs[i] = (i+1) * in.coeffs [i+1]; };

		returnValue = reduce(returnValue);

		returnValue = truncate(returnValue);

		return returnValue;

	}

//
// Start of utility functions called by tickable functions.
//


// Function to calculate the Highest Common Factor (Greatest Common Divisor) of 2 integers.

public static long hcf(long m, long n)
	{
            if (m == 0) return n;
            if (n == 0) return m;
            return hcf(n,m%n);
        }

// Function to reduce a polynomial to its simplest terms.

public static Poly reduce(Poly in)
	{
		Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator );
		long divisor = in.denominator;

		for (int i = 0; i < in.coeffs.length; i++)
			{  divisor = hcf(in.coeffs[i],divisor); };

		for (int i = 0; i < in.coeffs.length; i++)
			{ returnValue.coeffs[i] = in.coeffs [i] / divisor; };

		returnValue.denominator = in.denominator / divisor;

		return returnValue;
	}

// Function to truncate 0 elements from the end of the array

public static Poly truncate(Poly in)
	{
		int top = 0; 	

		for ( int i = 0; i < in.coeffs.length; i++ )
			{ if (in.coeffs[i] != 0)
				{ top = i; }
			else continue;
			};

		Poly returnValue = new Poly ( in.variableName, new long [top+1], in.denominator );

		for ( int i = 0; i < top+1; i++ )
			{ returnValue.coeffs[i] = in.coeffs[i]; };

		return returnValue;

	}

// Function to caluculate and return factorial of a number

//
// Start of Main method
//

public static void main(String[] args)
	{
		// Proof of pudding part 1:
		
        System.out.println("Proof of pudding part 1:");
		
		Poly [] P1 = new Poly[13];
		
		P1[0]= new Poly("x", new long[] {1L}, 1L);
		
		System.out.printf("P_0" + " = " + P1[0].debugPrint() + "%n");
		
		P1[1]= new Poly("x", new long[] {0L, 1L}, 1L);
		
		System.out.printf("P_1" + " = " + P1[1].debugPrint() + "%n");
		
        for (int n = 2; n < 13; n++)
        {
			Poly left = mulByCoeff(mulByx(P1[n-1]),(2*n-1));
			
			Poly right = mulByCoeff(P1[n-2],(n-1));
			
			P1[n] = divByCoeff(polyMinus(left,right), n);
			
            System.out.printf("P_%d" + " = " + P1[n].debugPrint() + "%n", n);
        }
		
		// Proof of pudding part 2:
		
        System.out.println("Proof of pudding part 2:");
			

		

        }
    }