python - Sum of digits in 2^1000? [duplicate]

Question

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?

Answer 1

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)))