/******************************************************************************
                           Code by AngelAtheist
         Run with https://www.onlinegdb.com/online_java_compiler
*******************************************************************************/

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Main
{
    public static void main(String[] args) {
                Long startTime = System.currentTimeMillis();
        List<BigInteger> fractions = new ArrayList<BigInteger>();
        //fractions.add(new BigInteger("17"));
        fractions.add(new BigInteger("19"));
        fractions.add(new BigInteger("23"));
        fractions.add(new BigInteger("29"));
        fractions.add(new BigInteger("31"));
        // 34
        fractions.add(new BigInteger("37"));
        // 38
        fractions.add(new BigInteger("41"));
        fractions.add(new BigInteger("43"));
        // 46
        fractions.add(new BigInteger("47"));
        // 51
        fractions.add(new BigInteger("53"));
        // 57
        // 58
        fractions.add(new BigInteger("59"));
        fractions.add(new BigInteger("61"));
        // 62
        BigInteger largePrimeProduct = new BigInteger("1");
        for (BigInteger fraction : fractions) {
            largePrimeProduct = largePrimeProduct.multiply(fraction);
        }
        BigInteger denominator = new BigInteger("1");
        for (int i = 2; i <= 64; i++) {
            BigInteger factor = new BigInteger(String.valueOf(i));
            BigInteger gcd = denominator.gcd(factor);
            denominator = denominator.multiply(factor).divide(gcd);
        }
        System.out.println("full denominator is " + denominator.toString());
        //fractions.add(5, new BigInteger("34")); // 17*2
        fractions.add(5, new BigInteger("38")); // 19*2
        fractions.add(8, new BigInteger("46")); // 23*2
        //fractions.add(12, new BigInteger("51")); // 17*3
        fractions.add(11, new BigInteger("57")); // 19*3
        fractions.add(12, new BigInteger("58")); // 29*2
        fractions.add(new BigInteger("62")); // 31*2
        List<BigInteger> partials = new ArrayList<BigInteger>();
        for (BigInteger fraction : fractions) {
            BigInteger partial = denominator.divide(fraction);
            partial = partial.mod(largePrimeProduct);
            partials.add(partial);
        }

        BigInteger lowestMatch = largePrimeProduct;

        for (int bits = 0; bits < Math.pow(3, fractions.size()); bits++) {
            BigInteger sum = BigInteger.ZERO;
            for (int index = 0; index < fractions.size(); index++) {
                int bitVal = (bits / (int)Math.pow(3, index)) % 3;
                if (bitVal < 0) {
                    bitVal = bitVal + 3;
                }
                if (bitVal == 2) {
                    sum = sum.add(partials.get(index));
                } else if (bitVal == 1) {
                    // do nothing
                } else {
                    sum = sum.subtract(partials.get(index));
                }
            }
            BigInteger sumRes = sum.mod(largePrimeProduct);
            if (sumRes.compareTo(lowestMatch) != 1 && !sumRes.equals(BigInteger.ZERO)) {
                // repeat the bit computation, getting the fraction values for printing purposes
                String printString = "sum of " + sumRes + " found with ";
                for (int index = 0; index < fractions.size(); index++) {
                    int bitVal = (bits / (int)Math.pow(3, index)) % 3;
                    if (bitVal < 0) {
                        bitVal = bitVal + 3;
                    }
                    if (bitVal == 2) {
                        printString = printString + "+" + fractions.get(index) + ",";
                    } else if (bitVal == 1) {
                        printString = printString + "0" + fractions.get(index) + ",";
                    } else {
                        printString = printString + "-" + fractions.get(index) + ",";
                    }
                }
                System.out.println(printString);
                lowestMatch = sumRes;
            }
        }
        BigInteger fractionInverse = denominator.divide(lowestMatch);
        Long endTime = System.currentTimeMillis();
        Long duration = (endTime - startTime) / 1000;
        Long durationSeconds = duration % 60;
        if (durationSeconds < 0) {
            durationSeconds += 60;
        }
        Long durationMinutes = duration / 60;
        System.out.println("ran and found lower bound of approximately 1/" + fractionInverse);
        System.out.println("it took " + durationMinutes + " minutes and " + durationSeconds + " seconds");
    }
}