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
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

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