F# で Project Euler Problem 23

与えられた数を素因数分解して、素因数とその指数とを Map にして返す関数

> let rec get_prime_factor (map:Map<int, int> byref) (n:int) (factor: int) =
-     if n  >= factor then
-         if n % factor <> 0 then
-             get_prime_factor &map n (factor + 1)
-         else
-             if Map.containsKey factor map then
-                 let n = map.[factor] + 1
-                 map <- map.Remove factor
-                 map <- (map |> Map.add factor n)
-             else
-                 map <- (map |> Map.add factor 1)
-
-             get_prime_factor &map (n / factor) factor
- ;;

val get_prime_factor : byref<Map<int,int>> -> int -> int -> unit

真の約数の和を返す関数

> let sum_of_proper_divisors (n:int):int =
-     let mutable map:Map<int, int> = Map.empty
-     get_prime_factor &map n 2
-
-     if map.IsEmpty then 0
-     else
-         int (map
-         |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1))
-         |> Map.toList
-         |> List.map (fun (k, t) -> t)
-         |> List.reduce(*)) - n
- ;;

val sum_of_proper_divisors : int -> int

過剰数の List を 作成

> let abundant_list = (
-     [12..28123]
-     |> List.filter(fun n -> (sum_of_proper_divisors n) > n)
- )
- ;;

val abundant_list : int list =
  [12; 18; 20; 24; 30; 36; 40; 42; 48; 54; 56; 60; 66; 70; 72; 78; 80; 84; 88;
   90; 96; 100; 102; 104; 108; 112; 114; 120; 126; 132; 138; 140; 144; 150;
   156; 160; 162; 168; 174; 176; 180; 186; 192; 196; 198; 200; 204; 208; 210;
   216; 220; 222; 224; 228; 234; 240; 246; 252; 258; 260; 264; 270; 272; 276;
   280; 282; 288; 294; 300; 304; 306; 308; 312; 318; 320; 324; 330; 336; 340;
   342; 348; 350; 352; 354; 360; 364; 366; 368; 372; 378; 380; 384; 390; 392;
   396; 400; 402; 408; 414; 416; ...]

> abundant_list
- |> List.length
- ;;
val it : int = 6965
> abundant_list
- |> List.sum
- ;;
val it : int = 97861532

2つの過剰数の和で書ける数の Set を 作成

>
- let abundant_set =
-     set [
-         for x in abundant_list do
-             for y in (List.filter(fun n -> n >= x) abundant_list) do
-                 let i = x + y
-                 if i <= 28123 then
-                     yield i
-     ]
- ;;

val abundant_set : Set<int> = set [24; 30; 32; 36; 38; 40; 42; 44; 48; ...]

2つの過剰数の和で書けない数の総和

> ([1..28123]
- |> List.sum) -
- (abundant_set
- |> Set.toList
- |> List.sum)
- ;;
val it : int = 4179871