Creative Scratchpad

I'm back again with yet another take on a problem from Project Euler series, this time problem No. 5:

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?

This time the problem is quite familiar, we need to get factors of a number or rather set of numbers once again, the only difference is the purpose. For the number to be divisible by another it needs to be divisible by all of its prime factors but that's not all. Let's take for example 16 and 40, while 40 is apparently divisibe by 2, it's not enough, it would actually need to be divisible by the greatest power of two in 16.

Well, looks like we need to collect all the prime factors and count their greatest powers at the same time. There are many ways to do that, let's keep it simple and declare a bitarray and an array, the first one to hold the prime factors already found, the second one to hold the powers (it'd be a small array anyway, in the range 1..20 the last prime is 19). If we would care for bigger numbers, we could just as well use one array of simple two-value structs and bsearch (even though it'd faster to use Point2 values instead of structs for smaller values, Point2 uses float value type and that could be a problem for really big values). It could be just as well done with one array only checking for != undefined but I prefer an additional bitarray for the simplicity of iterating over it.

local factors = #{}
local powers = #()

It makes sense to prepare a little function for setting the values. This one needs to take care of setting new indices and raising powers of existing ones if we suplly it with one. In short, when the index is already defined, we check for its power and if the supplied one is higher we use that one instead. If the index haven't been set yet, we set the index and the supplied power.

fn setPows nr pow =
(
    if factors[nr] then
       if powers[nr] < pow do
            powers[nr] = pow
    else
    (
       factors[nr] = true
       powers[nr] = pow
    )
)

Now, for every number in the range we need to find its prime factors and their powers. This time we need to know how many times we've divided the number so instead of recursion I made use of a while loop, the first one checking for multiples of 2 and counting how many times we can divide the number so that it would still be even, the second one dealing with the rest. At the end of the function if the number couldn't be divided any further and it's still bigger than one, we know it's a prime so we set its first power.

fn primeFactorsPow nr =
(
    if isEven nr do
    (
       local pow = 0L
       do (nr /= 2L; pow += 1) while isEven nr
       setPows 2L pow
    )

    local rootNr = nr^0.5

    for i = 3L to rootNr by 2L
       where mod nr i == 0 do
    (
       local pow = 0L
       do (nr /= i; pow += 1) while mod nr i == 0
       setPows i pow
    )

    if nr > 1 do
       setPows nr 1L
)

The only thing that remains is to set the primes and their powers for all the numbers in range. Let's wrap it up in a function called lowestCommonMultiple where we will iterate over the range calling primeFactorsPow for each number and then for all the collected primes multiply the result by the prime to its highest power recorded. For the sake of completeness I include both the functions explained prior as well as the isEven function we've been using almost from the beginning.

(
    fn isEven nr = bit.and 1L nr == 0

    local factors = #{}
    local powers = #()

    fn setPows nr pow =
    (
        if factors[nr] then
           if powers[nr] < pow do
                powers[nr] = pow
        else
        (
           factors[nr] = true
           powers[nr] = pow
        )
    )

    fn primeFactorsPow nr =
    (
        if isEven nr do
        (
           local pow = 0L
           do (nr /= 2L; pow += 1) while isEven nr
           setPows 2L pow
        )

        local rootNr = nr^0.5

        for i = 3L to rootNr by 2L
           where mod nr i == 0 do
        (
           local pow = 0L
           do (nr /= i; pow += 1) while mod nr i == 0
           setPows i pow
        )

        if nr > 1 do
           setPows nr 1L
    )

    fn lowestCommonMultiple nrs =
    (
        local result = 1L

        for nr in nrs do
           primeFactorsPow nr

        for fact in factors do
           result *= fact^powers[fact]

        result
    )

    lowestCommonMultiple #{2..20}
)

That's it, not much different from our last encounter with prime factors, I agree, but still an interesting task.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.