Project Euler #1 - Lasso

Question

I've been working on Project Euler questions as part of learning how to code in Lasso and am wondering if my solution can be improved upon. Here is what I've got below for question #1 in Lasso 8 code, and it returns the correct answer:

var ('total' = 0);

loop(1000-1);
    loop_count % 3 == 0 || loop_count % 5 == 0 ? $total += loop_count;
/loop;

output($total);

My question: is there a better or faster way to code this? Thanks!

Answer 1

n = input number

x = (n-1)/3 = count of 3 divisible numbers.*
sum3 = (3*x*(x+1)) / 2 = sum of those numbers.**

y = (n-1)/5 = count of 5 divisible numbers.
sum5 = (5*y*(y+1)) / 2 = sum of those numbers.

half_Ans = sum3 + sum5

but 15, 30, 45... count twice (in both sum3 & sum5).
so remove it one time, so only they count once.

z = (n-1)/15 = count of 15 divisible numbers.
sum15 = (15*z*(z+1)) / 2 = sum of those numbers.

Answer = half_Ans - sum15

• * => (n-1)/3 gives count of 3 divisible numbers.

  • if n = 100 we need to count of (3, 6, 9, ..., 99)
  • 3 is 1st, 6 is 2nd, .... so on 99 is 33rd
  • so total count of those number is gain by last number / 3
  • last number is near to our input n (specifically less than input n)
  • if n = 99 we must not count 99, because statement is "find the sum of all the multiples of 3 or 5 below n".
  • so w/o subtract 1 last unwanted number also count, if n is divisible by 3.

• ** => (3*x*(x+1)) / 2 gives sum of those numbers

  • if n = 100 sum id 3 + 6 + 9 + ... + 99
  • all component are multiple of 3.
  • so 3 + 6 + 9 + ... + 99 = 3*(1 + 2 + 3 + ... + 33)
  • sum of 1 to m is (m*(m+1)) / 2
  • so 3 + 6 + 9 + ... + 99 = (3*33*(33+1)) / 2
  • here m for 1 to m is last number or total number of that sequence or length of sequence that's why we find count of divisible numbers.

Answer 2

There is a fun story about how Gauss once summed numbers, which involves a strategy which can help to avoid the loop.

local('p' = 3);
local('q' = 5);
local('n' = 1000);
local('x' = integer);
local('before');
local('after');

#before = micros

loop(1000) => {
    /* In the tradition of Gauss */
    local('n2' = #n - 1)

    local('pq' = #p * #q)

    local('p2' = #n2 / #p)
    local('q2' = #n2 / #q)
    local('pq2' = #n2 / #pq)

    local('p3' = (#p2 + 1) * (#p2 / 2) + (#p2 % 2 ? #p2 / 2 + 1 | 0))
    local('q3' = (#q2 + 1) * (#q2 / 2) + (#q2 % 2 ? #q2 / 2 + 1 | 0))
    local('pq3' = (#pq2 + 1) * (#pq2 / 2) + (#pq2 % 2 ? #pq2 / 2 + 1 | 0))

    #x = #p * #p3 + #q * #q3 - #pq * #pq3
  }

#after = micros

'Answer: ' + #x + '<br/>\n'
'Average time: ' + ((#after - #before) / 1000) + '<br/>\n'

/* Different numbers */
#p = 7
#q = 11

#before = micros

loop(1000) => {
    /* In the tradition of Gauss */
    local('n2' = #n - 1)

    local('pq' = #p * #q)

    local('p2' = #n2 / #p)
    local('q2' = #n2 / #q)
    local('pq2' = #n2 / #pq)

    local('p3' = (#p2 + 1) * (#p2 / 2) + (#p2 % 2 ? #p2 / 2 + 1 | 0))
    local('q3' = (#q2 + 1) * (#q2 / 2) + (#q2 % 2 ? #q2 / 2 + 1 | 0))
    local('pq3' = (#pq2 + 1) * (#pq2 / 2) + (#pq2 % 2 ? #pq2 / 2 + 1 | 0))

    #x = #p * #p3 + #q * #q3 - #pq * #pq3
  }

#after = micros

'Answer: ' + #x + '<br/>\n'
'Average time: ' + ((#after - #before) / 1000) + '<br/>\n'

The output is:

Answer: 233168<br/>
Average time: 3<br/>
Answer: 110110<br/>
Average time: 2<br/>

Although the first time I ran it, that first average time was 18 instead of 3. Maybe Lasso is doing something smart for subsequent runs, or maybe it was just bad luck.

Answer 3

Actually Chris it looks like my L9 code answer was almost exactly the same. However what I had to do to time is was wrap it in a loop to time it 1000 times.

Lasso 9 can do Microseconds, whereas versions prior can only time in milliseconds.

Below are 3 ways - the first is yours, then my two versions.

define br => '<br>'
local(start_time = micros)
loop(1000)=>{
    var ('total' = 0);

    loop(1000-1);
        loop_count % 3 == 0 || loop_count % 5 == 0 ? $total += loop_count;
    /loop;
    $total;

}
'Avg (L8 code in 9): '+(micros - #start_time)/1000+' micros'

br
br

local(start_time = micros)
loop(1000)=>{
    local(sum = 0)
    loop(999)=>{ loop_count % 3 == 0 || loop_count % 5 == 0 ? #sum += loop_count }
    #sum
}
'Avg (incremental improvement): '+(micros - #start_time)/1000+' micros'

br
br

local(start_time = micros)
loop(1000)=>{
    local(sum = 0)
    loop(999)=>{ not (loop_count % 3) || not(loop_count % 5) ? #sum += loop_count }
    #sum
}
'Avg using boolean not: '+(micros - #start_time)/1000+' micros'

The output is:

Avg (L8 code in 9): 637 micros
Avg (incremental improvement): 595 micros
Avg using boolean not: 596 micros

Note that I didn't use "output" as it's redundant in many situations in 8 and completely redundant 9 :)