Friday, June 4, 2010

Problem 32: Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

While having lots of pieces, this problem is mostly straightforward.  The only part that required any analysis is determining sufficient lower and upper bounds for the product, since the worst case range (1 to 999999999) is far too large.  Letting p be the product, mn be the multiplican, and mr be the multiplier, we observe that if mn * mr = p, then (len p) = ((len mn) + (len mr)) + (-1 or 0).  Which implies the length of the product is cannot be less than 4 or greater than 5 or we will have either too few or too many digits in our pandigital set. Thus the range  may be restricted to 1234 to 98765.

let problem32c =
    let hasDistinctPositiveDigits (nstr:string) = 
        not (nstr.Contains("0")) && nstr.Length = (nstr |> Seq.distinct |> Seq.length)
    
    let isPositivePanDigitalSet mnstr mrstr pstr =
        let concatedDigitStr:string = mnstr + mrstr + pstr
        concatedDigitStr.Length = 9 && hasDistinctPositiveDigits concatedDigitStr
        
    let findPositivePanDigitalSet p =
        let pstr = p |> string
        if not (hasDistinctPositiveDigits pstr) then None
        else
            let sr = sqrtn p
            let rec loop mn =
                if mn > sr then None
                elif p % mn = 0 then
                    let mr = p/mn
                    if isPositivePanDigitalSet (mn |> string) (mr |> string) pstr then 
                        Some(mn, mr, p) 
                    else loop (mn + 1)
                else loop (mn + 1)
            loop 2
    
    {1234..98765} //product must be between 4 and 5 digits
    |> Seq.map findPositivePanDigitalSet
    |> Seq.filter Option.isSome
    |> Seq.sumBy (fun (Some(_,_,p)) -> p)

No comments:

Post a Comment