### Zlatan's blog

By Zlatan, history, 10 days ago, ,

Hey guys! My professor proposed me to solve this problme. Given a number p <= 10^7, print the sum of the digits of 2^p. For exemple, 2^4 = 16 so we'll print 7. How can I do this properly? I first tried to use in a way or in another, the little theorem of fermat but it made no sense here.

• +26

 » 10 days ago, # |   +62 Well since $2^p$ will have less than $10^7$ digits you can compute $2^p$ by using FFT with complexity $Nlog^2N$. Then you simply find the sum of the digits.
•  » » 10 days ago, # ^ |   0 So this is the only solution. I was wondering if there is a solution with math for every number not only 2
•  » » » 9 days ago, # ^ | ← Rev. 2 →   -10 I think you can do for any number N and accordingly constrain may reduce... for example- for 3^p . we can use polynomial (1+x+x^2)^p instead of (1+x)^p for 2^p case. we might use polynomial like (1+2x)^p for 3^p but it's not good bcz we will have to deal with intermediate 2^k term so we should go for such polynomial whose coefficient is 1 for all x^i, 0<=i<=n and so for k^p we can take our polynomial as (1+x+x^2+...+x^(k-1))^p for FFT means moto is if we put x=1 in polynomial then we should get k. Please correct me if I am wrong.
•  » » 10 days ago, # ^ |   -30 2^10^7 has 3010300 decimal digits which is greater than 10^7 then how can you say that 2^p is less than 10^7 ??
•  » » » 10 days ago, # ^ |   +33 3010300 has only 7 digits, how can it be larger than 10^7?
•  » » » » 10 days ago, # ^ |   -28 i didn't mean it. 2^10^7 has 3010300 digits in decimal representation.
•  » » » » » 10 days ago, # ^ |   +11 $10^{10^7}$ will have exactly $10^7 + 1$ digits and since $2 < 10$ then $2^{10^7}$ will have less than $10^7 + 1$ digits.
•  » » 10 days ago, # ^ |   +61 Even better. Realize that 1log1 + 2log2 + 4log4 + 8log8 + ... + nlogn is O(nlogn), thus your solution is O(nlogn).
•  » » » 7 days ago, # ^ |   -8 Can you please explain, why is this formula correct? Something is very wrong about it.
•  » » » » 7 days ago, # ^ |   0 N + N/2 + N/4 + N/8 + N/16 + ... converges to 2N
•  » » » » » 7 days ago, # ^ | ← Rev. 3 →   -8 Well, yeah, this one is true, but the formula must be $\sum_{i=1}^n n/i\cdot i \cdot log(i)$ for all powers of two which is $O(n\cdot log^2)$. You can even apply master theorem here $f(n)=2f(n/2)+O(nlog) = O(n\cdot log^2)$
•  » » » » » » 7 days ago, # ^ |   0 No, it's simple. All logs in that sum are at most $\log N$, so you can estimate that it's $\le 1 \log N + 2 \log N + 4\log N + \ldots + (N/2) \log N + N \log N$ $= \log N (1 + 2 + 4 + \ldots + N/2 + N)$.
•  » » » » » » » 7 days ago, # ^ |   -8 But it's not $1+2+4+...+n$, because our sum is $\sum n/i \cdot i \cdot log(i) = n \sum log(i) \geq n \cdot (log(n)/2)^2$
•  » » » » » » » » 7 days ago, # ^ |   0 What do the terms in that sum correspond to? It clearly can't be computing $2^1, 2^2, 2^3, \ldots$ step by step because each term is at least $O(N)$.
•  » » » » » » » » » 7 days ago, # ^ |   -8 My algorithm is a little different from binary exponentiation. It can multiply any $n$ short numbers, so it takes $nlog^2$. And yes, binary exponentiation will take exactly $nlog$ time.
•  » » » » » » » » » 7 days ago, # ^ |   0 Ok, so now you know that multiplying many small numbers isn't a great idea.
•  » » » » » » 7 days ago, # ^ |   0 You don't need to do two recursive calls to do binary exponentiation.Using your logic plain binary exponentiation works in $f(n)=2f(n/2)+O(1)=O(n)$
•  » » » » » » » 7 days ago, # ^ |   -8 Wait, that's illegal.How is it possible you can multiply two numbers of length $n/2$ in $O(1)$. I think the reccurence must be $f(n)=f(n/2)+O(nlog) = O(nlog)$.
•  » » » » » » » » 7 days ago, # ^ |   0 solve(n, num): if n == 1 return num else return solve(n/2, num)^2 * (n % 2 == 1 ? num : 1) or just do plain of iterative exp solve(n, num) ans = 1 while n > 0: if(n & 1) ans = ans * num num = num * num n /= 2 return ans both of these are exactly the recurrence you said.
 » 10 days ago, # |   +155 Tell your prof that in base 2 the sum of the digits is just 1
•  » » 7 days ago, # ^ |   0 Your answer seems so straight forward that I spent few minutes thinking how to compute sum of digits mod 2, just to realize that you mean't sum of digits when the number is itself in base 2 :facepalm:Is it any easy way to compute sum of digits mod 2?
 » 10 days ago, # |   +16 interesting, i like your prof
 » 9 days ago, # |   -19 you can do the computation in strings then finally add the result
•  » » 8 days ago, # ^ |   -25 Hey why the downvotes? This a totally valid solution since the question didn't specify required complexity or time limit.
•  » » » 8 days ago, # ^ |   +149 Do we need to specify every time that time limit is smaller than a few hours?
•  » » » 7 days ago, # ^ |   -10 "This a totally valid solution" — excuse me, but where do you see a solution here? Information of how to store the digits doesn't seem to me like a totally valid solution :).
•  » » » » 4 days ago, # ^ |   -10 Lol he suggested manually calculating it with biginteger strings, which, while dumb, is a solution.
•  » » 7 days ago, # ^ |   0 actually yes it tried to do it and it gives tle.