How to increase the time complexity of implementing Java recursion with large numbers?

Question

I have recursion

T(1) = 2 ^ k
T(2) = 2 * T(1) - 1
T(3) = 2 * T(2) - 1
T(4) = 2 * T(3) - 2
T(5) = 2 * T(4) - 4
T(6) = 2 * T(5) - 8

..

T(10) = 2 * T(9) - 128 

..

for n> = 3 we can see that:

T(n) = 2 * T(n-1) - (2 ^ (n-3))

terms:

1 <= n <= 2.000.000.000
0 <= K <= 40
k < n

Since n can be very large, I implemented this iteration recursion using BigInteger (returning the StackOverflow error function recursively), but for n = 200.000 and k = 39 the program takes 15 seconds to calculate T (n), and it should take less than 5 seconds for max (n) and max (k). I need not T (n), but T (n)% 40009, so how can I reduce this recursion?

Answer 1

will try to convert the term:

T(1) = 2 ^ k
T(2) = 2 * 2 ^ k - 1
T(3) = 2 * 2 * 2 ^ k - 2 * 1 - 1 = 2 ^ 2 * 2 ^ k - 2 ^ 1 - 1
T(4) = 2 * 2 * 2 * 2 ^ k - 2 * 2 * 1 - 2 = 2 ^ 3 * 2 ^ k - 2 ^ 2 - 2 ^ 1
T(5) = 2 * 2 * 2 * 2 * 2 ^ k - 2 * 2 * 2 * 1 - 2 * 2 - 4 = 2 ^ 4 * 2 ^ k - 2 ^ 3 - 2 ^ 2 - 2 ^ 2
T(6) = 2 * 2 * 2 * 2 * 2 * 2 ^ k - 2 * 2 * 2 * 2 * 1 - 2 * 2 * 2 - 2 * 4 - 8 = 2 ^ 5 * 2 ^ k - 2 ^ 4 - 2 ^ 3 - 2 ^ 3 - 2 ^ 3

as you can see, we can break it down into 2 terms: first:

T(n) = 2 ^ (n-1) * 2 ^ k + ... = 2 ^ (k + n - 1) + ...

second:

T(n) = ... + -2^(n-2) - (n - 2) * 2^(n-3)

:

T(n) = 2^(k + n - 1) - 2^(n-2) - (n - 2) * 2^(n-3)

modulo :

T(n) = 2^(n - 3) * (2^(k + 2) - 2^(1) - (n - 2)) = 2^(n - 3) * (2^(k + 2) - n)

modulo:

T(n) modulo 40009 = ((2^(n - 3) modulo 40009) * (2^(k + 2) - n) modulo 40009) modulo 40009

BigInteger:

static long calc(int n, int k, int m) {
    BigInteger left = new BigInteger("2");
    BigInteger nBig = new BigInteger(String.valueOf(n - 3));
    BigInteger mod = new BigInteger(String.valueOf(m));
    left = left.modPow(nBig, mod);

    BigInteger right = new BigInteger("2");
    right = right.pow(k + 2);
    right = right.subtract(new BigInteger(String.valueOf(n)));
    right = right.mod(mod);

    left = left.multiply(right);
    left = left.mod(mod);

    return left.longValue();
}

EDIT: