Yan Cui
I help clients go faster for less using serverless technologies.
Problem
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
let naturalNumbers = Seq.unfold (fun state -> Some(state, state+1)) 1
let rec cycleLength n =
if n % 2I = 0I then cycleLength (n/2I)
else
if n % 5I = 0I then cycleLength (n/5I)
else
naturalNumbers
|> Seq.filter (fun x -> ((pown 10I x) - 1I) % n = 0I)
|> Seq.head
let answer = [1I..999I] |> Seq.maxBy cycleLength
Whenever you’re ready, here are 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.
let p26 =
let getSeqLen i =
let rec loop rem remainders rlen =
match rem with
|x when List.exists (fun y -> y = x) remainders -> rlen
|x -> let r = ((rem*10)%i)
match r with
|0 -> rlen
|r -> loop r (x::remainders) (rlen+1)
loop 1 [] 0
let findMax =
let rec loop maxLen maxI i =
match i with
|i when i (maxLen, maxI)
|0 -> (maxLen, maxI)
|i -> let iLen = getSeqLen i
match iLen > maxLen with
|true -> loop iLen i (i-1)
|false -> loop maxLen maxI (i-1)
loop 0 0 1000
findMax