Learning basic Clojure and Scala by solving some problems from http://www.projecteuler.net

euler.clj

;; import all helper functions
(load-file "helpers.clj")

(ns euler)

;;
;; Problem 1
;; 
(defn prob-1 []
  "Find the sum of all the multiples of 3 or 5 below 1000"
  (let [;; a few anonymous functions to make
        ;; the later deduction look simpler
        mod-3?      #(= 0 (mod % 3))
        mod-5?      #(= 0 (mod % 5))
        mod-either? #(or (mod-3? %) (mod-5? %))]
    ;; pick all the numbers from 0-1000 for whom
    ;; n % 3 == 0 or n % 5 == 0, then sum them
    (reduce + (filter mod-either? (range 1000)))))

;; 
;; Problem 2
;;
(defn prob-2 []
  "By considering the terms in the Fibonacci sequence
   whose values do not exceed four million, find the 
   sum of the even-valued terms."
  (let [ less-than-4M? #(<= % 4e6) 
         valid?        #(and (even? %) (less-than-4M? %))]
    ;; sum all that's made it this far
    (reduce + 
            ;; extract the terms that are < 4e6 
            ;; and are even numbers
            (filter valid? 
                    ;; this is the Fibonacci up to 100
                    ;; as (fib 100) is definitely > 4e6.
                    ;; Yes, this is probably redundant and
                    ;; should be found in runtime. Sue me.
                    (map fib (range 100))))))

;;
;; Problem 3
;;
(defn prob-3 []
  "What is the largest prime factor of the number 600851475143"
  ;; using (prime? ..), (primes ..) and (max-prime ..) 
  ;; from helpers.clj
  (max-prime 600851475143))

;;
;; Problem 5
;;
(defn prob-5 []
  "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"
  (let [div? #(= 0 (mod %1 %2))]
    (loop [current 20]
      (if 
        (zero? 
          (reduce + 
                  (map #(if (div? current %) 0 1) 
                       (range 1 20))))
        current
        (do
          (println (str "\r" current))
          (recur (inc current)))))))

;;
;; Problem 6
;;
(defn prob-6 []
  "Find the difference between the sum of the 
   squares of the first one hundred natural numbers
   and the square of the sum"
  (let [nn 101]
    (- 
      ;; square of the sums
      (expt (reduce + (range 0 nn)) 2) 
      ;; sum of the squares
      (reduce + (map #(expt % 2) (range 0 nn))))))

;;
;; Problem 7
;;
(defn prob-7 []
  "What is the 10001st prime number?"
  (nth (primes 110000) 10000))

euler.scala

// helper - calculate the Fibonacci number given a value

// the Fibonacci number for a given index of the series
def fib(num: BigInt) : BigInt = {

    def helper(num: BigInt, current: BigInt, next: BigInt ) : BigInt = {
      if ( num == 0 ) return current;
      return helper(num - 1, next, current + next);
    }

    return helper(num, 0, 1);
}

// return a list of prime numbers up to specified limit
// Uses the Sieve of Eratosthenes method for primes
def primes(limit: Int) : List[Int] = {

  // initial list of values
  var list  = (2 to limit).toList;

  def helper(idx: Int, lst: List[Int]) : List[Int] = {
    var value = lst(idx);

    if ( value == limit || idx + 1 >= lst.length ) {
      return lst;
    } else {
      return helper( idx + 1, lst.filter( n => { n % value != 0 || n == value } ) );
    }
  }
  return helper(0, list);
}

// factorial
def fact(num: Int) : BigInt = {

  def helper(nn: BigInt, acc: BigInt): BigInt = {
    if ( nn == 0 ) return acc;
    return helper( nn - 1 , nn * acc);
  }
  
  return helper(num, 1);
}

// simple method that uses string comparison to find if a number is a palindrome
def isPalindrome(num: Int) : Boolean = ( num.toString == num.toString.reverse );

// determine if a number is prime using Wilson's theorem
def isPrime(num: Int) : Boolean = {
  if ( num == 0 || num == 1 ) {
    return false;
  } else if (num == 2 || num == 3) {
    return true;
  } else {
    return ( fact(num - 1) % num == ( num - 1 ) );
  }
}

// calculate the sum of all the number below 1000  who are a multiple of either 5 or 3 
def prob_1() : Unit = {
    val ans = (1 until 1000).filter(n => { (n % 3 == 0) || (n % 5 == 0) }).reduceLeft( _ + _ );
    println("The answer is " + ans);
}

// By considering the terms in the Fibonacci sequence whose values 
// do not exceed four million, find the sum of the even-valued terms.
def prob_2() : Unit = {
  // overkill - create the fib series for 1 to 100, find the even terms, then all the terms that are
  // less than 4M, then sum everything up
  var ans = (1 to 100).map( fib(_) ).filter(_ % 2 == 0).takeWhile( _ < 4000000 ).sum
  println("The answer is " +  ans);
}

//What is the largest prime factor of the number 600851475143 ?
def prob_3() : Unit = {
  var num = 600851475143.0;
  //var num = 13195.0;

  // only need to calculate primes up to sqrt(limit)
  val limit = math.sqrt(num).toInt;
  val prms  = primes(limit);

  // traverse the primes list from the end (as its already
  // sorted, and return the first member that evenly divides
  // with the input
  def findMaxPrime(list: List[Int]) : Int = {
    val last = list.last;
    if ( num % last == 0 ) {
      return last;
    } else {
      return findMaxPrime( list.take( list.length - 1) );
    }
  }
  
  println("The answer is " + findMaxPrime(prms) );
}


// Find the largest palindrome made from the product of two 3-digit numbers.
def prob_4() : Unit = {
  
  // create a list of smallest 3-digit product to largest 3-digit product (square of 999), 

  def findMaxPalindrome() : Int = {
    var num = 0;
    var set = Set[Int]();

    for ( i <- (999 to 100 by -1) ) {
      for ( j <- (999 to 100 by -1 )) {
        num = i * j;
        if ( isPalindrome(num) ) {
          set = set + num;
        }
      }
    }
    return set.toList.sort(_ >= _).head;
  }

  println("The answer is " + findMaxPalindrome() );
}

// What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? 
def prob_5() : Unit = {
  
  // see if one number is divisible by another
  def divisible(x : Int, y : Int) : Boolean = (x % y == 0);

  val top = 20;

  def findMinDivisible(current: Int) : Int = {
    val div = (x: Int) => { if ( divisible(current, x) ) { 0 } else { 1 } } ;
    val sum = (1 to top).map( div(_) ).reduceLeft(_ + _);

    if ( sum == 0) {
      return current;
    } else {
      return findMinDivisible(current + 1);
    }
  }

  println("The answer is " + findMinDivisible(100) );
}


// Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
def prob_6() : Unit = {
  val top = 100;

  val sumsquares = (1 to top).map( math.pow(_, 2) ).sum.toInt;
  val squaresums = math.pow( (1 to top).sum, 2).toInt;

  println("The answer is " + ( squaresums - sumsquares ) );

}


// What is the 10001st prime number?
def prob_7() : Unit = {
  val ans = primes(110000)(10000);
  println("The answer is " + ans );
}

helpers.clj

;; 
;; helper methods for euler.clj - trying to learn some clojure
;; by working through some of the problems in http://www.projecteuler.net
;;
(ns euler
  (:use clojure.contrib.math))

;; Fibonacci value calculation - using tail recursion!
;; used in: prob-2. 
;; TODO: simplify using (loop ..)
(defn fib
  "return the fibonacci value for a given number"
  ([nn] (fib nn 0 1))
  ([nn cur nxt]
   (if (= nn 0)
     cur
     (recur (- nn 1) nxt (+ cur nxt)))))


;; calculate the factorial of a positive integer
(defn fact
  "Factorial of a number"
  ([nn] (fact nn 1))
  ([nn acc]
   (if (zero? nn)
     acc
     (recur (- nn 1) (* acc nn)))))

;; Test if a given number is a prime one
(defn prime?
  "Uses Wilson's theorem to determine if a number is prime. Not too efficient."
  [nn]
  (if (or (= 0 nn) (= 1 nn))
    false
    (if (or (= 2 nn) (= 3 nn))
      true
      (= 
        (mod (fact (dec nn)) nn) 
        (dec nn)))))


;; list of primes up to given nn. Uses the Sieve of Eratosthenes 
;; algorithm.
(defn primes
  "return a list of all prime numbers up to given value"
  [nn]
  (loop [i 0 lst (range 2 nn)]
    (let [value (nth lst i)
          multiple? #(and (not= % value) (= 0 (mod % value)))]
      (if (or (>= value nn) (= value (last lst)))
        lst
        (recur (+ i 1) (filter #(not (multiple? %)) lst))))))

;; get the max prime factor for a given number
(defn max-prime
  "Given a number nn, determine the largest prime factor"
  [nn]
  ;; the list of primes is sorted in ascending order -
  ;; start from the end (max value) and check to see
  ;; if it divides by the given number. If not, proceed
  ;; to the next largest.
  (loop [values (primes (ceil (sqrt nn)))]
    (let [tail (last values)]
      (do ;;(println values) (println tail)
        (if (= 0 (mod nn tail))
          tail
          (recur (drop-last values)))))))