Problem 2 ver. 2, 3, 4: logarithmic complexity
Find the sum of all the evenvalued terms in the Fibonacci sequence which do not exceed four million
The last time we had the straightforward O(n) solution: building a sequence, filtering out even values and adding them. We can improve a bit, noticing that actually, every third member of the Fibonacci sequence is even. We don't check then for evennes, but just jump over three components each time. This version 2 (I don't publish it here) should be several times faster, but still is O(n) in performance.
We can also express a member of the Fibonacci sequence via the third and sixth members from behind: and compute those values as the values of a new sequence: . This version 3 is essentially the same as the previous one and again, I don't publish it here.
The drastic improvement is obtained using the expression (I've added it and a proof to the wikipedia article, but they immediately reverted my changes as "unsourced"  this is pathetic). Now the sum is obtained just computing one Fibonacci member, and this can be done with O(log n).
Indeed, we can compute a Fibonacci member exponentiating the appropriate matrix, and this exponentiation, just like usual one, can be done with O(log n). I prefer this solution over using the golden ratio exponentiation formula (again logarithmic complexity), because only integeroperations are involved. So, this is the version 4 of the solution.

(define (fibonaccimemberlogarithmic n) (matrix2da12 (^2d fibonaccimatrix n)))

(define (fibonaccisumeven n) (/ ( (fibonaccimemberlogarithmic (+ n 2)) 1) 2))
I quickly outlined a class for 2D matrices and operations with it:

(definerecordtype matrix2d (fields a11 a12 a21 a22))

(define identitymatrix2d (makematrix2d 1 0 0 1))

(define fibonaccimatrix (makematrix2d 1 1 1 0))

(define (*2d A B) (let ([a11 (matrix2da11 A)]

[a12 (matrix2da12 A)]

[a21 (matrix2da21 A)]

[a22 (matrix2da22 A)]

[b11 (matrix2da11 B)]

[b12 (matrix2da12 B)]

[b21 (matrix2da21 B)]

[b22 (matrix2da22 B)])

(makematrix2d (+ (* a11 b11) (* a12 b21)) (+ (* a11 b12) (* a12 b22))

(+ (* a21 b11) (* a22 b21)) (+ (* a21 b12) (* a22 b22)))))

(define (^2dlinear A n) (applyntimes identitymatrix2d n (lambda (x) (*2d x A))))

(define (^2dlogarithmic A n) (if (= n 0) identitymatrix2d

(if (odd? n) (*2d A (^2dlogarithmic A ( n 1)))

(let ([B (^2dlogarithmic A (div n 2))]) (*2d B B)))))

(define ^2d ^2dlogarithmic)
The solution is O(1) in memory and O(log n) in performance  of course, where n denotes the index of a number in the Fibonacci sequence. And we have been questioned about the cutset, where members of a sequence are less than certain number. Then an additional function (closestfibonacciindex) comes in handy (see the wiki for explanation):

(define goldenratio (/ (+ 1 (sqrt 5)) 2))

(define (closestfibonacciindex f) (round (log (* f (sqrt 5)) goldenratio)))

(define (solution2optimized3 n) (fibonaccisumeven (closestfibonacciindex n)))
The final touch is asking ourselves about complexity of the (log) function. Well, it can be computed fast enough not to spoil complexity of the algo's main part.