4
\$\begingroup\$

I just started learning Racket as my first lisp dialect so after getting used to the syntax I implemented the Recamán's sequence.

Apart from the style, I'd also like to know if my code is a linear iteration or not. I kind of get the idea but I don't know how to be sure it is.

#lang racket

(define (recaman-seq size)
  (define (recaman-iter curr-seq n goal)
    (if (= n goal)
        (reverse curr-seq)
        (cond
          [(and (= n 0) (empty? curr-seq))
           (recaman-iter (list n) (+ n 1) goal)]
          [else
           (define a (- (car curr-seq) n))
           (define b (+ (car curr-seq) n))
           (define is-new (not (member a curr-seq)))
           (cond
             [(and (positive? a) is-new)
              (recaman-iter (list* a curr-seq) (+ n 1) goal)]
             [else
              (recaman-iter (list* b curr-seq) (+ n 1) goal)])])))
  (recaman-iter '() 0 (+ size 1)))

(recaman-seq 10)
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

This code is not exactly linear as member is a o(n) time function and grown in proportion to curr-seq, making the whole function about O(n^2).

However without an algorithmic trick, the function requires a search of past results, and the best search that I know of on a mutable structure is O(log (n)), so the best you can hope for here is O(n*log(n)). But this is only if you go off to infinity.

This sequence seems reasonably dense, so you could probably create a boolean vector a bit bigger than the sequence initialized to true,and as you add numbers to the sequence flip the value of that index to false.

First to translate to scheme...

(define (recaman-seq size)
  (define (recaman-iter curr-seq n goal)
    (if (= n goal)
        (reverse curr-seq)
        (cond
          ((and (= n 0) (null? curr-seq))
           (recaman-iter (list n) (+ n 1) goal))
          (else
           (let* ((a      (- (car curr-seq) n))
                 (b      (+ (car curr-seq) n))
                 (is-new (not (member a curr-seq))))
           (cond
             ((and (positive? a) is-new)
              (recaman-iter (cons a curr-seq) (+ n 1) goal))
             (else
              (recaman-iter (cons b curr-seq) (+ n 1) goal))))))))
  (recaman-iter '() 0 (+ size 1)))

(recaman-seq 10) ]=>(0 1 3 6 2 7 13 20 12 21 11)

Next making some modifications, using a let to make a temperary vector, changing the define and call with a named loop,

;lang rsr5

(define (recaman-seq size)
 (let ((rman-vect (make-vector (* 10 size) #t))) 
;;hopefully generous enough
  (let recaman-iter ((curr-seq '()) (n 0))
;; goal is unneccesary, if and cond are essentially the same, nest them
    (cond ((> n size)
           (reverse curr-seq))
          ((and (= n 0) (null? curr-seq) (vector-ref rman-vect 0))
           (vector-set! rman-vect 0 #f)
;;Mark number as used, this is a side effect,not a returned value
           (recaman-iter (cons n curr-seq) (+ n 1)))
          (else
           (let* ((a      (- (car curr-seq) n))
                 (b      (+ (car curr-seq) n)))
             (cond ((and (> a 0))  (vector-ref rman-vect a)
                    (vector-set! rman-vect a #f) 
                    (recaman-iter (cons a curr-seq) (+ n 1)))
             (else (vector-set! rman-vect b #f)
                   (recaman-iter (cons b curr-seq) (+ n 1))))))))))

Can get the first 500,000 terms that way before I run out of memory.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Right I didn't think about nesting the if into the cond. That vector of booleans is super clever ! May I ask how can you tell that this sequence is dense ? \$\endgroup\$ Aug 8, 2018 at 9:36
  • \$\begingroup\$ Converting a search or complex function into a table/vector lookup is a fairly common way to trade memory for speed. There is a bit-string data structure that can be used in a similar way, but is much more memory compact. \$\endgroup\$
    – WorBlux
    Aug 25, 2018 at 19:50
  • \$\begingroup\$ As for the density it was a guess. I looked at the fact the algorithm prefers subtraction and the higher the number relative in the sequence, the more likely there is an empty spot below and the first 70 terms available from you link. There are a few related sequences on the site dealing with height of the terms that give a better idea on how dense it it. No real rigorous proof that it is dense though. The original FORTRAN code submitted with the sequence may be worth a look as well. oeis.org/A005132/a005132.txt \$\endgroup\$
    – WorBlux
    Aug 25, 2018 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.