How can I calculate 2^n+2^n-1+...+2^k mod 2^60 in C++, where the value of 2^i can be very big?

Question

For a programming question I have to print the expression 2^n+2^n-1+...+2^k mod 2^60, where 1<=k<n<=240?

Basically, how can I calculate 2^240 mod 2^60? If this can be solved, I can make it work for n<240 as well!

I read an answer here: How can I calculate 2^n for large n?

But, that calculates for large values of n and not 2^n.

Any help?

Answer 1

2^k + 2^k+1 + ... + 2^n-1 + 2^n mod 2^60

=

2^k * (2^0 + 2^1 + ... + 2^n-k-1 + 2^n-k) mod 2^60

=

2^k * ((2^n-k+1)-1) mod 2^60

=

(2^n+1 - 2^k) mod 2^60

=

(2^n+1 mod 2^60 - 2^k mod 2^60) mod 2^60

• k >= 60: result is 0 because both 2^n+1 and 2^k can be divided by 2^60
• k < 60:
  • n >= 59: result is -2^k
  • n < 59: result is 2^n+1 - 2^k

Because of the conditions, all those numbers can be calculated because fit properly on a long variable (64 bits).