Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js


I_LOVE_ROMANIA's blog

Sum digits of 2^p with p<=10.000.000
By I_LOVE_ROMANIA, history, 5 years 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

Comments Comments (27)
| Write comment?
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Well since 2p will have less than 107 digits you can compute 2p by using FFT with complexity Nlog2N. Then you simply find the sum of the digits.

→ Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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 ??

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          10107 will have exactly 107+1 digits and since 2<10 then 2107 will have less than 107+1 digits.

          → Reply
  • »
    »
    5 years 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).

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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 ∑ni=1n/i⋅i⋅log(i) for all powers of two which is O(n⋅log2). You can even apply master theorem here f(n)=2f(n/2)+O(nlog)=O(n⋅log2)

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No, it's simple. All logs in that sum are at most logN, so you can estimate that it's ≤1logN+2logN+4logN+…+(N/2)logN+NlogN =logN(1+2+4+…+N/2+N).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              But it's not 1+2+4+...+n, because our sum is ∑n/i⋅i⋅log(i)=n∑log(i)≥n⋅(log(n)/2)2

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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 21,22,23,… step by step because each term is at least O(N).

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years 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 nlog2. And yes, binary exponentiation will take exactly nlog time.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years 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.

                  → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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).

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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.

                → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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?

    → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

interesting, i like your prof

→ Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
    • »
      »
      »
      5 years 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 :).

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply