5 people like it.
Like the snippet!

Project Euler #1

This snippet is code that solves first Project Euler problem. It finds the sum of all the multiples of 3 or 5 below 1000. Please add other (more efficient, succinct or interesting) solutions to this snippet.

Using declared functions

1: 
2: 
3: 
4: 
5: 
6:

let range = [0..999]
let condition x = x % 3 = 0 || x % 5 = 0

range 
  |> List.filter condition 
  |> List.fold (+) 0

Using lambda functions

1: 
2: 
3:

[0..999] 
  |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) 
  |> Seq.reduce (+)

Using sequence expressions

1: 
2: 
3:

seq { for x in 0 .. 999 do
      if x % 3 = 0 || x % 5 = 0 then yield x }
|> Seq.sum

Using recursive function for ultimate speed

1: 
2: 
3: 
4: 
5: 
6:

let rec multiple x =
  if x = 1000 then 0
  elif x%3 = 0 || x%5 = 0 then x + multiple (x+1)
  else multiple (x+1)
  
multiple 1

Using accumulator for tail-recursive and pattern matching

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9:

let rec mul' acc x =
  match x with
  | 999L -> acc + x 
  | x when (x%3L=0L||x%5L=0L) ->       
      mul' (acc + x) (x + 1L)   
  | _ -> 
      mul' acc (x + 1L)

mul' 0L 1L

Fast calculation (generalized solution)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30:

let mSum (multipliers:int list) limit =
//if 1 + 2 + .. + n = n*(n+1)/2
  let aSum n = n*(n+1I) >>> 1

//then k + 2k + .. + k*n = k*(aSum n), where n = limit/k
  let lSum limit k = limit/k |> aSum |> (*) k

//make all combinations of multipliers
//thanks to Alexander Rautenberg
  let allCombinations lst =
     let rec comb accLst elemLst =
         match elemLst with
         | h::t ->
             let next = [h]::List.map (fun el -> h::el) accLst @ accLst
             comb next t
         | _ -> accLst
     comb [] lst

//and do calculations using inclusion–exclusion principle
  multipliers 
   |> allCombinations 
   |> List.map  (fun l -> let k = List.reduce (*) l |> bigint in
                           if (List.length l) % 2 = 0 then 
                             -(lSum limit k)
                           else 
                              lSum limit k
                )
   |> List.sum

let ans = mSum [3;  5] 999I

val range : int list

Full name: Script.range

val condition : x:int -> bool

Full name: Script.condition

val x : int

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter

val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold

module Seq

from Microsoft.FSharp.Collections

val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.filter

val reduce : reduction:('T -> 'T -> 'T) -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.reduce

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val sum : source:seq<'T> -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum

val multiple : x:int -> int

Full name: Script.multiple

val mul' : acc:int64 -> x:int64 -> int64

Full name: Script.mul'

val acc : int64

val x : int64

val mSum : multipliers:int list -> limit:System.Numerics.BigInteger -> System.Numerics.BigInteger

Full name: Script.mSum

val multipliers : int list

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val limit : System.Numerics.BigInteger

val aSum : (System.Numerics.BigInteger -> System.Numerics.BigInteger)

val n : System.Numerics.BigInteger

val lSum : (System.Numerics.BigInteger -> System.Numerics.BigInteger -> System.Numerics.BigInteger)

val k : System.Numerics.BigInteger

val allCombinations : ('a list -> 'a list list)

val lst : 'a list

val comb : ('b list list -> 'b list -> 'b list list)

val accLst : 'b list list

val elemLst : 'b list

val h : 'b

val t : 'b list

val next : 'b list list

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

val el : 'b list

val l : int list

val reduce : reduction:('T -> 'T -> 'T) -> list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.reduce

type bigint = System.Numerics.BigInteger

Full name: Microsoft.FSharp.Core.bigint

val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length

val sum : list:'T list -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sum

val ans : System.Numerics.BigInteger

Full name: Script.ans

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/1a
Posted:	5 years ago
Author:	Eugene Gavrin
Tags:	list , filter , fold , euler problem , inclusion-exclusion