5

This is my code in python but the answer it gives is not correct according to projecteuler.net.

a = 2**1000
total = 0
while a >= 1:
    temp = a % 10
    total = total + temp
    a = int(a/10)
print(total)

It gives an output 1189. Am I making some mistake?

Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
Riptide
  • 472
  • 3
  • 14
  • Have a look [here](https://www.quora.com/How-do-you-find-the-sum-of-the-digits-of-2-1000) – Jeroen Heier Jul 15 '18 at 06:42
  • @abccd That question is relevant, and there's good info there in the answers and comments, but I don't think it's close enough to this question to use it as a duplicate target. – PM 2Ring Jul 15 '18 at 07:16
  • @PM2Ring your answer's great. When I left the link, I was hoping to see if the community think if it's a dupe if not, a relevant post. I guess the verdict (at least by two other voters) was it's a close-enough dupe. Feel free to spark a reopen vote:) – Taku Jul 15 '18 at 15:27
  • @abccd I could re-open it by myself. It doesn't bother me too much that others wanted to close it with that dupe target, although I'd prefer it if a better matching question was the target. – PM 2Ring Jul 15 '18 at 15:39

1 Answers1

7

Your logic is fine. The problem is that 2 ** 1000 is too big for all the digits to fit into a float, so the number gets rounded when you do a = int(a/10). A Python float only has 53 bits of precision, you can read about it in the official tutorial article: Floating Point Arithmetic: Issues and Limitations, and on Wikipedia: Double-precision floating-point format. Also see Is floating point math broken?.

This is 2 ** 1000

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

But print(format(2**1000 / 10, 'f')) gives us this:

1071508607186267380429101388171324322483904737701556012694158454746129413355810495130824665231870799934327252763807170417136096893411236061781867579266085792026680021578208129860941078404632071895251811587214122307926025420797364998626502669722909817741077261714977537247847201331018951634334519394304.000000

You can see that the digits start going wrong after 10715086071862673.

So you need to use integer arithmetic, which in Python has arbitrary precision (only limited by how much memory Python can access). To do that, use the // floor division operator.

a = 2**1000
total = 0
while a >= 1:
    temp = a % 10
    total = total + temp
    a = a // 10
print(total)

output

1366

We can condense that code a little by using augmented assignment operators.

a = 2**1000
total = 0
while a:
    total += a % 10
    a //= 10
print(total)

Here's a faster way. Convert a to a string then convert each digit back to int and sum them. I use bit shifting to compute a because it's faster than exponentiation.

print(sum(int(u) for u in str(1 << 1000)))
PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
  • Won't any errors or warning be shown? It's an overflow, right? – J...S Jul 15 '18 at 06:58
  • 1
    @J...S: Python ints are arbitrary-precision. – user2357112 Jul 15 '18 at 06:58
  • @user2357112 But PM said something about number being too big to fit in a float. – J...S Jul 15 '18 at 07:01
  • @J...S 2**1000 is not too large in magnitude for a float in python, but it does require more bits to store exactly than a python float provides, so the result is erroneous but does not throw an exception. – Dillon Davis Jul 15 '18 at 07:03
  • @DillonDavis Meaning there will be an precision error or something? – J...S Jul 15 '18 at 07:04
  • @J...S When we do `2 ** 1000` or `1 << 1000` only integer arithmetic is involved, so we don't have any problems with overflow. – PM 2Ring Jul 15 '18 at 07:07
  • @J...S there exists no precision exception AFAIK. It will just return the incorrect / approximate value in all further arithmetic operations. – Dillon Davis Jul 15 '18 at 07:07
  • @PM2Ring I understand that now. But can you tell me why the `float` version is different? – J...S Jul 15 '18 at 07:10
  • @J...S By example: `val = (1 << 1000) / 1.0` => `1.0715086071862673e+301`, `val + 1` => `1.0715086071862673e+301`, no errors thrown. – Dillon Davis Jul 15 '18 at 07:13
  • 3
    @J...S Because a float can only hold 53 bits of precision, which is not enough to accurately represent a number with 1001 bits. – PM 2Ring Jul 15 '18 at 07:13
  • Ah, I see. Thank you! – J...S Jul 15 '18 at 07:15
  • Perhaps clarify that floating point arithmetic is limited precision by definition. There would be a warning for nearly every floating-point operation if we were to receive warnings for rounding. – tripleee Jul 15 '18 at 08:40
  • @tripleee Good idea, I've added a little more info & a couple of links, but I don't want to turn this answer into a tutorial on floating-point. – PM 2Ring Jul 15 '18 at 08:51