Project Euler with Befunge


Fork me on GitHub
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