Project Euler — Problem 38 Solution

Problem

Take the num­ber 192 and mul­ti­ply it by each of 1, 2, and 3:

192 x 1 = 192

192 x 2 = 384

192 x 3 = 576

By con­cate­nat­ing each prod­uct we get the 1 to 9 pandig­i­tal, 192384576. We will call 192384576 the con­cate­nat­ed prod­uct of 192 and (1,2,3)

The same can be achieved by start­ing with 9 and mul­ti­ply­ing by 1, 2, 3, 4, and 5, giv­ing the pandig­i­tal, 918273645, which is the con­cate­nat­ed prod­uct of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandig­i­tal 9-dig­it num­ber that can be formed as the con­cate­nat­ed prod­uct of an inte­ger with (1,2, … , n) where n > 1?

Solution

// define function which checks if a given number is 1-9 pandigital
let isPandigital n =
    let str = n.ToString()
    [1..9]
    |> List.map string
    |> List.forall (fun x -> str.Contains(x) && str.IndexOf(x) = str.LastIndexOf(x))

// define function to generate the (possible) pandigital sequence
let getConcatProduct n =
    // define recursive inner function
    let rec genSeq n' (digits:string) n=
        let digits' = digits + (n' * n).ToString()
        if digits'.Length > 9 then digits else genSeq (n'+1) digits' n
    genSeq 1 "" n

let answer =
    [1..10000]
    |> List.map getConcatProduct
    |> List.filter (fun d -> d.Length = 9 && isPandigital d)
    |> List.maxBy int

See­ing as n must be greater than 1 as spec­i­fied in the prob­lem brief, we only needs to check num­bers up to 10000 as the con­cate­nat­ed form of two 5-dig­it num­bers will be longer than 9 dig­its.

The get­Con­cat­Prod­uct func­tion does most of the inter­est­ing work and is respon­si­ble for tak­ing a num­ber and return­ing the con­cate­nat­ed prod­uct of that num­ber and 1, 2.. up to 9. The last sec­tion of the code checks the out­puts and only look for con­cate­nat­ed prod­ucts that are 9 dig­its long and pandig­i­tal from 1 to 9, find­ing the largest num­ber of this kind.