Prove only (pow(4,n)-1)%3=0


  • 0
    G

    0 = pow(2,0) - 1, %3 = 0

    1 = pow(2,1) -1, %3 = 1

    3 = pow(2,2) - 1, %3 = 0

    7 = pow(2,3) -1, %3 = 1

    ...

    for n=0 and 1:

    we know 2pow(4,n) -1 = N3 +1

    we get 2pow(4,n) = N3 +2

    so when n becomes n+1:

    2pow(4,n+1) -1 = 4(N3 +2) -1 = 12N +7, which %3 = 1

    Similarly,

    for n=0 and 1:

    we know pow(4,n) -1 = N*3

    when n becomes n+1:

    pow(4, n+1) - 1 = 12*N-1+1 which %3 = 0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.