# Projecteuler.net Problem 2 using collection pipeline Pattern

I solve projecteuler.net Problem 2 deferent way

1. Generate number from 1 to range ex 100 and get the even number
2. Get Fibonacci numbers from list
3. Reduce array

I have one problem with a large set of numbers like 1000000 or 4000000. can I ask how can I optimize the code? I am trying to solve the problem as a collection pipeline

swift code

Luckily, the former condition isPerfectSquare(5 * $0 *$0 + 4) with $0 = 0 is true, and so, there is no need to evaluate the latter. # Conciseness We don't really need the collection pipeline pattern since the initial numbers won't be transformed until the reduce. With the above remarks taken into consideration, here is what your code would look like: let result = (0..<100) .filter {$0 % 2 == 0 }
.filter { isPerfectSquare(5 * $0 *$0 + 4) || isPerfectSquare(5 * $0 *$0 - 4) }
.reduce(0, +)


You could make it more concise: avoiding the first filter by using a stride instead:

let result = stride(from: 0, to: 100, by: 2)
.filter { isPerfectSquare(5 * $0 *$0 + 4) || isPerfectSquare(5 * $0 *$0 - 4) }
.reduce(0, +)


Or, if you like to use one reduce only, your code will become:

let result = stride(from: 2, to: 100, by: 2)
.reduce(into: 0) { total, element in
if isFibonacci(element) { total += element }
}

func isFibonacci(_ n: Int) -> Bool {
let square = n * n
return isPerfectSquare(5 * square + 4) || isPerfectSquare(5 * square - 4)
}

func isPerfectSquare(_ n: Int) -> Bool {
guard n >= 0 else { return false }
let root = Int(sqrt(Double(n)))
return root * root == n
}


# Performance

Like you said, in your original code, you could avoid creating intermediate arrays in the pipeline by using the lazy keyword. The worst part about the original code is that you have to check for every number if it's even, and then check if it's a Fibonacci number. And there not so many Fibonacci numbers up to 4,000,000.

You could notice that in the Fibonacci series, every third element, is even:

fib(0) fib(1) fib(2) fib(3) fib(4) fib(5) fib(6) fib(7) ...
0 1 1 2 3 5 8 13 ...

Now, all we have to do is sum every third element in the Fibonacci series as long as it is less than the given limit (in your case 4,000,000). We could get the Fibonacci numbers using recursion, or Dynamic Programming, or Matrix Exponentiation, or more simply using the formula:

$$Fib[n] = \frac{A - B}{\sqrt{5}}$$

with:

$$A = (\frac{1 + \sqrt{5}}{2})^{n}$$ $$B = (\frac{1 - \sqrt{5}}{2})^{n}$$

Here is code for the new approach:

let sqrt5 = sqrt(5)
var sum = 0

stride(from: 3, through: 4_000_000, by: 3)
.drop { n in
let fn = fib(n)
if fn <= 4_000_000 {
sum += fn
return true
}
return false
}

func fib(_ n: Int) -> Int {
let numerator = pow((1 + sqrt5)/2, Double(n)) - pow((1.0 - sqrt5)/2.0, Double(n))
return Int(numerator/sqrt5)
}

print(sum)      //4613732


drop(while:) makes sure we stop once the Fibonacci number exceeds 4,000,000.

Let's calculate a better end for the stride:
Since B is negligible, we could approximate the upper limit to which we should be calculating Fibonacci numbers:

$$Fib[n_{max}] \simeq \frac{(\frac{1 + \sqrt{5}}{2})^{n_{max}}}{\sqrt{5}} \leqslant 4\cdot10^{6}$$ $$\Rightarrow (\frac{1 + \sqrt{5}}{2})^{n_{max}} \leqslant 4\cdot\sqrt{5}\cdot10^{6}$$ $$\Rightarrow n_{max}\cdot\ln(\frac{1 + \sqrt{5}}{2}) \leqslant \ln(4\cdot\sqrt{5}\cdot10^{6})$$ $$\Rightarrow n_{max} \leqslant \frac{\ln(4\cdot\sqrt{5}\cdot10^{6})}{\ln(\frac{1 + \sqrt{5}}{2})}$$ $$\Rightarrow n_{max} \leqslant 33.26$$ $$\Rightarrow n_{max} = 33$$

Lucky for us, 33 is a multiple of 3!

Finally, here is the solution to the problem using the collection pipeline pattern:

let sqrt5 = sqrt(5)

func fib(_ n: Int) -> Int {
let numerator = pow((1 + sqrt5)/2, Double(n)) - pow((1.0 - sqrt5)/2.0, Double(n))
return Int(numerator/sqrt5)
}

let result = stride(from: 3, through: 33, by: 3)
.lazy
.map(fib)
.reduce(0, +)

print(result)   //4613732


# One more thing 🤔

There has to be a better way, and indeed, there is an elegant solution to this problem. Enjoy!