## 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.1Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seenthat 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_exponentiationlet 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_orderlet 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_denominatorslet period_of_1divp p = multiplicative_order 10 p// http://en.wikipedia.org/wiki/Prime_number#Verifying_primalitylet 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 2let 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# !