>>129
Here, this version should work with Guile, Chez Scheme and Chicken.
(define (sequence n)
(let* ((rs 7) ; Smallest R value unused.
(ss (let ((n (list 5))) ; Queue of S values.
(cons n n)))
(r 7) ; Current R value.
(s 5) ; Current S value.
(negsum -7) ; Negative sum of unused R values.
(pos 3) ; Smallest n in the queues.
(n (- n 1))) ; Off by one.
(let loop ((i 4))
(when (<= (+ s r) (+ i n))
(set! r (+ r s))
(set! s (+ s 1))
(set! negsum (- negsum r))
(when (= s rs)
(set! rs (+ rs (caar ss)))
(set! negsum (+ negsum s))
(set! s (+ s 1))
(set! pos (+ pos 1))
(set-car! ss (cdar ss)))
(let ((n (list s)))
(set-cdr! (cdr ss) n)
(set-cdr! ss n))
(loop (+ i 1))))
(list pos negsum r (cadr ss))))
(define (sum m n)
(* (/ (- m n -1) 2) (+ m n)))
(define (jump n)
(cond
((= n 1) 1)
((= n 2) 3)
((= n 3) 7)
((= n 4) 12)
(else
(let* ((seq (sequence n))
(m (list-ref seq 0))
(ns (list-ref seq 1))
(rx (list-ref seq 2))
(sx (list-ref seq 3))
(nx (+ m -1))
(s (+ sx (- n nx))))
(+ rx (sum (- s 1) sx) ns)))))Both perform better on R(10^13) but slow down soon after.
>>126
You might want to run a benchmark that actually stresses bigints. At least for my case, R(10^13) spends at least 80% of its time in GC. If I turn off the GC (GC_DONT_GC=0 guile hofstadter.scm) it is much faster, but at R(10^15), memory consumption blows up.