Home > front end >  Why does this code not give the correct result for Project Euler Question #56?
Why does this code not give the correct result for Project Euler Question #56?

Time:05-23

I'm completing the 56th question on Project Euler:

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100`, what is the maximum digital sum?

I wrote this code, which gives the wrong answer:

import math

value = 0
a = 1
b = 1


while a < 100:
    b = 1
    while b < 100:
        result = int(math.pow(a,b))
        x = [int(a) for a in str(result)]
        if sum(x) > value:
            value = sum(x)
        b = b   1
    a = a   1

print(value)

input("")

My code outputs 978, whereas the correct answer is

972

I already know the actual approach, but I don't know why my reasoning is incorrect. The value that gives me the greatest digital sum seems to be 8899, but adding together each digit in that result will give me 978. What am I misinterpreting in the question?

CodePudding user response:

You're using math.pow, which appears to be using floating point numbers internally, which don't have enough precision to get you the correct value.

So:

>>> from math import pow
>>> pow(88, 99)
3.1899548991064687e 192
>>> 88**99
3189954899106468738519431331435374548486457306565071277011188404860475359372836550565046276541670202826515718633320519821593616663471686151960018780508843851702573924250277584030257178740785152
>>> int(pow(88, 99))
3189954899106468677983468001676918389478607432406058411199358053788184470654582587122118156926366989707830958889227847846886750593566290713618113587727930256898153980172821794148406939795587072

Converting pow(88, 99) back to an integer does give you an int value that's similar, but it's not the same, and happens to have 978 as a sum of its digits.

CodePudding user response:

As earlier post your misuse of pow, you could simplify your code just modify a little bit:

Try to use built-in range to loop over directly instead of using while-loop can make the code more compact and readable.

ans = 0

for a in range(100):
    for b in range(100):
        #ds = sum(int(digit) for digit in str(a**b))
        ds = sum(map(int, str(a ** b)))      # faster
        if ds > ans:
            ans = ds
print(ans)
  • Related