# Problem Definition

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

# Solution

```object Euler03 {

type Factor = Long
type Number = Long
type Factors = List[Factor]

/* Returns the largest prime factor of the given
* number.It first computes all the prime factors of the given
* number and then returns the largest among them.
*/
def largestPrimeFactor (x: Number): Factor =
primeFactors(x).max

/* Returns the prime factors of the given number x. For instance
* if the number x equals to 5, it returns List(2,3).
*/
def primeFactors(x: Number): Factors = {
val numUpToSqrt = (2L to math.sqrt(x).toLong)
val divisibleBy = numUpToSqrt.find(x % _ == 0)

divisibleBy match {
case None =>  List(x)
// x is a prime number and not divisible by any
case Some(d) => d :: primeFactors(x/d)
}
}
}

```

## Collatz Problem a.k.a. 3n+1 Problem

This post focuses on Collatz problem, which is also known as, among others, the 3n+1 problem, and  the Syracuse problem.

Outline. We begin by introducing Collatz conjecture; afterwards, we presents an algorithm to solve the problem (UVa 100 or SPOJ 4073) published in both UVa and SPOJ. The primary advantage of having it in SPOJ is that we can use F# to derive a simple and elegant solution; at the same time, we can verify it via SPOJ’s online judge.

# Background: Collatz Conjecture

Collatz problem, also known as problem, concerns the iterates generated by the repeated applications of following the function: Given a positive integer,  which implies that if is even, it returns , otherwise . This function is called Collatz function. Consider, for instance, , the generated iterates are following: . This sequence is referred to as Collatz sequence, or hailstone numbers. Collatz conjecture, which is credited to Luther Collatz at the University of Hamburg, asserts that for any positive integer , the repeated applications of the Collatz function, i.e., eventually produces value ; that is, , where denotes application of . Considering , it follows: .

The generated sequence of iterates: is called the Collatz-trajectory of . For instance, beginning from , the resulted sequence converged to as follows: . Therefore, Collatz-trajectory of 26 is . Note that, although Collatz problem is based on this simple concept, it is intractably hard. So far, it has been verified for by Leaven and Vermeluen.

# Algorithm Design: 3n+1 problem

In the rest of this post, we intend to solve the problem, which is essentially a restricted or bounded version of the Collatz problem.

Interpretation. It restricts the iteration by exiting as soon as the Collatz sequence reaches to value 1 at . For = 26, the resulting Collatz sequence is therefore: , and length of the sequence is i.e., 11. This problem asks to compute the largest Collatz sequence that results from any integer between and , which are provided as inputs. Note that, the value of and are both positive integers: .

Implementation. We first apply a naïve brute-force algorithm to solve this problem, which computes the length of the sequence for each integer from to , and returns the maximum length found.  It is worth noting that- A naïve brute-force algorithm redundantly computes sequences again and again. Consider =13 and =26. For = 26, we also compute the sequence for 13 that has already  been computed during = 13. We must apply a tail-recursive implementation to compute the sequence, as naïve implementation might results in stack overflow.

As we shall see next, we have optimized the naïve implementation considering the above observations. First, we define function, `nextCollatz`, that returns next integer of the Collatz sequence, given an integer . In effect, it computes from as follows.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 let nextCollatz (n:int64) = if n%2L = 0L then n/2L else 3L*n+1L
view raw gistfile1.fs hosted with ❤ by GitHub

Using the algorithm outlined in `collatzSeqLength`, the length of the Collatz sequence is computed for any given integer .

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 let max = 1000001L let memo = Array.create (max|>int) 0L // Computes Collatz sequence length, given a // positive integer, x. let rec collatzSeqLength (x:int64):int64 = let rec seqLength' (n:int64) contd = match n with | 1L -> contd 1L // initalizing sequence length with 1 | _ -> if n < max && memo.[n|>int] <> 0L then contd memo.[n|>int] else seqLength' (nextCollatz n) (fun x -> let x' = x+1L //incrementing length and storing it in memo. if nint] <- x' else () contd x' ) x|>(fun i -> seqLength' i id)
view raw gistfile1.fs hosted with ❤ by GitHub

It includes the following optimizations over the naïve implementation we stated earlier: Memorization has been incorporated to effectively optimize the algorithm by avoiding redundant computations of the sequence and its length, which in turn provides a faster algorithm than its naïve counterpart, albeit with the cost of additional space. Tail-recursive algorithm enables computation of Collatz sequence with larger . Continuation-passing-style  has been applied in this algorithm to accommodate, and to combine tail-call optimization with memorization.

The following snippet demonstrates how the maximum sequence length is obtained by invoking collatzSeqLength for each integer between the given and .

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 let maxCollazSeqLength (x:int64,y:int64) = let x',y' = System.Math.Min(x,y), System.Math.Max(x,y) seq[x'..y'] |> Seq.fold (fun max x -> let r = collatzSeqLength x if r > max then r else max) 0L
view raw gistfile1.fs hosted with ❤ by GitHub

Complete source code of this problem can be found in this gist. Following IDEONE page (with sample inputs and outputs) has been provided to further play with the code (in case of the unavailability of F# in local system).  Java source code is also available for this problem.

Try solving Euler Problem 14, which resembles this problem and based on these stated concepts. Please leave a comment if you have any question/suggestion regarding this post. Happy coding!

# Problem Definition

Available at Sum square difference

The sum of the squares of the first ten natural numbers is,

`12 + 22 + ... + 102 = 385`

The square of the sum of the first ten natural numbers is,

`(1 + 2 + ... + 10)2 = 552 = 3025`

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025-385 = 2640.Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

# Implementation

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 open System let squareOfSum n = let i = n*(n+1)/2 i*i let sumOfSquare n = [1..n] |> List.fold (fun acc x -> acc + x*x) 0 let solveEuler6 N = (squareOfSum N)- (sumOfSquare N)
view raw euler06.fs hosted with ❤ by GitHub

# Problem Definition

Available at Largest Palindrome Product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Implementation

We have to find out a palindrome p such that — where both  a and b are  three digit number.  To do so, we first define a function that checks whether a  number (e.g., p) is a palindrome.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 let ispalindrom (x:int):bool = let s = x.ToString() s = (s |> (fun x -> new string(x.ToCharArray() |> Array.rev)))
view raw ispalindrom.fs hosted with ❤ by GitHub

Then, we  iterate over all the tuples (a,b) of three digit numbers  e.g.,  [100..999]  that satisfy the  following equation. Finally, we check if a*b is a palindrome and get the largest palindrome, as outlined below.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 seq{ for x in 100..999 do for y in x..999 do if ispalindrom (x*y) then yield (x*y)} |> Seq.max
view raw euler04.fs hosted with ❤ by GitHub

Would/did you solve it differently? Please let me know your opinion in the comment section below.

Happy problem solving … ## Solution

Given that the length of the sides are `{a,b,c,d}`, the Maximal Quadrilateral Area is given by the following equation: where semiperimeter `s` can be defined as follows. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 let getMaxQuadrilateralArea (a,b,c,d) = let s = 0.50 *(a+b+c+d) System.Math.Sqrt((s-a)*(s-b)*(s-c)*(s-d)) let solveSpoj2716() = let parseLine() = let l = System.Console.ReadLine().Split() (l.|>float,l.|>float,l.|>float,l.|>float) let rec runTests currentTest maxAvailableTests = if currentTest < maxAvailableTests then parseLine() |> getMaxQuadrilateralArea |> printfn "%f" runTests (currentTest+1) maxAvailableTests in match System.Console.ReadLine() |> System.Int32.TryParse with | (true, i) when i > 0 -> runTests 0 i | _ -> () solveSpoj2716()
view raw QUADAREA.fs hosted with ❤ by GitHub