# Project Euler Problem 72

Project Euler Problem 72 yields an elegant imperative solution that I do not see yet how to match by comparable functional one.

Let’s regroup fractions given for **d <= 8** by denominator, then numerator:

**1/2 (ɸ(2)=1)**

**1/3 2/3 (ɸ(3)=2)**

**1/4 3/4 (ɸ(4)=2)**

**1/5 2/5 3/5 4/5 (ɸ(5)=4)**

**1/6 5/6 (ɸ(6)=2)**

**1/7 2/7 3/7 4/7 5/7 6/7 (ɸ(7)=6)**

**1/8 3/8 5/8 7/8 (ɸ(8)=4)**

Apparently, the sought power of set of reduced proper fractions is equal to sum of totients from 2 to 1000000.

Now, given that totient of **n** is product of **n** and all **(1-1/p)**, where **p** is a prime factor of **n**, we can quite efficiently calculate our million of totients based on observation that if **p** is prime factor of **n**, it is also prime factor of **2n**, **3n**, …

let problem072() = let d = 1000000 let ɸ = Array.init (d + 1) id for i in 2..d do if ɸ.[i] = i then for j in i..i..d do ɸ.[j] <- ɸ.[j] / i * (i - 1) Array.map int64 ɸ |> Array.sum |> (+) -1L

Performance is decent ~400ms. Interestingly, F# allows **ɸ** as identificator.