Smallest multiple

2014-09-11

Problem 005: Smallest multiple

Description:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

45*00p110p120p >10g20g*10p00g20g1+:20p`#v_10g.@
               ^_v#`g00p03+1:g03   <p031<         v <
                 >10g30g%          |1              <^        p01/g03g01<
                                   >10g30g/40p150p  > 20g50g1+:50p` #v_^
                 ^                                < |!%g05g04        <
                                                   ^<

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

We start with a value of 1. Then we multiply one after another the numbers from 1 to 20 to our value (We call these multiplicand in the loop).

After each multiplications we search go through the numbers from 2 to value and search for a number divisor where

value % divisor == 0
(value / divisor) % {0, multiplicand} == 0

Then (after we found such a number) we can reduce the value with it (value /= divisor).

The reduction steps guarantees us that we find the smallest number and it prevents our Int64 numbers from overflowing

Interpreter steps:	50 166
Execution time (BefunExec):	47ms (1.07 MHz)
Program size:	73 x 6 (fully conform befunge-93)
Solution:	232792560
Solved at:	2014-09-11