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.