// Copyright (C) 2012 Toby Thain, toby@telegraphics.com.au package main.scala.euler object Euler { def sumSeries(n:Int) = n*(n+1)/2 // Find the sum of all the multiples of 3 or 5 below 1000. def problem_1(n:Int) = { val m = n-1 3*sumSeries(m/3) + 5*sumSeries(m/5) - 15*sumSeries(m/15) } // By considering the terms in the Fibonacci sequence whose values do not // exceed four million, find the sum of the even-valued terms. // 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... // O,E,O,O,E,O,O,E,O,O,... // 0,1,2,3,... // 0,1,2,3,... def problem_2(n:Int) = { // compute every third Fibonacci term until n is exceeded. // f0 is always odd, f1 is always even def fibEven(f0:Int, f1:Int, sum:Int):Int = { if(f1 > n) sum else { val f2 = f0+f1 // odd val f3 = f1+f2 // odd fibEven(f3, f2+f3, sum+f1) } } fibEven(1, 2, 0) } def fibStream(a:Int, b:Int):Stream[(Int,Int)] = { Stream.cons((a,b), // current state fibStream(b, a+b)) // lazily evaluated expression produces Stream with updated state } def problem_2b(n:Int) = { // solve using a Stream // process the Stream until values exceed n def sum(acc:Int, s:Stream[(Int,Int)]):Int = { val v = s.head._2 if(v > n) acc else sum(if(v % 2 == 0) acc+v else acc, s.tail) } sum(0, fibStream(0, 1)) } def problem_2c(n:Int) = { fibStream(0, 1) map(_._1) takeWhile(_ <= n) filter(_ % 2 == 0) sum } /* These two methods comprise a remarkably slow way of generating a stream of * prime numbers. */ def isPrime(n:BigInt):Boolean = { primes.takeWhile((k) => k*k <= n).forall(n % _ != 0) } def primes = { def oddPrimesFrom(n:BigInt):Stream[BigInt] = { Stream.cons(n, oddPrimesFrom(n+2) filter isPrime) } BigInt(2) +: oddPrimesFrom(3) } // Alternative strategy... maintain a list of discovered primes // to use for trial divisions. This is still probably quadratic (handwaves). def primesUpTo(n:BigInt):List[BigInt] = { def p(i:BigInt, primes:List[BigInt]):List[BigInt] = { // forall does too many trials. we only need to test up to largest p where p*p <= i if(i > n) primes else p(i+2, if(primes.forall(i % _ != 0)) i :: primes else primes) } 2 :: (p(3, List()).reverse) } def primeSieve(n:Int) = { val primes = collection.mutable.BitSet(n) ++ (2 to n) // set of composites found for(p <- 2 to n/2 if primes.contains(p); q <- p+p to n by p ) primes -= q primes } def primeFactorsSlow(n:BigInt) = { primesUpTo(n) filter { n % _ == 0 } } val B0 = BigInt(0) def primeFactors(n:BigInt) = { def tryDivisor(n:BigInt, d:BigInt, factors:List[BigInt]):List[BigInt] = { if(n == 1) factors else n /% d match { case (q,B0) => tryDivisor(q, d, d :: factors) case _ => tryDivisor(n, d+1, factors) } } tryDivisor(n, 2, List()) } def intSqrt(n:BigInt) = { def trial(m:BigInt):BigInt = { val q = n/m if(q >= m) m else trial((m + q)/2) } trial(n/2) } // based on https://github.com/pufuwozu/roy/blob/master/examples/sqrt.lroy def intSqrtBabylonian(n:BigInt) = { def halfLog2(m:BigInt) = { def logStep(mm:BigInt, p:Int):Int = { if(mm < 4) p else logStep(mm/4, p+2) } logStep(m, 0) } def sqrtStep(r:BigInt):BigInt = { println("root guess: "+r) val q = n/r if(q == r) r else sqrtStep((q+r)/2) } sqrtStep(BigInt(2).pow(halfLog2(n))) } def primeFactorPowers(n:BigInt) = { def tryFactor(n:BigInt, d:BigInt):List[(BigInt,BigInt)] = { def tryDiv(n:BigInt, e:BigInt):(BigInt,BigInt) = { n /% d match { case (q,B0) => tryDiv(q, e+1) // divided without remainder, so count and try again case _ => (n,e) // otherwise, return quotient of successful divisions plus count (exponent) } } if(n == 1) Nil else { val (nn,e) = tryDiv(n, 0) val rest = tryFactor(nn, d+1) if(e > 0) (d,e) :: rest else rest } } tryFactor(n, 2) } def primeFactorPowers2(n:BigInt) = { val sieve = primeSieve(n.toInt).toList def tryFactor(n:BigInt, pr:List[Int]):List[(BigInt,BigInt)] = { val d = BigInt(pr.head) def tryDiv(n:BigInt, e:BigInt):(BigInt,BigInt) = { n /% d match { case (q,B0) => tryDiv(q, e+1) // divided without remainder, so count and try again case _ => (n,e) // otherwise, return quotient so far, and count (exponent) } } if(n == 1) Nil else { val (nn,e) = tryDiv(n, 0) val rest = tryFactor(nn, pr.tail) if(e > 0) (d,e) :: rest else rest // obviously not tail recursive } } tryFactor(n, sieve) } // Find largest prime factor def problem_3(n:BigInt) = { primeFactors(n).last } def problem_4() = { def isPalindrome(k:Int) = { val s = k.toString s == s.reverse } ( for(i <- 100 to 999; j <- 100 to i; if isPalindrome(i*j)) yield i*j ).sorted.last } // Find largest k such that base^k <= i def floorLog(base:BigInt, i:BigInt):Int = { if(i < base) 0 else 1 + floorLog(base, i/base) } def square(x:BigInt) = x*x def square(x:Int) = x*x /* This is BigInt.pow() def expt(base:BigInt, e:BigInt):BigInt = { if(e == 0) 1 else if(e % 2 == 0) { square(expt(base, e/2)) } else { base*expt(base, e-1) } } */ // What is the smallest positive number that is evenly divisible by // all of the numbers from 1 to 20? // (The sequence over n is http://oeis.org/A003418 ) def problem_5(n:Int) = { // let's try it with 1..10 // prime factors: 1 2 3 4 5 6 7 8 9 10 // 10: 1 1 // 9: 2 // 8: 3 // 7: 1 // 6: 1 1 // 5: 1 // 4: 2 // 3: 1 // 2: 1 // For each prime, take the highest power. // 3 2 1 1 i.e. answer is 2^3 * 3^2 * 5 * 7 ( primesUpTo(n) map { pr => pr.pow((BigInt(1) to n map { floorLog(pr, _) }).max) } ).product } def problem_6(n:Int) = square(sumSeries(n)) - (1 to n map(square)).sum def problem_7(n:Int) = primes(n-1) // Too slow! Lulz. // This is still terrible. def nthPrime(n:Int) = { import scala.collection.immutable._ def accPrimes(acc:LinearSeq[Int], n:Int, count:Int):LinearSeq[Int] = { if(acc.length == count) acc else accPrimes(if(acc.forall(n % _ != 0)) acc :+ n else acc, n+2, count) } accPrimes(LinearSeq(2), 3, n).last } def problem_7b(n:Int) = nthPrime(n) // Find the greatest product of five consecutive digits in the 1000-digit // number. def problem_8(n:String) = n.map{_ - '0'}.sliding(5).map{_.product}.max // A Pythagorean triplet is a set of three natural numbers, a < b < c, for // which, // a^2 + b^2 = c^2 // For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. // There exists exactly one Pythagorean triplet for which a + b + c = 1000. // Find the product abc. def problem_9(n:Int) = { for(c <- 1 to n-2; b <- 1 to (1000-c min c-1); a <- Seq(1000-b-c) if a < b; if a*a + b*b == c*c && a+b+c == n ) yield (a,b,c) } // Find the sum of all the primes below two million. // (cannot simply use .sum because returned sieve is a set of Int, // and Int will overflow) def problem_10(n:Int) = primeSieve(n-1).foldLeft(BigInt(0))(_ + _) // What is the greatest product of four adjacent numbers in any direction // (up, down, left, right, or diagonally) in the 20 * 20 grid? def problem_11(a:Array[Array[Int]]) = { (for(j <- 0 to a.length-4; i <- 0 to a(0).length-4; k <- Seq( Seq((0,0),(1,0),(2,0),(3,0)), Seq((0,0),(0,1),(0,2),(0,3)), Seq((0,0),(1,1),(2,2),(3,3)), Seq((3,0),(2,1),(1,2),(0,3)) )) yield (k map { t:(Int,Int) => a(j+t._1)(i+t._2) }).product ).max } // The sequence of triangle numbers is generated by adding the natural // numbers. The first ten terms would be: // 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... // We can see that 28 is the first triangle number to have over five // divisors. What is the value of the first triangle number to have // over five hundred divisors? /* def problem_12(n:Int) = { def step(i:Int):Int = { val tri = sumSeries(i) if(divisors(tri).length > n) tri else step(i+1) } step(1) }*/ def main(args:Array[String]) {/* println(problem_1(1000)) println(problem_2(4000000)) println(problem_2b(4000000)) println(problem_2c(4000000)) println(problem_3(600851475143L)) println(problem_4()) println(problem_5(20)) println(problem_6(100)) println(problem_7b(10001)) // 51 seconds. :/ */ println(problem_8("7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450")) println(problem_9(1000)) println(problem_10(2000000)) println(problem_11( // cleaned up the data with sed -E -e 's/([0-9][0-9])/\1,/g' -e 's/0([0-9])/ \1/g' Array(Array( 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8), Array(49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0), Array(81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65), Array(52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91), Array(22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80), Array(24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50), Array(32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70), Array(67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21), Array(24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72), Array(21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95), Array(78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92), Array(16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57), Array(86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58), Array(19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40), Array( 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66), Array(88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69), Array( 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36), Array(20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16), Array(20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54), Array( 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48)))) //println(problem_12(500)) } }