Number System : 1022

Find [1/3] + [2/3] + [2²/3] + [2³/3] + ... + [2¹⁰⁰⁰/3].

 

Solution

Let f(n) = [2ⁿ/3]. Note that f(0) = f(1) = 0. 

We have 2ⁿ = (3-1)ⁿ = (-1)ⁿ mod 3, 

If n is even, then 2ⁿ/3 = f(n) + 1/3 and 

hence 2ⁿ⁺¹/3 = 2f(n) + 2/3. 

So f(n+1) = 2f(n). 

Similarly, if n is odd, f(n+1) = 2f(n) + 1. 

Thus f(2n) = 2f(2n-1)+1 = 4f(2n-2)+1. 

Put u_n = f(2n) + 1/3, then u_n = 4u_n-1. 

But u₁ = 4/3, so u_n = 4ⁿ/3.

Hence u₁ + u₂ + ... + u_n = (4/3)(1 + ... + 4^n-1) = (4/9)(4ⁿ-1). 
So f(2) + f(4) + ... + f(2n) = (4/9)(4ⁿ-1) - n/3. 
We have f(2n+1) = f(2n), so f(3) + f(5) + ... + f(2n-1) = (8/9)(4^n-1-1) - (2/3)(n-1). 
Hence f(2) + f(3) + ... + f(2n) = (2/3)(4ⁿ-1) - n.

Answer

(2/3)(2¹⁰⁰⁰-1)-500