Wednesday, December 8, 2010

Project Euler, problem 26

Problem is stated as following:

A unit fraction contains 1 in the numerator. The decimal representation of the unit
fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen
that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in
its decimal fraction part.



Solution is based on idea that longest recurring cycle should have 1/p form, where p - prime number. After quick look at wikipedia about repeating decimals I thought that I should just search biggest prime, but at closer examination of wiki, I understood that not necessary biggest prime would result in biggest recurring cycle of 1/prime. So for the sake of mathematical integrity, I decided to implement 'correct' search of biggest recurring cycle, which is based on calculating multiplicative order of 10 modulo prime. Solution also is pretty fast - executes in about 130 ms. Below is solution code in language F#:



open System.Diagnostics

// http://en.wikipedia.org/wiki/Modular_exponentiation
let modular_exponent b e m =
let rec modular_exponent0 b e e0 m c0 =
match () with
| _ when e0 >= e -> c0
| _ -> let e1 = e0 + 1 in
let c1 = (c0 * b) % m in
modular_exponent0 b e e1 m c1
modular_exponent0 b e 0 m 1

// http://en.wikipedia.org/wiki/Multiplicative_order
let multiplicative_order a n =
let rec multiplicative_order0 a n k0 =
let me = modular_exponent a k0 n in
match me with
| 1 -> k0
| _ -> let k1 = k0 + 1 in
multiplicative_order0 a n k1
multiplicative_order0 a n 1

// http://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators
let period_of_1divp p = multiplicative_order 10 p

// http://en.wikipedia.org/wiki/Prime_number#Verifying_primality
let is_prime x =
let rec is_prime0 x d0 =
match () with
| _ when d0 > int (sqrt (float x)) -> true
| _ when x % d0 = 0 -> false
| _ -> let d1 = d0 + 1 in
is_prime0 x d1
is_prime0 x 2

let main = let stopwatch = new Stopwatch()
stopwatch.Start()
let prime,max_period =
[ for x in 6..999 do if is_prime x then yield x,period_of_1divp x ] |>
Seq.fold (fun (a,b) (x,y) -> if y > b then (x,y) else (a,b)) (0,0)
stopwatch.Stop()
printfn "Fraction with greatest period of %d is 1/%d, calculated in %d ms"
max_period
prime
stopwatch.ElapsedMilliseconds



Have fun with Project Euler and F# !

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.