Project Euler - Problem 26 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

This article is brought to you by

Don’t reinvent the patterns. Catalyst gives you consistent APIs for messaging, data, and workflow with key microservice patterns like circuit-breakers and retries for free.

Try the Catalyst beta

Problem

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

¹/₂= 0.5

¹/₃= 0.(3)

¹/₄= 0.25

¹/₅= 0.2

¹/₆= 0.1(6)

¹/₇= 0.(142857)

¹/₈= 0.125

¹/₉= 0.(1)

¹/₁₀= 0.1

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

Find the value of d < 1000 for which ¹/_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.

1 thought on “Project Euler – Problem 26 Solution”

Omu
June 15, 2012 at 4:00 pm

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

Problem

Solution

1 thought on “Project Euler – Problem 26 Solution”

Leave a Comment