Skip to content

Instantly share code, notes, and snippets.

@iiska
Created January 31, 2012 15:11
Show Gist options
  • Save iiska/1710981 to your computer and use it in GitHub Desktop.
Save iiska/1710981 to your computer and use it in GitHub Desktop.
Scheme solution for Project-Euler problem 50
;; The prime 41, can be written as the sum of six consecutive primes: 41
;; = 2 + 3 + 5 + 7 + 11 + 13
;;
;; This is the longest sum of consecutive primes that adds to a prime
;; below one-hundred.
;;
;; The longest sum of consecutive primes below one-thousand that adds to
;; a prime, contains 21 terms, and is equal to 953.
;;
;; Which prime, below one-million, can be written as the sum of the most
;; consecutive primes?
(define (is-prime? number)
(let ((max (sqrt number)))
(let loop ((i 2))
(if (<= i max) (if (eq? (modulo number i) 0) #f (loop (+ i 1))) #t))))
(define (next-prime from)
(let loop ((i from))
(if (is-prime? i) i (loop (+ i 2)))))
(define (prev-prime from)
(let loop ((i from))
(if (is-prime? i) i (loop (- i 2)))))
(define (problem-50)
;; First find largest sum of primes below million
(let prime-summer ((i 3)(sum 2)(last-prime 2))
(if (< (+ sum i) 1000000)
(if (is-prime? i)
(prime-summer (+ i 2) (+ sum i) i)
(prime-summer (+ i 2) sum last-prime))
;; Make binary tree search kind of algorithm for finding the
;; prime with longest sequence using depth-first search
;; Stop immediately after we find largest prime.
(let max-prime ((c (list sum 2 last-prime))(nodes '()))
(if (is-prime? (car c))
c
(if (null? nodes)
(max-prime (list (- (car c) (cadr c)) (next-prime (cadr c)) (caddr c))
(list (list (- (car c) (caddr c)) (cadr c) (prev-prime (caddr c)))))
(max-prime (car nodes)
(append
(list
(list (- (car c) (cadr c)) (next-prime (cadr c)) (caddr c)) ;; Left branch
(list (- (car c) (caddr c)) (cadr c) (prev-prime (caddr c)))) ;; Right branch
(cdr nodes)))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment