Finds all Base-10 Factorions

factorion.swift

#!/usr/bin/env swift

// Inspired by @AlgebraFact, https://twitter.com/AlgebraFact/status/636205354544726017

import Foundation

//
// A factorion is a number that is equal to the sum of the factorials of its digits.
// There are only 4 factorions.
// 1 = 1!
// 2 = 2!
// 145 = 1! + 4! + 5!
// 40585 = 4! + 0! + 5! + 8! + 5!
//
// PROOF!

// We keep a factorial table for N<10 to speed up execution a bit
func factorial(number: Int) -> (Int) {
  switch(number) {
    case 0,1: return 1
    case 2: return 2
    case 3: return 6
    case 4: return 24
    case 5: return 120
    case 6: return 720
    case 7: return 5040
    case 8: return 40320
    case 9: return 362880
    default: return 0
  }
}

// If 10^(D-1)>9!*D, then the largest possible factorial-sum of size D (i.e. 9!*D) is less than D digits.
// This means it cannot be a factorion, not could any smaller factorial-sum of D digits.
var maxD = 1
for var D = 1; (pow(10.0,Double(D)-1.0) <= Double(factorial(9)*D));D++  {
    maxD = D
}
println("A factorion can't have more than " + String(maxD) + " digits")

// Now that we know D, find all the factorions with >= maxD digits
for var i = 0; i<=Int(pow(10.0,Double(maxD))); i++  {
    var digits = Array(String(i)).map{String($0).toInt()!} // i'd love to know a better way to do this in Swift
    var sum = digits.reduce(0) {$0 + factorial($1)}
    
    if (sum == i) { println("Found factorion: " + String(sum)) }
}

println("There are no more factorions!")

// QED