401.sps

#!r6rs

;; Project Euler - Problem 401
;; Order = O(sqrt(N))
;;
;; $ time racket 401.sps
;; *********
;;
;; real 0m43.008s
;; user 0m41.420s
;; sys  0m0.304s


(import (rnrs))

(define N #e1e15)
(define M #e1e9)

(define (sum-squares n)
  (* n (+ n 1) (+ n n 1) 1/6))

(define (print . xs)
  (for-each display xs)
  (newline))

(let solve ([a 1] [x (div N 1)] [p (sum-squares (div N 1))]
            [b 2] [y (div N 2)] [q (sum-squares (div N 2))]
            [sum 0])
  (cond
   [(< x a) (print (mod sum M))]
   [(= x a) (print (mod (+ sum (* a a x)) M))]
   [else (let* ([c (+ b 1)]
                [z (div N c)]
                [r (sum-squares z)])
           (solve b y q c z r (+ sum (* a a x) (* a (- p q)))))]))