Problem: Digit Products

[Winston Gutkowski]

Piet Souris wrote:But I meant calculating permutations...

Ah, gotcha. Personally, I think I'd just use BIs and then report the way I was told to. Saves a lot of faffing around.

However, I was interested in that 'modulo (10^9 + 7)', and wondered if it might be a clue to the solution. Otherwise, why 10^9 + 7?

Well, I hope I have time to implement what I wrote about, since from tomorrow I'll be on holidays for a week, without internet

Have a great time either way,

Winston

[Stephan van Hulst]

1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer. It's to avoid that calculating the modulus will be a time consuming step in your solution. Why use a modulo at all? Because typing in more than 10 digits in an answer form can be really annoying.

[Winston Gutkowski]

Stephan van Hulst wrote:1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer.

Ah. Thanks Stephan. Still getting to grips with modular arithmetic (not least because I find the notation a bit odd); but even so, I should have thought about the possibility of a prime.

Winston

[Piet Souris]

Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.

To illustrate the method, Lets say A = 50, B = 135, T = 12.

First T is transformed into a List of IntLists (= ArrayList<Integer>, but saves a lot of typing), and [2, 6] is one of these IntLists. This IntList is converted into a Frequencty table ('FT'), (a HashMap<Integer, Integer>, but again saves much typing).

So, for this case we have A, B and FT. What happens next depends very much on the length of these components. For A and B, this is simply the number of digits, and for FT, this is the sum of the values in the Map. An enum ('AandBandT') then characterizes the situation. In the case of the given values for A, B and FT it is CASE2: |A| = |FT| < |B|.

In the method 'permutationsCASE2' it is first calculated how many permutations of 'FT' are at least equal to A. Then, for lengths |A|+1 up to and including |B|-1, ones are added to FT'and all permutations are calculated. Finally, enough ones are added to FT to make its length equal to |B|, and the number of permutations are calculated that are at most B.

Well, that's it in essence. Special tricks were necessary when |A| = |B|, where only those permutations of FT must be calculated that are between A and B (inclusive).

Do not let the length of the code scare you off. It is Java7 code, I could have seriously shortened the code, but at the expense of making a complicated program even harder to read.
And is it all correct? I've done some testing for small values for A, B and T, and that was fine (well, after quite some repairing, that is).

Two questions remain: does anyone have a better (and hopefully shorter) solution? And is there a volunteer who wants to write a brute force method to test some bigger values for A, B and T?

Finally, I don't think there is much interest in this stuff. But if anyone has some questions or spotted some bugs, send them in.
Here's the code. All I can say to the author of this problem: you have probably a much more elegant solution, so I don't think I am spoiling this problem (I hope).

/**
 *
 * @author Piet
 */
public class RamsinKoshaba {

    public static void main(String... args) {
        a(permutations("50", "12788888888888888888888888888888888888888", "128").toString(), true);
    }

    /****** to avoid the lengthy 'System.out.println()' ******************
     * 
     * @param s
     * @param asterisks 
     */
    private static void a(String s, boolean asterisks) {
        if (asterisks) {
            System.out.println("************************");
        }
        System.out.println(s);
        if (asterisks) {
            System.out.println("************************");
        }
    }

    /*********************************************************************
     * makes a copy of a FrequencyTable
     *
     * @param table a FrequencyTable
     * @return a copy of this table
     */
    private static FT copyOf(FT table) {
        FT answer = new FT();
        for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
            answer.put(entry.getKey(), entry.getValue());
        }
        return answer;
    }

     /*********************************************************************
     * Creates a FrequencyTable given an input IntList
     *
     * @param list an IntList
     * @return the corresponding FrequencyTable
     */
    private static FT makeFT(IntList list) {
        FT answer = new FT();
        for (int x : list) {
            if (!answer.containsKey(x)) {
                answer.put(x, 1);
            } else {
                answer.put(x, answer.get(x) + 1);
            }
        }
        return answer;
    }

    /*********************************************************************
     * is method returns the sum of an Iterable
     *
     * @param iter an Iterable
     * @return the sum of all its integers
     */
    private static int sumOf(Iterable<Integer> iter) {
        int answer = 0;
        for (int x : iter) {
            answer += x;
        }
        return answer;
    }

    /*********************************************************************
     * Given a Frequency table and a key, returns a new Frequency table in which
     * the value of this key is reduced by 1. If the resulting value becomes 0,
     * the key is removed. If the key is not present, then a copy of the FT is
     * returned.
     *
     * @param table the Frequency table
     * @param key the key whose value must be decreased
     * @return the modified table
     */
    private static FT decrease(FT table, int key) {
        FT answer = copyOf(table);
        if (!answer.containsKey(key)) {
            return answer;
        }
        int freq = answer.get(key) - 1;
        if (freq <= 0) {
            answer.remove(key);
        } else {
            answer.put(key, freq);
        }
        return answer;
    }

    /*********************************************************************
     * This method extends a given Frequency table with ones such, that the sum
     * of the values of this table become equal to N. The input table is not
     * affected; a copy is returned.
     *
     * @param table the input FT
     * @param N the desired sum of the values
     * @return the extended FT
     */
    private static FT extendWithOnes(FT table, int N) {
        FT answer = copyOf(table);
        int valuesum = sumOf(table.values());
        if (answer.containsKey(1)) {
            answer.put(1, answer.get(1) + N - valuesum);
        } else {
            answer.put(1, N - valuesum);
        }
        return answer;
    }

    /*********************************************************************
     * Gives the factorial of an integer, in the form of a BigInteger. It makes
     * use of a helper method.
     *
     * @param N the integer
     * @return N!
     */
    private static BigInteger factorial(int N) {
        return factorialHelp(BigInteger.ONE, N);
    }

    private static BigInteger factorialHelp(BigInteger sofar, int N) {
        if (N <= 1) {
            return sofar;
        } else {
            return factorialHelp(sofar.multiply(new BigInteger("" + N)), N - 1);
        }
    }

    /**********************************************************************
     * Given some Iterable of integers, calculates the factorial of each
     * element, and returns the product of all these factorials. For instance,
     * if the Iterable = {2, 3, 5, 5, 6} then the return value is 2! * 3! * 5! *
     * 5! * 6!
     *
     * @param iter the Iterable with integers
     * @return the product of factorials
     */
    private static BigInteger productOfFactorials(Iterable<Integer> iter) {
        BigInteger answer = BigInteger.ONE;
        for (int x : iter) {
            answer = answer.multiply(new BigInteger("" + x));
        }
        return answer;
    }

    /**********************************************************************
     * Given a Frequency table, returns the number of permutations. A standard
     * and well known function from the combinatorics is used. For instance: if
     * we have W white balls, G green and R red, then the return value = (W + G
     * + R) / (W! * G! * R!)
     *
     * @param table the frequency table
     * @return the number of permutations
     */
    private static BigInteger permutations(FT table) {
        BigInteger numerator = factorial(sumOf(table.values()));
        BigInteger denominator = productOfFactorials(table.values());
        return numerator.divide(denominator);
    }

    /*********************************************************************
     * Makes a List of IntLists, while for each of these IntLists, the product
     * of its elements equal the input parameter x. For instance, if x = 12,
     * then 3 IntLists are returned: [[2, 2, 3], [2, 6], [3, 4]] This method
     * makes use of a helper method and of recursion
     *
     * @param x a long
     * @return a List of IntLists
     */
    private static List<IntList> digitsLists(long x) {
        List<IntList> answer = new ArrayList<>();
        helpDigits(x, new IntList(), answer, 2);
        return answer;
    }

    private static void helpDigits(long x, IntList listSofar, List<IntList> answer, int start) {
        for (int digit = start; digit <= 9; digit++) {
            IntList currentList = new IntList(listSofar);
            if (x % digit == 0) {
                currentList.add(digit);
                if (x / digit == 1) {
                    answer.add(new IntList(currentList));
                } else {
                    helpDigits(x / digit, currentList, answer, digit);
                }
            }
        }
    }

    /**********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the first of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE1(String A, String B, FT table) {
        // l < a < b
        BigInteger answer = BigInteger.ZERO;
        FT temp;
        for (int length = A.length() + 1; length < B.length(); length++) {
            temp = extendWithOnes(table, length);
            answer = answer.add(permutations(temp));
        }
        temp = extendWithOnes(table, A.length());
        answer = answer.add(permutationsGivenA(A, temp));
        temp = extendWithOnes(table, B.length());
        answer = answer.add(permutationsGivenB(B, temp));
        return answer;
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the second of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE2(String A, String B, FT table) {
        // l = a < b
        BigInteger answer = permutationsGivenA(A, table);
        FT temp;
        for (int N = A.length() + 1; N < B.length(); N++) {
            temp = extendWithOnes(table, N);
            answer = answer.add(permutations(temp));
        }
        temp = extendWithOnes(table, B.length());
        answer = answer.add(permutationsGivenB(B, temp));
        return answer;
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the third of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE3(String A, String B, FT table) {
        // a < l < b
        FT temp;
        BigInteger answer = permutations(table);
        for (int N = sumOf(table.values()) + 1; N < B.length(); N++) {
            temp = extendWithOnes(table, N);
            answer = answer.add(permutations(temp));
        }
        temp = extendWithOnes(table, B.length());
        answer = answer.add(permutationsGivenB(B, temp));
        return answer;
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the fourth of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE4(String A, String B, FT table) {
        return permutationsGivenB(B, table);
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the fifth of these, this method is invoked.
     * However, no permutations are suitable, so 0 is returned (as BigInteger)
     *
     * @return BigInteger.ZERO
     */
    private static BigInteger permutationsCASE5() {
        // a < b < l
        return BigInteger.ZERO;
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the sixth of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE6(String A, String B, FT table) {
        // l < a = b
        FT temp = extendWithOnes(table, A.length());
        BigInteger a = permutationsGivenA(A, temp);
        BigInteger b = permutationsGivenB(B, temp);
        BigInteger x = permutations(temp);
        return a.add(b).subtract(x);
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the seventh of these, this method is invoked.
     *
     * @param A the bounding smaller string
     * @param B the bounding larger string
     * @param table a frequency table
     * @return the number of suitable permutations
     */
    private static BigInteger permutationsCASE7(String A, String B, FT table) {
        BigInteger a = permutationsGivenA(A, table);
        BigInteger b = permutationsGivenB(B, table);
        BigInteger x = permutations(table);
        return a.add(b).subtract(x);
    }

    /***********************************************************************
     * When given the bounding parameters A and B, and a frequency table, there
     * are 8 cases to consider. In the eighth of these, this method is invoked.
     * However, no permutations are suitable, so 0 is returned (as BigInteger)
     *
     * @return BigInteger.ZERO
     */
    private static BigInteger permutationsCASE8() {
        // a = b < l
        return BigInteger.ZERO;
    }

    /***********************************************************************
     * Given the bounding value A, gives the number of those permutations of the
     * frequency table that are at least equal to A. A precondition is that the
     * sum of the values of the table equals the length of A
     *
     * @param A the minimum value of each permutation
     * @param table the frequency table
     * @return the number of permutations that are at least equal to A
     */
    private static BigInteger permutationsGivenA(String A, FT table) {
        BigInteger answer = BigInteger.ZERO;
        boolean stillBusy = true;
        FT copy = copyOf(table);

        while (A.length() > 0 && stillBusy) {
            int x = A.charAt(0) - '0';
            Situation situation = Situation.check(x, copy);
            switch (situation) {
                case BiggerThanAllKeys:
                    // no permutation is okay
                    stillBusy = false;
                    break;
                case SmallerThanAllKeys:
                    // all permutations are okay
                    answer = answer.add(permutations(copy));
                    stillBusy = false;
                    break;
                default:
                    for (int key : copy.keySet()) {
                        if (key > x) {
                            FT temp = decrease(copy, key);
                            answer = answer.add(permutations(temp));
                        }
                    }
                    if (situation == Situation.InBetweenAndPresent) {
                        copy = decrease(copy, x);
                        A = A.substring(1);
                        if (A.length() == 0) {
                            answer = answer.add(BigInteger.ONE);
                        }
                    } else {
                        stillBusy = false;
                    }
            }
        }
        return answer;
    }

    /***********************************************************************
     * Given the bounding value B, gives the number of those permutations of the
     * frequency table that are at most equal to B. A precondition is that the
     * sum of the values of the table equals the length of B
     *
     * @param B the minimum value of each permutation
     * @param table the frequency table
     * @return the number of permutations that are at most equal to B
     */
    private static BigInteger permutationsGivenB(String B, FT table) {
        FT copy = copyOf(table);
        BigInteger answer = BigInteger.ZERO;
        boolean stillBusy = true;

        while (B.length() > 0 && stillBusy) {
            int x = B.charAt(0) - '0';
            Situation situation = Situation.check(x, copy);
            switch (situation) {
                case BiggerThanAllKeys:
                    // all permutation are okay
                    answer = answer.add(permutations(copy));
                    stillBusy = false;
                    break;
                case SmallerThanAllKeys:
                    // no permutation is okay
                    stillBusy = false;
                    break;
                default:
                    for (int key : copy.keySet()) {
                        if (key < x) {
                            FT temp = decrease(copy, key);
                            answer = answer.add(permutations(temp));
                        }
                    }
                    if (situation == Situation.InBetweenAndPresent) {
                        copy = decrease(copy, x);
                        B = B.substring(1);
                        if (B.isEmpty()) {
                            answer = answer.add(BigInteger.ONE);
                        }
                    } else {
                        stillBusy = false;
                    }
            }
        }
        return answer;
    }

    /*************************************************************************
     * Given the bounding parameters A and B, and a frequency table, gives the
     * number of permutations that are between A and B (both inclusive)
     *
     * @param A the smaller bounding parameter, as String
     * @param B the larger bounding parameter, as String
     * @param table the frequency table
     * @return the number of permutations between A (inclusive) and B
     * (inclusive)
     */
    private static BigInteger permutations(String A, String B, FT table) {
        AandBandT whichCase = AandBandT.check(A.length(), B.length(), sumOf(table.values()));
        BigInteger answer = BigInteger.ZERO;
        switch (whichCase) {
            case CASE1:
                answer = permutationsCASE1(A, B, table);
                break;
            case CASE2:
                answer = permutationsCASE2(A, B, table);
                break;
            case CASE3:
                answer = permutationsCASE3(A, B, table);
                break;
            case CASE4:
                answer = permutationsCASE4(A, B, table);
                break;
            case CASE5:
                answer = permutationsCASE5();
                break;
            case CASE6:
                answer = permutationsCASE6(A, B, table);
                break;
            case CASE7:
                answer = permutationsCASE7(A, B, table);
                break;
            case CASE8:
                answer = permutationsCASE8();
                break;
        }
        return answer;
    }

    /***********************************************************************
     * And this is the method that solves the question
     *
     * @param A the smaller bounding parameter (String)
     * @param B the larger bounding parameter (String)
     * @param T the value of T as given in the problem (String)
     * @return the number of suitable permutations, as BigInteger
     */
    public static BigInteger permutations(String A, String B, String T) {
        long t = Long.parseLong(T);
        List<IntList> lists = digitsLists(t);
        BigInteger answer = BigInteger.ZERO;
        for (IntList list : lists) {
            FT ft = makeFT(list);
            answer = answer.add(permutations(A, B, ft));
        }
        return answer;
    }

    //********** FrequencyTable ************************************************
    private static class FT extends HashMap<Integer, Integer> {

        public FT() {
            super();
        }
    }

    //*********** IntList = ArrayList of Integers ******************************
    private static class IntList extends ArrayList<Integer> {

        public IntList() {
            super();
        }

        public IntList(Collection<Integer> collection) {
            super(collection);
        }
    }

    /************************************************************************
     * An enum describing the possible situations when we compare a digit 
     * to the keys of a Frequency table. A method for this is defined as 
     * well.
     */
    enum Situation {
        BiggerThanAllKeys("BiggerThanAllKeys"),
        SmallerThanAllKeys("SmallerThanAllKeys"),
        InBetweenAndPresent("In between and present"),
        InBetweenNotPresent("in between but not present");

        private final String s;

        Situation(String s) {
            this.s = s;
        }

        public static Situation check(int x, FT table) {
            Situation answer;
            IntList list = new IntList(table.keySet());
            Collections.sort(list);
            if (x < list.get(0)) {
                answer = SmallerThanAllKeys;
            } else if (x > list.get(list.size() - 1)) {
                answer = BiggerThanAllKeys;
            } else if (list.contains(x)) {
                answer = InBetweenAndPresent;
            } else {
                answer = InBetweenNotPresent;
            }
            return answer;
        }

        @Override
        public String toString() {
            return s;
        }
    }

    /************************************************************************
     * The enum describes the 8 possibilities when given an A, B and a 
     * frequency table. Important in this is what possible lengths we have 
     * for A, B and the FT. For the different lengths, a suitable method 
     * is defined.
     */
    enum AandBandT {
        // |A| < |B|
        CASE1("|l| < |A| < |B|"),
        CASE2("|l| = |A| < |B|"),
        CASE3("|A| < |l| < |B|"),
        CASE4("|A| < |l| = |B|"),
        CASE5("|A| < |B| < |l|"),
        // |A| = |B|
        CASE6("|l| < |A| = |B|"),
        CASE7("|l| = |A| = |B|"),
        CASE8("|A| = |B| < |l|");

        private final String s;

        AandBandT(String s) {
            this.s = s;
        }

        public static AandBandT check(int a, int b, int l) {
            AandBandT answer;
            if (a < b) {
                answer = l < a ? CASE1
                        : l == a ? CASE2
                                : l < b ? CASE3
                                        : l == b ? CASE4
                                                : CASE5;
            } else {
                // a == b
                answer = l < a ? CASE6
                        : l == a ? CASE7
                                : CASE8;
            }
            return answer;
        }

        @Override
        public String toString() {
            return s;
        }
    }
}

edit: there is a big bug in the 'productOfFactorials', but its repair is trivial and left to the reader.

[Winston Gutkowski]

Piet Souris wrote:Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.

Either way, it's very impressive. I've been away from this thread for a while, so it'll probably take me a day or two to get back into the "groove", but have a cow for effort in the meantime.

Winston

[Tak Ming Laio]

public class Solution {
	private static final int[] ONE_DIGIT_PRIMES = new int[] {2,3,5,7};
	private static int[] powers;
	
	public static void main(String[] args) throws FileNotFoundException {
		Scanner in = new Scanner(new File("C:\\digitProduct\\testcase.txt"));
		int numOfCases = in.nextInt();
		
		for (int i=1; i<=numOfCases; i++) {
			BigInteger A = in.nextBigInteger();
			BigInteger B = in.nextBigInteger();
			long K = in.nextLong();
			BigInteger C = compute(A, B, K).mod(BigInteger.TEN.pow(9).add(new BigInteger("7")));
			System.out.printf("Case %d: ", i);
			System.out.println(C);
		}
		in.close();
	}
	
	/**
	 * Compute for a single test case, number of integers in the interval [A,B] whose digit product is equal to K
	 */
	public static BigInteger compute(BigInteger A, BigInteger B, long K) {
		BigInteger count = BigInteger.ZERO;
		if (!factorize(K)) return count;	// if K have factors other than single digit primes, K is not a digit product of any number
		
		// Narrow down the range [A,B] if possible

		// If A is like xxx0xxxx, can adjust the start of the range as xxx11111

		BigInteger a = A;
		String stringA = A.toString();
		int i = stringA.indexOf('0');
		if (i > 0) {
			StringBuilder sb = new StringBuilder(stringA.substring(0, i));
			for (int j=i; j<stringA.length(); j++) {
				sb.append('1');
			}
			a = new BigInteger(sb.toString());
		}
		// If B is like xxx0xxxx, can adjust the end of the range as xxy9999, where y = x-1

		BigInteger b = B;
		String stringB = B.toString();
		i = stringB.indexOf('0');
		if (i > 0) {
			b = (new BigInteger(stringB.substring(0, i))).multiply(BigInteger.TEN.pow(stringB.length() - i)).subtract(BigInteger.ONE);
		}
		if (a.compareTo(b) > 0) return count;
		
		BigInteger x = a;
		while (x.compareTo(b) <= 0) {
			if (digitProductTest(x)) {
				count = count.add(BigInteger.ONE);
			}
			x = x.add(BigInteger.ONE);
		}
		
		return count;
	}
	
	/**
	 * Try to factorize k into single digit primes, return true if and only if k has single digit prime factors only
	 * Side effect count and record the number of single digit prime factors in array powers.
	 */
	private static boolean factorize(long k) {
		powers = new int[8];
		for (long prime : ONE_DIGIT_PRIMES) {
			while (k >= prime && k % prime == 0L) {
				++powers[(int) prime];
				k /= prime;
			}
		}
		return k == 1L;
	}
	
	/**
	 * Compare prime factors of all digit of x with that of k (stored in powers) to determine whether digit product of x equal to k
	 * Return true if any only if digit product of x equal to k
	 */
	private static boolean digitProductTest(BigInteger x) {
		String stringX = x.toString();
		if (stringX.indexOf('0') > 0) return false;
		
		int[] primeDigitCounts = Arrays.copyOf(powers, powers.length);
		for (int i=0; i<stringX.length(); i++) {
			char c = stringX.charAt(i);
			if (c == '2') {
				primeDigitCounts[2]--;
				if (primeDigitCounts[2] >< 0) return false;
			} if (c == '3') {
				primeDigitCounts[3]--;
				if (primeDigitCounts[3] < 0) return false;
			} if (c == '4') {
				primeDigitCounts[2] -= 2;
				if (primeDigitCounts[2] < 0) return false;
			} if (c == '5') {
				primeDigitCounts[5]--;
				if (primeDigitCounts[5] < 0) return false;
			} if (c == '6') {
				primeDigitCounts[2]--;
				if (primeDigitCounts[2] < 0) return false;
				primeDigitCounts[3]--;
				if (primeDigitCounts[3] < 0) return false;
			} if (c == '7') {
				primeDigitCounts[7]--;
				if (primeDigitCounts[7] < 0) return false;
			} if (c == '8') {
				primeDigitCounts[2] -= 3;
				if (primeDigitCounts[2] < 0) return false;
			} if (c == '9') {
				primeDigitCounts[3] -= 2;
				if (primeDigitCounts[3] < 0) return false;
			}
		}
		if (primeDigitCounts[2] + primeDigitCounts[3] + primeDigitCounts[5] + primeDigitCounts[7] > 0) {
			return false;
		}
		return true;
	}
}

[Piet Souris]

hi Tak Ming Laio,

thank you for this program! I did some checks, and with A = 50, B = 100.000.000 and K = 128, both programs agreed on 4.257. So, I guess it is fine.

You earned a cow, but unfortunately I have no clue how to give one. So, patience!

[Stephan van Hulst]

I gave him a cow for you, Piet.

[Piet Souris]

Thank you, Stephan.

[Tak Ming Laio]

Thank you Stephan and Piet, but for very large interval [A,B], this is not a fast solution. I will try another solution when have time.