Hofstadter Figure-Figure sequences: Difference between revisions

=={{header|Common Lisp}}==

<lang lisp>;;; equally doable with a list

(flet ((seq (i) (make-array 1 :element-type 'integer

:initial-element i

:fill-pointer 1

:adjustable t)))

(let ((rr (seq 1)) (ss (seq 2)))

(labels ((extend-r ()

(let* ((l (1- (length rr)))

(r (+ (aref rr l) (aref ss l)))

(s (elt ss (1- (length ss)))))

(vector-push-extend r rr)

(loop while (<= s r) do

(if (/= (incf s) r)

(vector-push-extend s ss))))))

(defun seq-r (n)

(loop while (> n (length rr)) do (extend-r))

(elt rr (1- n)))

(defun seq-s (n)

(loop while (> n (length ss)) do (extend-r))

(elt ss (1- n))))))

(defun take (f n)

(loop for x from 1 to n collect (funcall f x)))

(format t "First of R: ~a~%" (take #'seq-r 10))

(mapl (lambda (l) (if (and (cdr l)

(/= (1+ (car l)) (cadr l)))

(error "not in sequence")))

(sort (append (take #'seq-r 40)

(take #'seq-s 960))

#'<))

(princ "Ok")</lang>output<lang>First of R: (1 3 7 12 18 26 35 45 56 69)

Ok</lang>

=={{header|C}}==

<lang c>#include <stdio.h>

#include <stdlib.h>

// simple extensible array stuff

typedef unsigned long long xint;

typedef struct {

size_t len, alloc;

xint *buf;

} xarray;

xarray rs, ss;

void setsize(xarray *a, size_t size)

{

size_t n = a->alloc;

if (!n) n = 1;

while (n < size) n <<= 1;

if (a->alloc < n) {

a->buf = realloc(a->buf, sizeof(xint) * n);

if (!a->buf) abort();

a->alloc = n;

}

}

void push(xarray *a, xint v)

{

while (a->alloc <= a->len)

setsize(a, a->alloc * 2);

a->buf[a->len++] = v;

}

// sequence stuff

void RS_append(void);

xint R(int n)

{

while (n > rs.len) RS_append();

return rs.buf[n - 1];

}

xint S(int n)

{

while (n > ss.len) RS_append();

return ss.buf[n - 1];

}

void RS_append()

{

int n = rs.len;

xint r = R(n) + S(n);

xint s = S(ss.len);

push(&rs, r);

while (++s < r) push(&ss, s);

push(&ss, r + 1); // pesky 3

}

int main(void)

{

push(&rs, 1);

push(&ss, 2);

int i;

printf("R(1 .. 10):");

for (i = 1; i <= 10; i++)

printf(" %llu", R(i));

char seen[1001] = { 0 };

for (i = 1; i <= 40; i++) seen[ R(i) ] = 1;

for (i = 1; i <= 960; i++) seen[ S(i) ] = 1;

for (i = 1; i <= 1000 && seen[i]; i++);

if (i <= 1000) {

fprintf(stderr, "%d not seen\n", i);

abort();

}

puts("\nfirst 1000 ok");

return 0;

}</lang>

=={{header|PicoLisp}}==

<lang PicoLisp>(setq *RNext 2)

(de ffr (N)

(cache '(NIL) N

(if (= 1 N)

1

(+ (ffr (dec N)) (ffs (dec N))) ) ) )

(de ffs (N)

(cache '(NIL) N

(if (= 1 N)

2

(let S (inc (ffs (dec N)))

(when (= S (ffr *RNext))

(inc 'S)

(inc '*RNext) )

S ) ) ) )</lang>

Test:

<lang PicoLisp>: (mapcar ffr (range 1 10))

-> (1 3 7 12 18 26 35 45 56 69)

: (=

(range 1 1000)

(sort (conc (mapcar ffr (range 1 40)) (mapcar ffs (range 1 960)))) )

-> T</lang>