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.
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.
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 .
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)
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 (!