A List processing problem in F#

Question

I am trying to do problem 12 in Project Euler.

numDivisor64 is to calculate number of divisors.

I wrote this F# code:

let problem12 =
    {1L..300000L} |> Seq.map (fun x->x*(x+1L)/2L) |> Seq.map numDivisor64 |> Seq.filter (fun x->x>500L)

The problem asks to find the number rather than its # of divisors. Besides writing this in a less compact way using loops or recursion, any beautiful method?

Another problem, I occasionally find that I need to convert a 32-bit int version of code to a 64-bit one by adding 'L' to all the numbers. Is there a way to avoid this? Anything like c++ template?

I first wrote

let numDivisor n =
    let rec countd n d =
        if n%d=0 then
            let n2, cnt = countd (n/d) d 
            n2, cnt+1
        else
            n, 0

    let rec collect n d = 
        if n < d then 1
        elif n%d=0 then
            let n2, cnt = countd n d
            (cnt+1) * (collect n2 d)
        else
            collect n (d+1)
    collect n 2

Later I found I need bigger integers:

let numDivisor64 n =
    let rec countd n d =
        if n%d=0L then
            let n2, cnt = countd (n/d) d 
            n2, cnt+1L
        else
            n, 0L

    let rec collect n d = 
        if n < d then 1L
        elif n%d=0L then
            let n2, cnt = countd n d
            (cnt+1L) * (collect n2 d)
        else
            collect n (d+1L)
    collect n 2L

Answer 1

if you have the list of divisors you could write a function to calculate the lowest common multiple of them all (which should be the number in question).

in haskell this looks like

lcmAll = foldl1 lcm

in F# i think it would look like this

let rec lcmAll ( head :: tail ) = 
    Seq.fold lcm head tail

I'm not sure if F# has a builtin lcm.

The alternative to this is to carry the original number around through all the transformations by using a product type, or tuple.

let problem12 =
    {1L..300000L} |> Seq.map (fun x->x*(x+1L)/2L) |> Seq.map (fun x->(x,numDivisor64 x)) |> Seq.filter (fun (x,y)->y>500L)

---

In regards to the 64 bit number issue, if you give your function an explicit type signature it could force F# to use 64-bit ints (provided the type signature is valid for the function definition). Again this sort of thing works in Haskell, I cannot confirm it does with F#. If you could double check that would be awesome.

Answer 2

I would rephrase the search for the first wanted number as follows:

• start with an infinite stream of int64's

• turn them into triangle numbers

• find the first number that satisfies the condition (instead of mapping to the number of divisors, which is not what you want, you want the number itself).

code:

let problem12 =
    Seq.initInfinite int64 //the same as Seq.initInfinite (fun n -> int64 n)
    |> Seq.map (fun x -> x*(x+1L)/2L)
    |> Seq.find (fun x -> numDivisor64 x > 500L)

Regarding the second problem: when I solve project Euler problems I usually use int64's by default, because of type inference restrictions.

It's possible to write a more generic version using the inline keyword. See for instance this thread over at hubFS.

EDIT: here's a more generic version, using the technique described in the above link: The type signature of NumDivisorG becomes horrible, but should work for any data type that 'knows' *,+,1 and 0.

module NumericLiteralG =
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne

let inline numDivisorG n =
    let rec countd n d =
        if n%d=0G then
            let n2, cnt = countd (n/d) d 
            n2, cnt+1G
        else
            n, 0G

    let rec collect n d = 
        if n < d then 1G
        elif n%d=0G then
            let n2, cnt = countd n d
            (cnt+1G) * (collect n2 d)
        else
            collect n (d+1G)
    collect n (1G+1G)

let problem12L =
    Seq.initInfinite int64 //the same as Seq.initInfinite (fun n -> int64 n)
    |> Seq.map (fun x -> x*(x+1L)/2L)
    |> Seq.find (fun x -> numDivisorG x > 500L)

let problem12I =
    Seq.initInfinite id //the same as Seq.initInfinite (fun n -> n)
    |> Seq.map (fun x -> x*(x+1)/2)
    |> Seq.find (fun x -> numDivisorG x > 500)