Euler Solution 1

From ProgSoc Wiki

(Redirected from Euler-sol-1)
Jump to: navigation, search

Contents

Solutions for Problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Ordinary languages

Java by Arichu

Runtime: 15ms

public class Main
{ 
  public static void main(String[] args)
  {
     int sum = 0;
     for( int i = 3; i < 1000; i ++)
     {
          if( i%3 ==0 || i%5 == 0)
           sum += i;
     }
     System.out.print(sum);
  }
}

Javascript by ctd

Runtime: 111ms (using node.js/V8)

var sum = 0;
for (var i = 3; i < 1000; i++) {
	if (i % 3 == 0 || i % 5 == 0)
		sum += i;
}
console.log(sum);

C by MichaelF

Runtime: 41ms

#include <stdio.h>
int main() {
       int i = 0;
       int sum = 0;

       while (i < 1000) {
               if (i % 3 == 0 || i % 5 == 0) {
                       sum += i;
               }
               i++;
       } 
       printf("%d\n", sum);
}

Caml by SanguineV

Runtime: 10ms

(* Finds the sum of integers starting at "start" and less than "limit"
 * where they are modulo one of the list of numbers "mods". *)
let sumMods start limit mods =
let rec inner n =
  if n < limit
  then (
    if (List.fold_left (fun x y -> x || n mod y == 0) false mods)
    then n + (inner (n + 1))
    else inner (n + 1))
  else 0
in
inner start
;;

Printf.printf "Result is: %u\n" (sumMods 0 1000 [3;5]);;

C++ by SanguineV

Runtime: 6.6ms

#include <iostream>
using namespace std;

int main() {
  int total = 0;
  for (int i = 3;i < 1000;i+=3) {
    total = total + i;
  }
  for(int i = 5; i < 1000;i+=5) {
    if (i%3 != 0) {
      total = total + i;
    }
  }
  cout << total << endl;
}

C# by PeterD

Runtime on WinXP VM: 0-10ms (faster than the resolution of my clock)
Runtime on niflheim: 144ms

using System;
using System.Linq;

class Program {
  static void Main(string[] args) {
    Console.WriteLine(Enumerable.Range(1, 1000).Where<Int32>(num => num % 3 == 0 || num % 5 == 0).Sum());
  }
}

Haskell by SanguineV

Runtime: 11.229 ms

main = print (sum (filter (\x -> gcd x 3 == 1) [5,10..995] ++ [3,6..999]))

MySQL by SanguineV

Runtime: < 0.01 seconds

select sum(ints) from euler where ints < 1000 and (ints % 3 = 0 or ints % 5 = 0);

perl by mmaster

I found this, half finished, on my hard drive. (Yes, I know that "half finished" with something this short is pretty dodgy.) Gods only know how long it'd been sitting there, I'm guessing since late '07. I fixed the errors it was throwing before adding it. Runtime: Less than a second.

#!/usr/local/bin/perl
#
for ($i=1; $i<1000;$i++){
   if (($i % 3 == 0) || ($i % 5 == 0)){
       $sum += $i;
}}
print "$sum\n";

PL/SQL by mmaster

Runtime: 0.08 seconds

 DECLARE
   i INTEGER;
   j INTEGER;
 BEGIN
   i := 0;
   j := 0;
   FOR i IN 1..999
   LOOP
     IF(i mod 3 = 0) OR (i mod 5 = 0) THEN
       j       := j +i;
     END IF;
   END LOOP;
   DBMS_OUTPUT.PUT_LINE(j);
 END;

Prolog by SanguineV

Runtime: 10ms (interactive mode)

% Return true if a number is divisible by 3 or 5.
mod35(N) :- N mod 3 =:= 0.
mod35(N) :- N mod 5 =:= 0.

% Sum to 0 is 0.
sumTo(0,R) :-
  R is 0.
% Sum to some limit "L", check and do recursively
sumTo(L,R) :-
  mod35(L),
  L1 is L - 1,
  sumTo(L1,R1),
  R is L + R1.
sumTo(L,R) :-
  L1 is L - 1,
  sumTo(L1,R).

% Find the sum to 999 (or 1000 - 1)
sumTo(999,R).


python by elden

Runtime: 7-8ms

# sum can be expressed as
#  sum of sequence of multiples of 3 plus sum of sequence of multiples of 5
#  less sequence of multiples of 15
# because each number divisible by 5 and 3 gets included twice

#code solution:
sum_threes = sum(range(0,1000,3))
sum_fives = sum(range(0,1000,5))
sum_fifteens = sum(range(0,1000,15))

print(sum_threes+sum_fives-sum_fifteens)

Ruby by tomchristmas

Runtime (on niflheim): 11ms

sum = 0

(1000/3).times{|x| sum += (3 * (x+1))}
(995/5).times{|x| sum += (5 * (x+1))}
(1000/15).times{|x| sum -= (15 * (x+1))}

puts sum

Such is the expressive power of Ruby that one can reduce the above code fragment to a single statement, as I have done here:

puts (1..999).inject(0) {|x,y| (y.modulo(3) == 0) || (y.modulo(5) == 0) ? x + y : x}


XSLT by MichaelF

Admittedly a little verbose...

Runtime: 81ms

<?xml version="1.0" encoding="UTF-8"?>
<xs:stylesheet version="1.0" xmlns:xs="http://www.w3.org/1999/XSL/Transform">
	<xs:template match = "/">
		<!-- Find the sum of all factors of 3 -->
		<xs:variable name="sum3s">
			<xs:call-template name="sumFactors">
				<xs:with-param name="max">
					<xs:text>1000</xs:text>
				</xs:with-param>
				<xs:with-param name="num">
					<xs:text>3</xs:text>
				</xs:with-param>
				<xs:with-param name="sum">
					<xs:text>0</xs:text>
				</xs:with-param>
				<xs:with-param name="i">
					<xs:text>0</xs:text>
				</xs:with-param>
			</xs:call-template>
			<xs:text> </xs:text>
		</xs:variable>
		<!-- Find the sum of all factors of 5 -->
		<xs:variable name="sum5s">
			<xs:call-template name="sumFactors">
				<xs:with-param name="max">
					<xs:text>1000</xs:text>
				</xs:with-param>
				<xs:with-param name="num">
					<xs:text>5</xs:text>
				</xs:with-param>
				<xs:with-param name="sum">
					<xs:text>0</xs:text>
				</xs:with-param>
				<xs:with-param name="i">
					<xs:text>0</xs:text>
				</xs:with-param>
			</xs:call-template>
			<xs:text> </xs:text>
		</xs:variable>
		<!-- Find the factors of 15 (to subtract them) -->
		<xs:variable name="sum15s">
			<xs:call-template name="sumFactors">
				<xs:with-param name="max">
					<xs:text>1000</xs:text>
				</xs:with-param>
				<xs:with-param name="num">
					<xs:text>15</xs:text>
				</xs:with-param>
				<xs:with-param name="sum">
					<xs:text>0</xs:text>
				</xs:with-param>
				<xs:with-param name="i">
					<xs:text>0</xs:text>
				</xs:with-param>
			</xs:call-template>
			<xs:text> </xs:text>
		</xs:variable>
		<!-- Output the sum -->
		<output>
			<xs:value-of select="$sum3s + $sum5s - $sum15s" />
		</output>
	</xs:template>
	<xs:template name="sumFactors">
		<xs:param name="max" />
		<xs:param name="num" />
		<xs:param name="sum" />
		<xs:param name="i" />
		<xs:choose>
			<xs:when test="$i &gt;= $max">
				<xs:value-of select="$sum" />
			</xs:when>
			<xs:otherwise>
				<xs:call-template name="sumFactors">
					<xs:with-param name="max">
						<xs:value-of select="$max" />
					</xs:with-param>
					<xs:with-param name="num">
						<xs:value-of select="$num" />
					</xs:with-param>
					<xs:with-param name="sum">
						<xs:value-of select="$sum + $i" />
					</xs:with-param>
					<xs:with-param name="i">
						<xs:value-of select="$i + $num" />
					</xs:with-param>
				</xs:call-template>
			</xs:otherwise>
		</xs:choose>
	</xs:template>
</xs:stylesheet>

Esoteric languages

BF by tomchristmas

A couple nota benes:

- The implementation of BF I used supports cells of type int (32-bit), not the traditional 8-bit unsigned char, which made calculating a *lot* easier! Perhaps if I'm utterly insane, I'll have a go at using four char cells to store the solution.

- This solution only calculates the answer; it doesn't print it. I've yet to figure out how to print! I verified the code's correctness by inserting a printf in the generated C code to print the contents of the result cell before compiling.

> move to cell 1; cell 0 will be used to store the result

add all factors of 3 less than 1000; ie 999 down to 3

cell 1 = 333
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++

[
  copy contents of cell 1 to 2; this is achieved by moving the contents
  of cell 1 to 2 and 3 simultaneously then moving 3 to 1

  [
    ->+>+<<    
  ] 
  >>
  [
    -<<+>>
  ]

  move to cell 2; multiply contents by 3 and add to cell 0

  <
  [
    <<+++>>-
  ]

  <- decrement cell 1 (the factor counter)
]

add all factors of 5 less than 1000; ie 995 down to 5

cell 1 = 190

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++++++

[
  copy contents of cell 1 to 2 as before

  [
    ->+>+<<    
  ]
  >>
  [
    -<<+>>
  ]

  move to cell 2; multiply contents by 5 and add to cell 0

  <
  [
    <<+++++>>-
  ]

  <- decrement cell 1 (the factor counter)
]

subtract all factors of 15 = 3 x 5 less than 1000; ie 990 down to 15

cell 1 = 66

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++

[
  copy contents of cell 1 to 2 as before

  [
    ->+>+<<    
  ]
  >>
  [
    -<<+>>
  ]

  move to cell 2; multiply contents by 15 and subtract from cell 0

  <
  [
    <<--------------->>-
  ]

  <- decrement cell 1 (the factor counter)
]

...so all I have to do now is print it. This is basically what I have to do:

- Separate each digit by repeatedly dividing the result by 10 and putting the remainder in a new cell until the result is 0.

- Add 48 to each digit in each remainder cell to convert the numerical value to its ASCII equivalent.

- Print each cell using '.' in the correct order.

It's harder than it looks!

LOLCODE by tomchristmas

Runtime: when I find a suitable compiler/interpreter, I'll tell you...

HAI

CAN HAS STDIO?
I HAS A SUMM
I HAS A COUNTAH

IM IN YR LOOP
   IZ COUNTAH BIGGER THAN 1000? KTHX
   UP COUNTAH!!3
   UP SUMM!!COUNTAH
IM OUTTA YR LOOP

LOL COUNTAH R 0

IM IN YR LOOP
   IZ COUNTAH BIGGER THAN 995? KTHX
   UP COUNTAH!!5
   UP SUMM!!COUNTAH
IM OUTTA YR LOOP

LOL COUNTAH R 0

IM IN YR LOOP
   IZ COUNTAH BIGGER THAN 1000? KTHX
   UP COUNTAH!!15
   NERF SUMM!!COUNTAH
IM OUTTA YR LOOP

VISIBLE SUMM

KTHXBYE
Personal tools