Project Euler 03. Largest prime factor with Scala

Problem Definition

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

What is the largest prime factor of the number 600851475143?

Source: https://projecteuler.net/problem=3

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

Conrad Wolfram on Making Maths Beautiful

UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500^th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Using F#, we can derive 1500^th Ugly Number in F#’s REPL as follows.

	seq{1L..System.Int64.MaxValue}
	\|> Seq.filter (isUglyNumber)
	\|> Seq.take 1500
	\|> Seq.last

view raw gistfile1.fs hosted with ❤ by GitHub

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

	(*
	* :a:int64 -> b:bool
	*)
	let isUglyNumber (x:int64) :bool =
	let rec checkFactors (n_org:int64) (n:int64) lfactors =
	match n with
	\| 1L -> true
	\| _ ->
	match lfactors with
	\| [] -> false
	\| d::xs ->
	if isFactor n d then
	checkFactors n_org (n/d) lfactors
	elif n > d then
	checkFactors n_org n xs
	else
	false

	checkFactors x x [2L;3L;5L]

view raw gistfile1.fs hosted with ❤ by GitHub

After computing the 1500^th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

	class Main {
	public static void main(String[] args) {
	System.out.println("The 1500'th ugly number is 859963392.");
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Please leave a comment in case of any question or improvement of this implementation. Thanks.

Functional Thinking with Neal Ford

UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

	import java.io.PrintWriter;
	import java.util.Scanner;

	public class Main {
	private final Scanner in;
	private final PrintWriter out;

	private final static int _MaxValue = 1000000;
	private final static long[] memo = new long[_MaxValue];

	public Main() {
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out) {
	this.in = in;
	this.out = out;
	}

	private static long[] getInts(String input) {
	String[] ints = input.trim().split(" ");
	long[] rets = new long[2];

	rets[0] = Long.parseLong(ints[0]);
	rets[1] = Long.parseLong(ints[1]);

	return rets;
	}

	private void solveAckermannProblem(long from, long to) {
	long maxValue = from;
	long maxLength = 0;

	for (long i = from; i <= to; i++) {
	long length = computeCycleLength(nextAckermannNumber(i));
	if (maxLength < length) {
	maxValue = i;
	maxLength = length;
	}
	}

	out.println(String
	.format("Between %d and %d, %d generates the longest sequence of %d values.",
	from, to, maxValue, maxLength));
	}

	private static long computeCycleLength(long n) {
	if (n == 0)
	return 0;

	if (n == 1)
	return 1;

	if (n < _MaxValue && memo[(int) n] != 0)
	return memo[(int) n];

	long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing
	// length of
	// Ackermann
	// sequence

	if (n < _MaxValue) // storing it in cache
	memo[(int) n] = len;

	return len;
	}

	public static long nextAckermannNumber(long n) {
	if (n % 2 == 0)
	return n / 2;
	else
	return n * 3 + 1;
	}

	public void run() {
	while (in.hasNextLine()) {
	long[] range = getInts(in.nextLine());

	if ((range[0] == 0) && (range[1] == 0))
	break;

	long from = Math.min(range[0], range[1]);
	long to = Math.max(range[0], range[1]);

	solveAckermannProblem(from, to);
	}
	}

	public static void main(String[] args) {

	Main solver = new Main();
	solver.run();
	}

	}

view raw UVa371.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

Author: adilakhter