Project Euler problem number #24 deals with permutations in lexicographical order. A non-brute force approach involves a mixed base number system based on factorials.
This problem is one of those that I solved using pen and paper after some research. I used the following Wikipedia pages:
Permutation where I learned that there is a connection between the lexicographical order of a permutation and
the factorial number system representation of that particular number
Finally, you will need to remember that the Wikipedia articles both counts 0,1,2,… while the Euler problem counts 1,2,3,….
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.
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 (!
To solve problem #23 I apply simple brute force and we get to play a little with F# sets. Find all abundant numbers below the given upper limit. Create a set of all sums of these numbers (with a small optimization where avoid computing both a+b and b+a). Then we make a set difference and sums the remaining elements.
#light
let n = seq { 1 .. 28123 }
let abundant number = (List.