re: Write a program or script to find Lucky Numbers VIEW POST


F# solution, ~460 milliseconds runtime. Edit: Previously 620ms when I had the procedures nicely separated. The current results are from going completely imperative. And generating new filters as needed.

foo> dotnet build -c Release

foo> dotnet bin\Release\netcoreapp2.0\MyConsoleApp.dll
Count: 71918
Elapsed Milliseconds: 456
Memory Usage: 916208 bytes
Garbage Collections: 0 gen0, 0 gen1, 0 gen2

About as imperative as possible. But if performance and a sieve is your problem, then imperative mutations are the answer. I actually made an Elm solution first for understand-ability and then translated it into imperative F#. The Elm solution took like 40 seconds to run in the browser. Sooooo much data copying.

open System

// Max is the number of items to wait before removal
// Count is items seen since last removal
type Filter() =
    [<DefaultValue>] val mutable public Max : int
    [<DefaultValue>] val mutable public Count : int

let main args =

    // pre-allocating capacity
    let results =
        Array.zeroCreate<int> 71918
    // 1 is a given
    results.[0] <- 1
    // index to place the next result
    let mutable nextResult = 1

    let iterationCount = 1_000_000
    // experimentally determined 6507 filters for 1,000,000
    // first filter (odd numbers) built into looping logic
    let filterCount = 6506 

    let filters =
        Array.zeroCreate<Filter> filterCount
    // index to place the next filter
    let mutable nextFilter = 0

    let timer =


    let mutable n = 3
    while n < iterationCount do
        let mutable i = 0
        let mutable survived = true
        // check each filter to see if it will discard the number
        // stop as soon as it is discarded
        while i < nextFilter && survived do
            let filter = filters.[i]
            let newCount = filter.Count + 1
            // update filter state... this is much faster than modulo
            if filter.Max = newCount then
                filter.Count <- 0
                survived <- false
                filter.Count <- newCount
                survived <- true
            i <- i + 1

        // survived the guantlet
        if survived then
            results.[nextResult] <- n
            nextResult <- nextResult + 1
            //printfn " %i" i

            // create a new filter, if there is room
            if nextFilter < filterCount then
                filters.[nextFilter] <- Filter(Max=n, Count=nextResult)
                nextFilter <- nextFilter + 1

        n <- n + 2 // odds


    printfn "Count: %i" nextResult
    printfn "Elapsed Milliseconds: %i" timer.ElapsedMilliseconds
    printfn "Memory Usage: %i bytes" <| GC.GetTotalMemory(false)
    printfn "Garbage Collections: %i gen0, %i gen1, %i gen2"
        <| GC.CollectionCount(0)
        <| GC.CollectionCount(1)
        <| GC.CollectionCount(2)

    0 // exit code

Some explanation

The idea is not to copy lists, but to filter out numbers as they come in. Each round of elimination is considered a "filter". The more filters, the lower margin of error in the results. I experimentally determined (by running the code and tweaking the number) the number of filters required for accurate results up to 1 million input numbers is 6507. In other words, 6507 rounds of elimination. You can tell the required margin of error for a given size because once you reach it, increasing the filter count further will not reduce the number of results.

code of conduct - report abuse