Problem 3
Find the largest prime factor of a composite number.
is a very well known problem called factorization. The fundamental theorem of arithmetics comes in handy.
Bruteforce in this case is just iterating from 2 upwards, searching for factors:

(define (factorizebruteforce n)

(define (iterate n x) (if (> x n) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))

(iterate n 2))
If a factor is found, we divide the number by it, and continue with searching factors of a quotient. We don't need to start from 2 again (see the theorem).
The complexity for finding one factor is O(n) in the worst case. Let us optimize at once, stopping the iteration at sqrt(n). Indeed, a number cannot have a factor greater than its square root. This improves the worst case complexity drastically to O(\sqrt(n)) and this is the classical factorization algo.

(define (factorizesqrtcomplexity n)

(define (iterate n x) (if (> x (sqrt n)) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))

(iterate n 2))
Now, having written additional function (maxlist) for finding maximums through lists, we can solve the third problem:

(define (maxlist list) (foldleft max (car list) list))

(define (solution3bruteforce n) (maxlist (factorizebruteforce n)))

(define (solution3optimized1 n) (maxlist (factorizesqrtcomplexity n)))
I've written the generic procedure to generate lists iteratively:

(define (generatelistiteratively seed filter map step stop)

(define (iterate current) (if (stop current) '()

(let ([rest (iterate (step current))])

(if (filter current) (cons (map current) rest) rest))))

(iterate seed))
I've refactored (createfilterednumberslist from to filter) function into (numbersfilters) and added also (numbers) for future use:

(define (numbersfiltered from to filter) (generatelistiteratively from filter (lambda (x) x) (lambda (x) (+ x 1)) (lambda (x) (> x to))))

(define (numbers from to) (numbersfiltered from to (lambda (x) #t)))
Now the bruteforce solution for the problem 2
Find the sum of all the evenvalued terms in the Fibonacci sequence which do not exceed four million
looks like this:

(define (fibonacci to) (generatelistiteratively (cons 1 1) (lambda (pair) #t) (lambda (pair) (car pair)) (lambda (pair) (cons (cdr pair) (+ (car pair) (cdr pair)))) (lambda (pair) (> (car pair) to))))


(define (solution2bruteforce n) (sumnumbers (filter even? (fibonacci n))))
The complexity is O(n). I decided not to generate a filtered list, but rather first generate, then filter, (fibonacci) function goes to the library for future use (for future functions I will not mention placing into my library). This is an optimal algorithm for generating a Fibonacci sequence, unlike computing the nth member of it, which can be done more efficiently. However, for computing a sum of members, perhaps, there is a better solution, I will think about it later.
I refactored the previous solution and extracted such library functions, they could be useful in future:

(define (somedivides? n divisors) (exists (lambda (x) (divides? n x)) divisors))

(define (sumnumbers numbers) (foldleft + 0 numbers))

(define (createfilterednumberslist from to filter)

(define (iterate current) (if (> current to) '()

(let ([rest (iterate (+ current 1))])

(if (filter current) (cons current rest) rest))))

(iterate from))
I think for these algoritms, where we have to iterate through large lists of numbers, the laziness (e.g. in Haskell) would give slightly more elegant code at certain places.
The first problem solution now becomes:

(define (sumofmultiplesbruteforce upton divisors)

(let ([multiples (createfilterednumberslist 1 upton (lambda (x) (somedivides? x divisors)))])

(sumnumbers multiples)))


(define (solution1bruteforce n) (sumofmultiplesbruteforce ( n 1) '(3 5)))
For a list of divisors with length k the number of operations will be k*n. Actually, less than that because of shortcut (exists). Assuming k fixed and small, the complexity is still O(n). We could make use of the not yet written (createnumberslist) function and filter that afterwards instead of the (createfilterednumberslist) function, but let us take less space in memory at once.
Let us start with solutions to Project Euler problems. I will always start with bruteforce solutions if those are possible and later on post optimized solutions. Every solution will be given in Scheme (R6RS) along with quick estimate of complexity. The reason for solving those problems is training myself in Scheme and, of course, fun.
Find the sum of all the multiples of 3 or 5 below 1000.
Solution:

#!r6rs

(import (rnrs))


(define n 1000)


(define (divides? n x) (= (mod n x) 0))


(define (dividedby3or5? n) (or (divides? n 3) (divides? n 5)))


(define (adddividends n sum) (if (< n 1) sum (adddividends ( n 1) (if (dividedby3or5? n) (+ sum n) sum))))


(display (adddividends ( n 1) 0))
This is the simplest straightforward approach. Backwardrecursion is used, with tailrecursion optimization, which is obligatory for all Scheme implementations, will be transformed into iteration. Backward direction is to simplify a function signature (otherwise an extra parameter is needed).
The complexity is O(n), assuming the (mod) operation is atomic. More strictly, the number of operations is 2*n. By the way, in R5RS (mod) is called (remainder).
Nemerle is waiting, but it have to wait more, while I'm learning Scheme. I have a plan to solve some problems from Project Euler, first with bruteforce (however, it is not always possible), then using smarter ways, and post some solutions here under the tags "projecteuler" and "scheme".
Another thing, I am setting up currently a Gentoo Linux system on my workstation, so, some postings about this will come under the tag "gentoo". One of the reasons to install it is an unexpected difficulty with SATAdrives under Windows. The motherboard (Asus M3N78VM) supports SATAdevices in three modes: SATA (only three accessible), RAID and AHCI. The latest is preferable for me, as I need more than three drives.
It was understandable when WinXP 64bits (I didn't try any 32bits systems, as I need more than 4 Gb of RAM) refused to work in AHCImode despite all my tricks with this and that, particlularly, manufacturer's drivers embedding with the nLite tool. But when Vista x64 with proper drivers could not load after switching m/b into AHCI, I decided that it's time to try Linux again. I prefer Gentoo, one of the most hardcore distributions available.