Project Euler 23 in Scala (non-abundant sums)

Question

I recently overhauled my solution to Project Euler Problem 23 (which asks for the sum of all positive integers which cannot be written as the sum of two abundant numbers) to move it from an imperative style to a functional style and tried to increase its speed. However, the performance is still slow. I have clocked this solution at 58 seconds, and the older imperative solution at 64 seconds.

I am mainly hoping for feedback on how I could speed up the performance of this solution. The bottleneck appears to be at the notSumAbundant function. Is there a reliable way to reduce the number of values I need to check? Can this portion of notSumAbundant be made faster in any other way?

if(!abundantList.exists(x => abundantList.contains(num - x))) { 
  notSumAbundant(num + 1, num :: currentList) }

I am also hoping for feedback if my code falls short of functional programming best practices.

val t0 = System.nanoTime()

//function to find factors
def factors(num: Int) = {
    val max = (num / 2) + 1
    val factors = for(i <- 1 to max if num % i == 0) yield { i }
    factors
}

//function to find sums
def sumList(numList: IndexedSeq[Int]) = {
  val sum = numList.reduceLeft( _ + _ )
  sum
}

//function to recursively form list of abundant numbers
def abundance(num: Int, currentList: List[Int]): List[Int] = {
  if(num <= 20161){
  val numFactors = factors(num)
  val factorSum = sumList(numFactors)

  //if the number is abundant, prepend it to the running list of abundant numbers in the function call
  if(factorSum > num) { abundance(num + 1, num :: currentList) }
  else { abundance(num + 1, currentList) }
  } else return currentList
}

//all abundant numbers
val abundant = abundance(3, List())

//function to create a list of numbers which cannot be formed as the sum of two abundant numbers
def notSumAbundant(num: Int, currentList: List[Int]): List[Int] = {
  val abundantList = abundant.filter(_ < num)
  if(num <= 20161) { 
    //if it cannot be made as the sum of abundant numbers, prepend it to the current list when calling on the next number
    if(!abundantList.exists(x => abundantList.contains(num - x))) { 
      notSumAbundant(num + 1, num :: currentList) 
      } else { notSumAbundant(num + 1, currentList) }
 }  else return currentList
}

//store the values and then sum them
val answerList = notSumAbundant(1, List())
val answer = answerList.reduceLeft(_ + _)

val t1 = System.nanoTime()
println("Elapsed time: " + (t1 - t0) / 1000000000 + " seconds")
println(answer)

Update:

Changing the nonAbundantSum function to use a Set instead of a List worked to get this down to 2 seconds, as t. fochtman suggested:

val abundant = abundance(3, List()).toSet
//function to create a list of numbers which cannot be formed as the sum of two abundant numbers
def notSumAbundant(num: Int, currentSet: Set[Int]): List[Int] = {
  val abundantList = abundant.filter(_ < num)
  if(num <= 20161) { 
    //if it cannot be made as the sum of abundant numbers, prepend it to the current list when calling on the next number
    if(!abundantList.exists(x => abundantList.contains(num - x))) { 
      val updatedSet = (num :: currentSet.toList).toSet
      notSumAbundant(num + 1, updatedSet) 
      } else { notSumAbundant(num + 1, currentSet) }
 }  else return currentSet.toList
}

//store the values and then sum them
val answerList = notSumAbundant(1, Set())

Answer 1

I was able to reduce the run time of your code to a few seconds (2 seconds on my computer) by changing the type of abundant from a List to an immutable Set.

You were correct that !abundantList.exists(x => abundantList.contains(num - x)) was the major bottleneck in your code.

This is a bottleneck because checking that an item exists in a List means inspecting every item in the List until we find it or reach the end of the List. Fortunately we can use a Set (which under the hood is supported by the immutable.HashMap class) and reduce the search time for objects from linear to effectively constant.

Notice that in the code below I simply applied the method toSet to your abundance function converting the returned List to a Set.

val abundant = abundance(3, List()).toSet

def notSumAbundant(num: Int, currentList: List[Int]): List[Int] = {
  if(num <= n) {
    val abundantSet: Set[Int] = abundant.filter(_ < num)
    if (!abundantSet.exists(x => abundantSet.contains(num - x))) {
      notSumAbundant(num + 1, num :: currentList)
    } else
      notSumAbundant(num + 1, currentList)
  } else
    currentList
}

For more information check out this nice write up on Scala collections that is co-written by the creator of Scala, Martin Odersky.