Project Euler – Problem 60 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

Problem

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution

Note: the source code for both solutions are available on github here.

Brute Force

	#load "Common.fs"
	open Common
	// test primes up to a max value
	let max = 10000
	let primes = genPrimes max |> Array.toList
	// the prime numbers we generated is not going to be sufficient to cover the
	// concatenated primes, hence the isPrime' function here and its memoized form
	let isPrime' n =
	if n % 2 = 0 then false
	elif n % 3 = 0 then false
	else let sqrtn = float n |> sqrt |> ceil |> int
	seq { 5..2..sqrtn } |> Seq.exists (fun x -> n % x = 0) |> not
	let isPrime = memoize isPrime'
	// concatenates two numbers together in both ways and check if both concatenated
	// numbers are also primes
	let concatsToPrime' (a, b) =
	let f a b = a * pown 10 (int (log10 (float b) + 1.0)) + b
	isPrime(f a b) && isPrime(f b a)
	let concatsToPrime = memoize concatsToPrime'
	// find all combinations of n elements in the list l where every two element
	// concatenates to a prime
	let rec comb n (l : int list) acc =
	match n, l with
	| 0, _ -> seq { yield [] }
	| _, [] -> Seq.empty<int list>
	| k, (x::xs) ->
	seq {
	if acc |> List.forall (fun y -> concatsToPrime(x, y))
	then yield! Seq.map ((@) [x]) (comb (k-1) xs (x::acc))
	yield! comb k xs acc
	}
	let answer = comb 5 primes [] |> Seq.map List.sum |> Seq.min

view raw gistfile1.fs hosted with by GitHub

This solution runs in just over 29 seconds on my machine, not great, but within the 1 minute rule for Euler solutions.

Using Set intersections

Here’s an alternative solution, using set intersections.

	#load "Common.fs"
	open Common
	// test primes up to a max value
	let max = 10000
	let primes = genPrimes max |> Array.toList
	// the prime numbers we generated is not going to be sufficient to cover the
	// concatenated primes, hence the isPrime' function here and its memoized form
	let isPrime' n =
	if n % 2 = 0 then false
	elif n % 3 = 0 then false
	else let sqrtn = float n |> sqrt |> ceil |> int
	seq { 5..2..sqrtn } |> Seq.exists (fun x -> n % x = 0) |> not
	let isPrime = memoize isPrime'
	// concatenates two numbers together in both ways and check if both concatenated
	// numbers are also primes
	let concatsToPrime' (a, b) =
	let f a b = a * pown 10 (int (log10 (float b) + 1.0)) + b
	isPrime(f a b) && isPrime(f b a)
	let concatsToPrime = memoize concatsToPrime'
	// returns the set of primes that concatenates with n to another prime
	let getConcatableSet' n =
	primes |> List.filter ((fun n' -> n' > n) <&&> (fun n' -> concatsToPrime(n, n'))) |> Set.ofList
	let getConcatableSet = memoize getConcatableSet'
	let rec comb n l (s : Set<int>) =
	match n, l with
	| 0, _ -> seq { yield [] }
	| _, [] -> Seq.empty<int list>
	| 1, [x] -> seq { yield [x] }
	| k, x::xs ->
	seq {
	let s' = getConcatableSet x |> Set.intersect s
	if not s'.IsEmpty then
	yield! Seq.map ((@) [x]) (comb (k-1) (s' |> Set.toList) s')
	yield! comb k xs s
	}
	let answer = comb 5 primes (primes |> Set.ofList) |> Seq.map List.sum |> Seq.min

view raw gistfile1.fs hosted with by GitHub

This solution is slightly more efficient, running in just over 17 seconds on my machine.