Project Euler #16 on Python

Question

import math

def sumOfDigit(num):
    sum_of_digits = 0
    while num > 9:
        sum_of_digits += num % 10
        num = int(num/10)
    sum_of_digits += num
    return sum_of_digits

print sumOfDigit(math.pow(2,1000))

This is what I thought of for Project Euler #16, and it works fine for smaller numbers. But when I tried 2¹⁰⁰⁰, the code gave me 1289.0 instead of the answer 1366 (Found this on the internet). I think the problem might have to do with the size of the number, but I'm not sure. Any points in the right direction will be appreciated. Thanks in advance!

Edit: Here is the question https://projecteuler.net/problem=16

Please include what you are trying to achieve in the question, not as an external link. — Thierry Lathuille
– Thierry Lathuille, Commented Jul 26, 2017 at 8:34

Elisha · Accepted Answer · 2017-07-26 09:03:34Z

5

The reason is that math.pow(2,1000) returns a float and not an int. Therefore, the operation num/10 returns a different answer than expected.

When calling with 2 ** 1000 the expected answer is returned.

Edit: in case of python 3, please note Hans comment or tobias_k answer regarding integers division.

edited Jul 26, 2017 at 9:03

answered Jul 26, 2017 at 8:39

Elisha

23.8k6 gold badges65 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Hans Over a year ago

With a Python 3.5.2, I just got the same problem even when using 2**1000 as the argument; I had to - additionally - use floor division in the reduction step to get the right result: num = num//10

tobias_k · Accepted Answer · 2017-07-26 08:41:27Z

1

The problem is that math.pow returns a floating point number, and for that large a number, the floating point precision is not good enough to give you a precise answer. Change your function like this:

def sumOfDigit(num):
    sum_of_digits = 0
    while num > 9:
        sum_of_digits += num % 10
        num = num // 10  # use integer division // instead of /
    sum_of_digits += num
    return sum_of_digits

print(sumOfDigit(pow(2, 1000))) # use builtin pow or ** operator instead of math.pow

Or shorter:

print(sum(int(c) for c in str(2**1000)))

answered Jul 26, 2017 at 8:41

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Comments

moritzg · Accepted Answer · 2017-07-26 08:37:25Z

0

I'd say that your number calculation is simply wrong. It can be achieved much easier:

import math

number = str(int(math.pow(2,1000)))
total = 0

for i in number:
    total += int(i)

print(total) #1366

Simply calculate the result of 2¹⁰⁰⁰, convert it to str and go through the numbers to sum them up.

answered Jul 26, 2017 at 8:37

moritzg

4,4145 gold badges41 silver badges63 bronze badges

4 Comments

Gribouillis Over a year ago

Unexpectedly, this works. I don't understand how int(math.pow(2, 1000)) could find all the digits as math.pow(2, 1000) is a float. Do you have an explanation ?

tobias_k Over a year ago

@Gribouillis Might have something to do that it's a power of two and thus can be represented exactly even as a floating point number.

Gribouillis Over a year ago

@tobias_k Indeed the ieee754 representation of 2**1000 on 64 bits is 0 11111100111 0000000000000000000000000000000000000000000000000000. All the information is in the exponent. It is an exact number.

Hans Over a year ago

As Elisha notes, the problem is not strictly the floating point representation of math.pow, but the division by 10 in the loop which gets a wrong result on the float.

Anıl Karakulak · Accepted Answer · 2018-11-20 07:59:30Z

0

Without math module, basically can be done like this:

a=list(str(2**1000))
b=0
for i in range(0,len(a)):
b+=int(a[i])
print(b)

answered Nov 20, 2018 at 7:59

Anıl Karakulak

337 bronze badges

Collectives™ on Stack Overflow

Project Euler #16 on Python

4 Answers 4

1 Comment

Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related