# fibonacho numbers

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

\$
```