题目应该还要补充N(1) = 1, 则N(2) = 1.
函数N(n)表示n的最大奇因数
=》 如果n为奇数,则：n = n * 1 =》 N(n) = n 如N(3)=3
如果n为偶数,则：n = (n/2) * 2 =》 N(n) = N(n/2) 如N(10)=N(5)=5
Sn = N(1)+N(2)+N(3)+...+N(2^n-1)+N(2^n)
= N(1) + N(3) + N(5) + ... + N(2^n -1) + N(2) + N(4) + N(6) + ... + N(2^n) (说明：分奇数偶数)
= 1 + 3 +5 +7 + ... + (2^n -1) + N(1)+N(2)+N(3)+...+N[2^(n-1))]
= [2^(n-1) ] * (1 + 2^n -1) / 2 + N(1)+N(2)+N(3)+...+N[2^(n-1))] (等差数列求和)
= 4^(n-1) + S(n-1)
=> Sn = 4^(n-1) + S(n-1)
=> Sn - S(n-1) = 4^(n-1)
=> S(n-1) - S(n-2) = 4^(n-2)
...
=> S2- S1 = 4^1
=> Sn - S1 = 4^1 + 4^2 + ... + 4^(n-1) 当n>1时 (当n=1时, S1 = N(1)+N(2) = 2)
=> Sn = 2 + 4^1 + 4^2 + ... + 4^(n-1)
= 1 + 4^0 + 4^1 + 4^2 + ... + 4^(n-1)
= 1 + 1 * (1-4^n) / (1-4) (等比数列求和)
= 1 + (4^n -1)/3 当n>1时
综上: Sn = 1 + (4^n -1)/3 当n>0时