fsharp

Project Euler 35

Michael Jacobsen
To create the rotations I make a “detour” by converting the number into a string and then performing the rotations on the string. #light let primes_below v = Euler_utils.primes | Seq.takeWhile (fun p - p Set.of_seq let rotate number = let number_str = number.ToString() let len = number_str.Length - 1 seq { for i in [ 1..len ] do yield int64 (number_str.Substring(i) + number_str.Substring(0,i)) } let has_rotated set number = let numbers = rotate number Seq.

Tail Recursion with F#

Michael Jacobsen
The familiar for loop featured in most if not all impertive langagues is not part of most functional languages if any because it has the mutable loop index. The standard way of looping in F# is to use recursion. In the solution to Project Euler problem 7 I have the following function let rec findprime primes test = if isprime primes test then test else findprime primes (test+2) Notice that the recursive call is placed as the very last operation in the function and it is therefore a tail call.

Project Euler 48

Michael Jacobsen
In order to keep the numbers in check we use the rule that $$a \equiv v (\bmod m) \Rightarrow a b \equiv v b (\bmod m)$$ This rule is implemented in the powermod function. Note, that the powermod function is not yet “tail recursive” and is therefore vulnerable to stack overflow for (very) large b. #light let rec powermod a b m = if b = 0I then 1I else (a*(powermod a (b-1I) m)) % m let sum = let numbers = [1I .

Euler problems 18 and 67

Michael Jacobsen
Problems 18 and 67 differs in their size, where problem 67 is so large that a (naive) brute force algorithm would not end within reasonable time. A simple algorithm shows it self if we goes from the bottom up. The problem formulation displays the numbers such that one looks at the numbers from the top going down. Look at one “sub-triangle” at the bottom such as (the very left one)

Project Euler

Michael Jacobsen
F# has a lot of functionality for manipulation of lists. Here is my first attempt at the solution in F#. let numbers35 = List.filter (fun i - i % 3 = 0 or i % 5 = 0) [1 .. 999];; printfn "Euler project problem 1 : %d" (List.fold_left (+) 0 numbers35);; I could have merged the two lines into one. However, I find this a bit more clear. The filter function filters (!