Skip to content

Project Euler Problem 72

January 18, 2012

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.

Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: