Hofstadter Figure-Figure sequences: Difference between revisions
({{header|Common Lisp}}) |
m (comment out of lang tag) |
||
Line 21: | Line 21: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
;;; equally doable with a list |
<lang lisp>;;; equally doable with a list |
||
(flet ((seq (i) (make-array 1 :element-type 'integer |
|||
:initial-element i |
:initial-element i |
||
:fill-pointer 1 |
:fill-pointer 1 |
Revision as of 21:25, 22 October 2011
These two sequences of positive integers are defined as:
- The sequence is further defined as the sequence of positive integers not present in .
Sequence R starts: 1, 3, 7, 12, 18, ...
Sequence S starts: 2, 4, 5, 6, 8, ...
Task:
- Create two functions named ffr and ffs that when given n return R(n) or S(n) respectively.
(Note that R(1) = 1 and S(1) = 2 to avoid off-by-one errors). - No maximum value for n should be assumed.
- Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
- Calculate and show that the first 40 values of ffr plus the first 960 values of ffs include all the integers from 1 to 1000 exactly once.
- References
- Sloane's A005228 and A030124.
- Wolfram Mathworld
- Wikipedia: Hofstadter Figure-Figure sequences.
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))) (flet ((extend-r ()
(let* ((l (1- (length rr))) (r (+ (aref rr l) (aref ss l))) (s (aref 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)) (aref rr (1- n)))
(defun seq-s (n)
(loop while (> n (length ss)) do (extend-r)) (aref ss (1- n))))))
(format t "First of R: ~a~%" (loop for i from 1 to 10 collect (seq-r i)))
(mapl (lambda (l) (if (and (cdr l) (/= (1+ (car l)) (cadr l))) (error "not in sequence")))
(sort (append (loop for i from 1 to 40 collect (seq-r i))
(loop for i from 1 to 960 collect (seq-s i))) #'<))
- if we reached here, the first 1000 numbers were in sequence
(princ "Ok")</lang>output<lang>First of R: (1 3 7 12 18 26 35 45 56 69) Ok</lang>
Python
<lang python>def ffr(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return ffr.r[n] except IndexError: r, s = ffr.r, ffs.s ffr_n_1 = ffr(n-1) lastr = r[-1] # extend s up to, and one past, last r s += list(range(s[-1] + 1, lastr)) if s[-1] < lastr: s += [lastr + 1] # access s[n-1] temporarily extending s if necessary len_s = len(s) ffs_n_1 = s[n-1] if len_s > n else (n - len_s) + s[-1] ans = ffr_n_1 + ffs_n_1 r.append(ans) return ans
ffr.r = [None, 1]
def ffs(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return ffs.s[n] except IndexError: r, s = ffr.r, ffs.s for i in range(len(r), n+2): ffr(i) if len(s) > n: return s[n] raise Exception("Whoops!")
ffs.s = [None, 2]
if __name__ == '__main__':
first10 = [ffr(i) for i in range(1,11)] assert first10 == [1, 3, 7, 12, 18, 26, 35, 45, 56, 69], "ffr() value error(s)" print("ffr(n) for n = [1..10] is", first10) # bin = [None] + [0]*1000 for i in range(40, 0, -1): bin[ffr(i)] += 1 for i in range(960, 0, -1): bin[ffs(i)] += 1 if all(b == 1 for b in bin[1:1000]): print("All Integers 1..1000 found OK") else: print("All Integers 1..1000 NOT found only once: ERROR")</lang>
- Output
ffr(n) for n = [1..10] is [1, 3, 7, 12, 18, 26, 35, 45, 56, 69] All Integers 1..1000 found OK