0

I am trying to solve this excercise:

https://projecteuler.net/problem=16

The code is pretty self-explanatory: I calculate 2^n in power(n), and in sum(n), I cut off the last digit of the number. I do this as long as pow > 0. I receive the right solution for 2^15, but for one reason or another, the same code doesn't work for 2^1000. I receive 1889, which is apparently wrong.

def power(n):
    power = 2
    for x in range(1, n):
        power = 2*power
    return power

def sum(n):
    pow = power(n)
    sum = 0
    while pow > 0:
        modulo = pow%10
        sum = sum + modulo
        pow = int((pow - modulo)/10)
    return sum

def main():
    print(int(sum(1000)))

if __name__ == '__main__':
    main()
15
  • 2
    2^1000 is a ridiculously huge number. Anyway, the challenge here is to do it in a different way.
    – Eugene Sh.
    Oct 5, 2017 at 16:27
  • 3
    @alfasin no - Python uses bigint's whose limit is basically your system memory... Oct 5, 2017 at 16:27
  • 1
    @EugeneSh. It is, but Python calculates it pretty quickly.
    – Julian
    Oct 5, 2017 at 16:28
  • 1
    Mind you... having said that: %timeit sum(map(int, str(2**1000))) seems fairly quick... 61 µs ± 3.18 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) Oct 5, 2017 at 16:34
  • 1
    Weird. Cutting and pasting your code, I get 1366 every time. Not 1889.
    – Jaguar
    Oct 5, 2017 at 16:37

4 Answers 4

3

A simple change in your code will give you the correct answer,

def power(n):
    power = 2
    for x in range(1, n):
        power = 2*power
    return power

def sum(n):
    pow = power(n)
    sum = 0
    while pow > 0:
        modulo = pow%10
        sum = sum + modulo
        pow = pow//10 # modified line
    return sum

def main():
    print(int(sum(1000)))

if __name__ == '__main__':
    main()

The reason why your example doesn't work is because you are casting the result of a float operation to int. Floats are never precise and when they are very large, they loose precision. Hence if you convert them back to integer, you get a much lower value.

A better function using divmod() is,

def sum(n):
    pow = power(n)
    sum = 0
    while pow > 0:
        pow,modulo = divmod(pow,10)
        sum = sum + modulo
    return sum
1
  • I receive 1366 now, which is the correct answer. Weird. Didn't think that it would make that much of a difference, thank you!
    – Julian
    Oct 5, 2017 at 16:35
2

Your original solution would have worked in Python 2 because Python 2 and Python 3 handle division differently.

For example print(1/2) gives 0 in Python2, and 0.5 in Python3. In Python3, we use // for floor division (which is what you want here).

1

Your code doesn't work for any number >= 57

The problem here is very easy to solve.

In python 3 and higher, / is a division that returns a float, while // is an integer division that always returns an integer. Since you are using float division, you are encountering the issues with floating point arithmetic. More about the issues and limitations.

To solve your problem, change the line

pow = int(pow - modulo)/10

into

pow = int(pow - modulo)//10

or even better, you can just say pow//=10

Isn't python beatiful?

0
def Power_digit_sum(n):
    number = list(str(2**n)) # pow number and convert number  in string and  list 
    result= [int(i) for i in number]# convert number in int and 
    return sum(result) # sum list
            
        
        
 print(Power_digit_sum(15)) # result 26
 print(Power_digit_sum(1000)) # result 1366
2
  • While this code snippet may be the solution, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. Mar 8, 2021 at 17:03
  • 1
    I admit that one of my mistakes was that I forgot the comments Mar 9, 2021 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.