Powerful digit sum
2015-04-29
Problem 056: Powerful digit sum
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$<
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 |