The Problem
The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
The Solution
The one is pretty easy. The hardest part, if you can call it that, is turning a number into a string of binary digits.
let rec intToBinary i =
match i with
| 0 | 1 -> string i
| _ ->
let bit = string (i % 2)
(intToBinary (i / 2)) + bit
The intToBinary
function simply divides the input by 2 over and over again until
the value reaches 0 or 1. This final value is the value of the last binary digit.
Before each division, we find i % 2
which equals the next digit in the series.
Concatenate them all together and you have a string of binary digits.
Now, we can find out if a string is a palindrome.
let isPalindrome n =
let s = n.ToString()
let r = System.String.Join("", s |> Seq.rev)
s = r
The isPalindrome
function simply reverses the string and compares it against
the input. If they are equal, it's a palindrome.
Now we can solve the problem:
#time
seq { 1..999999 }
|> Seq.filter isPalindrome
|> Seq.filter (fun x -> isPalindrome (intToBinary x))
|> Seq.sum
#time
We generate the sequence 1..999999 and filter out any number that is not a palindrome. Then we convert the resulting numbers to binary strings and filter out any of those that aren't palindromes. The answer is the sum of the resulting sequence.
Other Posts in This Series