Claudio Cherubino's blog Life of a Googler

17Dec/081

Project Euler in F# – Problem 55

As in the last post, in the description of Project Euler problem 55 there is a detailed step-by-step solution of the problem itself and we just have to write the F# code to perform the tasks.

The only thing that I really had to understand is the definition of Lychrel numbers:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

As usual, it is suggested to break down the problem into little pieces that can be easily solved with a few lines of code each.

First, we need a function to reverse an integer and another one to check whether a number is palindromic, i.e. it is equal to its reverse.

Then we define a function that will be used during each iteration to take a number and sum it with its reverse. This new number is the one that will be checked next for being a palindrome inside the isLychrel function.

If we found a palindrome then the number under testing is not a Lychrel, otherwise we can start the next iteration up to a maximum of 50 times. If we hit this limit then we can conclude the number is a Lychrel.

We have now all the pieces required to answer the original question. Just take all numbers smaller then 10000, filter the Lychrel ones and count them:

#light

let reverse n =
  n.ToString().ToCharArray()
  |> Array.rev
  |> Array.map (fun x -> x.ToString())
  |> Array.reduce_left (^)
  |> bigint.Parse

let isPalindromic n =
  n = reverse n

let reverseAndAdd n =
  n + reverse n

let isLychrel n =
  let rec isLychrelIter n i =
    match i with
    | 50 -> true
    | _ ->
      let r = reverseAndAdd n
      if isPalindromic r then
        false
      else
        isLychrelIter r (i+1)
  isLychrelIter n 1

let answer = [1I .. 10000I]
             |> Seq.filter (fun x -> isLychrel x)
             |> Seq.length
8Oct/081

Project Euler in F# – Problem 36

A number (in general a word) is palindromic when it can be read in the same way from left to right and in the opposite direction, i.e. it is "symmetrical".

According to the definition, a number can be palindromic when written in base10 and not palindromic in base2, but there are some numbers that are palindromic in both bases.

In Project Euler Problem 36 we have to find all these numbers between 1 and 1 million:

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.)

To solve this problem we need two helper functions, one to check whether a number is palindromic and another one to convert a number from base10 to base2:

#light
open Microsoft.FSharp.Math

let isPalindromic n =
  let chars = n.ToString().ToCharArray()
  chars = Array.rev chars

let toBinary (n : BigInt) =
  let rec toBinary1 a v =
    match v with
    | 0I -> a
    | _ ->
      let q,r = BigInt.DivMod (v,2I)
      toBinary1 (r.ToString()::a) q
  toBinary1 [] n |> List.reduce_left (^) |> BigInt.Parse

let euler36 = [1I .. 1000000I] |>
              List.filter isPalindromic |>
              List.filter (fun x -> x |> toBinary |> isPalindromic) |>
              List.reduce_left (+)

The first function checks if a number is palindromic by converting it into an array of digits and checking if this array is equal to its reverse one.

Then we have the toBinary function that is based itself on an inner function called (with a lot of originality) toBinary1.

This recursive function uses the list a to store the remainders of the repeated divisions by 2, until the original number is over.

These digits, converted as strings, are joined with ^, the string concatenation operator and eventually the result is converted to a BigInt.

To find the answer to the problem we start with the list of all numbers between 1 and 1 million and take (filter) only the elements which are palindromic in base10.

After this first step, we filter the list again, this time keeping only those numbers that are palindromic when converted to base2.

The last step is the easiest, we only need to sum the numbers left to get the answer to the problem.