Write a function that accepts a positive integer and returns the number of steps in the integer's Fibonacci reduction. Write a function that accepts a positive integer and returns a list of fibonacho numbers no greater than the integer.
$ cat fbn.rkt #lang racket (require srfi/1) (define (fibonacci-residue n) ; Return the smallest non-negative number that results ; from reducing the given number by the Fibonacci ; sequence (i.e., (- (- (- (- n 1) 1) 2) 3)...). (do ((n n (- n a)) (b 0 a) (a 1 (+ b a))) ((< n a) n) #f)) (define (fibonacci-reduction-size n) ; Return the number of Fibonacci reductions needed to ; reduce the given number to 0. (do ((n n (fibonacci-residue n)) (c 0 (+ c 1))) ((< n 1) c) #f)) (define (is-fibonacho-number? n) ; Return true iff the given number is a fibonacho number. (let ((i (fibonacci-reduction-size n))) (do ((n (- n 1) (- n 1))) ((or (< n 1) (<= i (fibonacci-reduction-size n))) (< n 1)) #t))) (define (fibonacho-numbers-upto n) ; Return the list of all fibonacho numbers no greater than ; the given number. (filter is-fibonacho-number? (iota (+ n 1)))) (require rackunit) (for-each (lambda (n r) (check-eq? (fibonacci-residue n) r)) '(0 1 2 3 4 5 6 7 8 9 10 11 12) '(0 0 0 1 0 1 2 0 1 2 3 4 0)) (for-each (lambda (n r) (check-eq? (fibonacci-reduction-size n) r)) '(0 1 2 3 4 5 6 7 8 9 10 11 12 226 227) '(0 1 1 2 1 2 2 1 2 2 3 2 1 5 6)) (for-each (lambda (n r) (check-eq? (is-fibonacho-number? n) r)) '( 0 1 2 3 4 5 6 7 8 9 10 11 12) '(#t #t #f #t #f #f #f #f #f #f #t #f #f)) (for-each (lambda (n r) (check-equal? (fibonacho-numbers-upto n) r)) '(0 1 2 3 4) '((0) (0 1) (0 1) (0 1 3) (0 1 3))) $ mzscheme fbn.rkt $