Lua

Lua, introduced in 1993, is renowned for its accessibility and simplicity; it's used primarily as an embedded scripting language. It's supposed to be highly optimized for speed.

My version of Euler1 here is straight out of the imperative school - it looks just like JavaScript, Java, VBScript... It's so familiar that it literally took me only 15 minutes to bang this out with no prior knowledge of this language. It's actually disappointingly verbose for what it is, but I can't complain about the development time:

#!/usr/bin/lua5.4
-- Euler1 in Lua

function euler(n)
    local retval = 0
    for i = 0, n do
        if i % 3 == 0 or i % 5 == 0 then
            retval = retval + i
        end
    end
    return retval
end

print (string.format("Euler1 = %d", euler(999)))

Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

#!/usr/bin/lua5.4
-- Euler1 in Lua

function euler(n, acc)
    if n == 1 then
        return acc
  elseif n%3 == 0 or n%5 == 0 then
        return euler(n-1, acc+n)
  else
      return euler(n-1, acc)
  end
end

function euler1(n)
    return euler(n, 0)
end

print (string.format("Euler1 = %d", euler1(999)))

Here's a version where we generate three ranges - multiples of 3, 5, and 15, and we subtract the multiples of 15 since they're going to be the duplicate values found in the other two sequences:

#!/usr/bin/lua5.4
-- Euler1 in Lua

function euler1(n)
   result = 0

   for i = 0, math.floor(n/3) do
       result = result + (i * 3)
   end
   for i = 0, math.floor(n/5) do
       result = result + (i * 5)
   end
   for i = 0, math.floor(n/15) do
       result = result - (i * 15)
   end

   return result
end

print (string.format("Euler1 = %d", euler1(999)))

Here's a different version - I simply sum up three collections of ints up to 999, one step 3, one step 15 starting at 5, and one step 15 starting at 10. This covers all the ints divisible by 3 or 5 with no overlaps. Cool!

#!/usr/bin/lua5.4
-- Euler1 in Lua

function euler1(n)
    result = 0

    for i = 0, math.floor(n/3) do
        result = result + (i * 3)
    end
    for i = 0, math.floor(n/15) do
        result = result + (i * 15 + 5)
    end
    for i = 0, math.floor(n/15)-1 do
        result = result + (i * 15 + 10)
    end

    return result
end

print (string.format("Euler1 = %d", euler1(999)))

Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together.

#!/usr/bin/lua5.4
-- Euler1 in Lua

-- calculate solution based on Quicksort problem decomposition
function euler(L, acc)
    if #L == 0 then 
        return acc -- sum of multiples of 3 and 5 that are below 'size'
    end

    local pivot = math.max(1, math.floor(#L / 2)) -- get the middle element of the list

    -- recursively solve the problem for the left and right half of the list
    return (euler( {table.unpack(L, 1, pivot-1)}, acc ) -- solve problem for left half of the list
          + euler( {table.unpack(L, pivot+1, #L)}, acc ) -- solve problem for right half of the list
          + ( (L[pivot]%3 == 0 or L[pivot]%5 == 0)  and  L[pivot]  or  0 ) -- add pivot if it is a multiple of 3 or 5
          + acc) -- add the total found so far to the result
    end

-- generate a list of ints using tail recursion
function genInts(i, acc)
    table.insert(acc, i)

    if i == 0 then 
        return acc -- when reaching 0, return the generated list
    end

    -- recursively generate a list of numbers from i to 0
    return genInts(i-1, acc)
end

function Euler1(size)
    -- call euler function with a list of numbers from 0 to 'size', and 0 as initial accumulator
    return euler(genInts(size, {}), 0)
end

-- print the solution of Euler1 problem for numbers below 1000
print ( "Euler1 = " .. Euler1(999) .. "\n" )

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:

#!/usr/bin/lua5.4
-- Euler1 in Lua

function euler(n, size)
    return (math.floor(size/n)^2 + math.floor(size/n)) * n / 2
end

function euler1(n)
    return euler(3, n) + euler(5, n) - euler(15, n)
end

print (string.format("Euler1 = %d", euler1(999)))

I look forward to investigating this language further. To install on Ubuntu, apt install lua5.3. Then to execute:

$ chmod +x euler1.lua
$ ./euler1.lua
233168