2015-04-29

# Problem 056: Powerful digit sum

Description:

A googol (`10^100`) is a massive number: one followed by one-hundred zeros; `100^100` 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?

Solution:
vXXX ######################################################################
XXX ######################################################################
######################################################################

>        "c"v  _v#   `*95:<
v+"I~"<\"c":<       >:55+%|
>1-:0\:"F"%v    >1-:|:-1  <
|:p/"F"\+5 <@.g1\$#2\$<
>\$188*2p020p10p>030p"~J"+>1-:::"F"%5+\"F"/g10g*20g+:55+/v
>21p > 1-:|^\$<      |:p/"F"\+5%"F":\p03+g03:%+55p02<
^g03_^#`g1># ^#2g03\$<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

Here we iterate through the values of a (1..99) and do (manually) the long multiplication.
Because we have to implement the multiplication manually we get every result from a^1 to a^99 an can easily get the digitsum for these. Then we remember the maximum digitsum and vĂ²ila, problem solved.

A few optimizations:

• We ignore values where `a%10 == 0`, because these result in numbers consisting mostly of zeroes, and those will never have a high digitsum
• We also ignore values for a<45, because the numbers are just to short to be really significant.

 Interpreter steps: 62 461 749 Execution time (BefunExec): 13s (4.49 MHz) Program size: 75 x 11 (fully conform befunge-93) Solution: 972 Solved at: 2015-04-29

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript