Zlatan's blog

By Zlatan, history, 10 days ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it +62 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it -10 Vote: I do not like it

      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, # ^ |
      Vote: I like it -30 Vote: I do not like it

    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, # ^ |
        Vote: I like it +33 Vote: I do not like it

      3010300 has only 7 digits, how can it be larger than 10^7?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        i didn't mean it. 2^10^7 has 3010300 digits in decimal representation.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          $$$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, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Even better. Realize that 1log1 + 2log2 + 4log4 + 8log8 + ... + nlogn is O(nlogn), thus your solution is O(nlogn).

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Can you please explain, why is this formula correct? Something is very wrong about it.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        N + N/2 + N/4 + N/8 + N/16 + ... converges to 2N

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
          Rev. 3   Vote: I like it -8 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it -8 Vote: I do not like it

              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, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ok, so now you know that multiplying many small numbers isn't a great idea.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it -8 Vote: I do not like it

              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, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                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, # |
  Vote: I like it +155 Vote: I do not like it

Tell your prof that in base 2 the sum of the digits is just 1

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +16 Vote: I do not like it

interesting, i like your prof

»
9 days ago, # |
  Vote: I like it -19 Vote: I do not like it

you can do the computation in strings then finally add the result

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    Hey why the downvotes? This a totally valid solution since the question didn't specify required complexity or time limit.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +149 Vote: I do not like it

      Do we need to specify every time that time limit is smaller than a few hours?

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      "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, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Lol he suggested manually calculating it with biginteger strings, which, while dumb, is a solution.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually yes it tried to do it and it gives tle.