Project Euler #2 (Even Fibonacci numbers) in Swift

Question

I figured working through Project Euler problems in Swift would be a good way to learn any tips or tricks. For example, tuples are something I'm not used to using, but they proved useful here. Using things makes me more confident with them, so perhaps this will help me find other uses for them in the future.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here is my solution:

func swap(inout left: Any, inout right: Any) {
    let swap = left
    right = left
    left = swap
}

func findNextEvenFibonacci(var firstFibonacci: Int = 0, var secondFibonacci: Int = 1) -> (Int, Int) {
    do {
        firstFibonacci += secondFibonacci
        swap(&firstFibonacci, &secondFibonacci)
    } while firstFibonacci % 2 != 0

    return (firstFibonacci, secondFibonacci)
}

let maxFibonacci: Int = 4_000_000
var fibonacci: (first: Int, next: Int) = (0,1)
var sumOfEvenFibonnaccis: Int = 0

while fibonacci.next < maxFibonacci {
    fibonacci = findNextEvenFibonacci(firstFibonacci: fibonacci.first, secondFibonacci: fibonacci.next)
    sumOfEvenFibonnaccis += fibonacci.first
}

let answer = sumOfEvenFibonnaccis

Answer 1

The following is similar to Flambino's approach, but creates a Swift SequenceType so that you can use the Swift library functions filter() and reduce() to iterate over the elements:

struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> GeneratorOf<Int> {
        var current = 1
        var next = 1
        return GeneratorOf<Int>() {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = lazy(FibonacciSequence(upperBound: 4_000_000))
let sum = reduce(fibseq.filter { $0 % 2 == 0 }, 0) { $0 + $1 }

See here for more information about sequences and generators. This nice application made me actually understand how you can create your own sequences.

lazy() creates a LazySequence, whose filter() method returns the elements "on demand", e.g. as needed in the summation. The filter() function would return an array of all even Fibonacci numbers before starting the summation. (Kudos to @jtbandes for his suggestion).

---

Update: Due to major changes in the Swift programming language, the above code does not compile anymore with the current Swift 2.1/Xcode 7. Here is an updated version fore anybody's convenience:

struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> AnyGenerator<Int> {
        var current = 1
        var next = 1
        return anyGenerator {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = FibonacciSequence(upperBound: 4_000_000).lazy
let sum = fibseq.filter { $0 % 2 == 0 }.reduce(0) { $0 + $1 }

Answer 2

I can only suggest a faster* math-based algorithm:

The fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and etc.

The even ones are: 0 at index 0, 2 at index 3, 8 at index 6, 34 at index 9 and so on.

This suggests that every third fibonacci number is even (starting from 0). Let's try and prove this by induction:

WARNING MATH AHEAD

We have already proved a few base cases: index 0 and 3 are even fibonacci numbers.

Suppose Fibonacci(3 * n) is even.

Fibonacci(3 * (n + 1)) = Fibonacci(3n + 3)
                       = Fibonacci(3n + 2) + Fibonacci(3n + 1)
                       = 2 * Fibonacci(3n + 1) + Fibonacci(3n)

Since 2 * Fibonacci(3n + 1) is even, and by the induction hypothesis, Fibonacci(3n) is even, which means the sum is even as well, and so Fibonacci(3 * (n+1)) must also be even. Thus induction is complete and we have proved that every third Fibonacci number is even.

Next we have to prove that all the other numbers are not even. Since we know Fibonacci(1) = 1 is odd, then using the same logic as previously, we can show that Fibonacci(3n + 1) = 2 * Fibonacci(3n - 1) + Fibonacci(3n + 1) which is guaranteed to be odd. Similarly the result will be obtained for all n = 2 mod 3.

END OF MATH

This simplifies your task to just summing every third fibonacci number, with no need to check if it is even or not, as we have just proved they are the only even fibonacci numbers.

• (DISCLAIMER) In the Python scripts I wrote to test this, the difference in time wasn't obvious until roughly 10¹⁰⁰⁰

Answer 3

Disclaimer: This is the most I've ever written in Swift. In other words, I barely know what I'm doing.

My gut feeling, Swift or no Swift, is the the findNextEvenFibonacci function is a little too specific on its own. I'd probably have another function that just generates the next Fibonacci number - even or odd. Its parity is then checked when summing up.

Also, I don't know how to feel about the tuple. While it's a simple, direct solution a tuple also feels a little opaque. Given that structs are quite powerful in Swift, a fully declared struct with some functions might be better.

Here's my naïve attempt:

struct FibonacciPair {
    var current: Int
    var previous: Int

    // using the name successor, since that's what Int
    // calls its next-in-sequence function
    func successor() -> FibonacciPair {
        return FibonacciPair(current: current + previous, previous: current)
    }
}

var generator = FibonacciPair(current: 1, previous: 1)
var sum = 0

while generator.current < 4_000_000 {
    if generator.current % 2 == 0 {
        sum += generator.current
    }
    generator = generator.successor()
}

let answer = sum

This is of course the sort of task that can be accomplished in a hundred different ways - the above is just what came to my mind first.

Aside: A few of those hundred other ways would be wholly procedurally without any functions or structs or other such contraptions - just a while loop and some variables. But I figure the idea here is also to play around with Swift.

Perhaps it'd be reasonable to extend Int with an isEven function, while we're at it. It's basic enough to be of general use as a core type extension, and it'd clean up the while loop above a little bit

extension Int {
    func isEven() -> Bool {
        return self % 2 == 0
    }
}

An alternative approach might be a Fibonacci-number generator that takes a closure. If only a closure could break the loop in which it's called instead of returning a bool... oh, well

func eachFibonacciNumber(iterator: (Int) -> (Bool)) {
    var current = 1
    var previous = 0

    while iterator(current + previous) {
        swap(&previous, &current)
        current += previous
    }
}

var sum = 0

eachFibonacciNumber() {
    // note: I definitely should be checking $0 < limit *before*
    // incrementing the sum... but it looks prettier if I don't :P
    if $0.isEven() { sum += $0 }
    return $0 < 4_000_000
}

let answer = sum

eachFibonacciNumber is a terrible Ruby'esque-but-not-really name, but you get the idea.

The limit could also just be an argument of course, which would avoid the bool return:

func fibonacciNumbersUpTo(limit: UInt, iterator: (Int) -> ()) {
    var current = 1
    var previous = 0

    while current < limit {
        iterator(current)
        swap(&previous, &current)
        current += previous
    }
}

var sum = 0
fibonacciNumbersUpTo(4_000_000) {
  if $0.isEven() { sum += $0 }
}

That's is probably the nicest, most straightforward of the bunch, in my opinion.

In either case, though, the idea is to have a way to get the regular Fibonacci sequence, and then deciding what to do with each number, rather than using a specific "only even Fibonacci numbers" device. Of course, either of the above could be form the basis for such a device.

In any case, going through Project Euler with Swift is a nice idea - I'll probably do the same :)

Answer 4

Here is an approach using a general RecurrenceRelation struct which can be used to write any recurrence, not just the Fibonacci sequence (the Fibonacci sequence is defined by initial conditions (1,1) and the relation T[n] = T[n-1] + T[n-2]). I also define takeWhile as an extension to LazySequence so the functionality doesn't have to be built into RecurrenceRelation — Swift has a built-in prefix but it seems to be designed for random-access collections only.

struct RecurrenceRelation<E> : SequenceType {
    let initialCondition: [E]
    let relation: (T: [E], n: Int) -> E

    init(_ initialCondition: [E], relation: (T: [E], n: Int) -> E) {
        self.initialCondition = initialCondition
        self.relation = relation
    }

    func generate() -> GeneratorOf<E> {
        var memory = initialCondition
        var i = 0

        return GeneratorOf<E> {
            if i < memory.count { return memory[i++] }
            memory.append(self.relation(T: memory, n: memory.count))
            memory.removeAtIndex(0)
            return memory.last
        }
    }
}

extension LazySequence {
    func takeWhile(pred: S.Generator.Element -> Bool) -> LazySequence<SequenceOf<S.Generator.Element>> {
        return lazy(SequenceOf { () -> GeneratorOf<S.Generator.Element> in
            var g = self.generate()
            return GeneratorOf<S.Generator.Element> {
                let n = g.next()
                if n == nil || !pred(n!) { return nil }
                return n
            }
        })
    }
}

let fib = RecurrenceRelation([1, 1]) { (T, n) in T[n-1] + T[n-2] }

let n = reduce(lazy(fib).takeWhile { $0 < 4_000_000 }.filter { $0 % 2 == 0 }, 0, +)