Project Euler – Problem 145 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

Problem

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbersreversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10⁹)?

Solution

	let digitBases = [9..-1..0] |> List.map (fun n -> pown 10 n)
	/// turns the specified number into a list of its digits
	let toDigits (n : int) =
	digitBases |> List.filter (fun n' -> n > n') |> List.map (fun n' -> (n / n') % 10)
	/// turns the specified list of digits into the number they represent
	let toNumber (digits : int list) =
	digits |> List.mapi (fun i n -> n * pown 10 (digits.Length - i - 1)) |> List.sum
	/// returns true if the specified number is reversible, otherwise returns false
	let isReversible (n :int) =
	let digits = toDigits n
	let revDigits = digits |> List.rev
	if (revDigits.Head = 0) then false
	else
	let nRev = toNumber revDigits
	let sum = n + nRev
	let sumDigits = toDigits sum
	sumDigits |> List.forall (fun n' -> n' % 2 <> 0)
	// only check odd numbers, as a pair of reversible numbers will consist off one odd
	// and one even number otherwise their sum will always be even
	let answer = (seq { 3..2..1000000000 } |> Seq.filter isReversible |> Seq.length) * 2

view raw gistfile1.fs hosted with by GitHub

The solution I have posted here solves the problem but it takes a good 15 mins or so to run so doesn’t meet the 1 minute rule.. unfortunately brute force is the only way I know how to solve this problem :-(