-2

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?

Ansh Shrivastava
  • 73
  • 7
  • 8
    `2^240 mod 2^60` = 0 – mvp Oct 04 '20 at 10:25
  • 1
    Does this: https://en.wikipedia.org/wiki/Modular_exponentiation help you? Basically: 1. You can do each summand separately anyway, 2. (a*b) mod m = (a mod m)*(b mod m) mod m – Aziuth Oct 04 '20 at 10:36
  • @Aziuth I don't think that's very useful in this context – harold Oct 04 '20 at 10:58
  • 2^n is just 1 followed by n zeroes. You could do it as a string. – stark Oct 04 '20 at 11:12
  • 2
    All the powers > 60 come out to 0 mod 2^60, so you can just ignore them. The other ones can be calculated with a left shift in a 64-bit int. Easy. Probably what you're asking for is not really what you want. – Matt Timmermans Oct 04 '20 at 13:11
  • @Matt Timmermans So, any power of 2 greater than 2^60 when mod by 2^60 comes out zero because it is totally divisible, right? Also, How to do that 64bit int thing? – Ansh Shrivastava Oct 04 '20 at 13:48

1 Answers1

2
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).

Mariano Demarchi
  • 339
  • 1
  • 5