; recognizing fibonacci numbers
(define (square? n)
(define (isqrt n)
(if (not (and (positive? n) (integer? n)))
(error 'isqrt "must be positive integer")
(let loop ((x n))
(let ((y (quotient (+ x (quotient n x)) 2)))
(if (< y x) (loop y) x)))))
(let ((x (isqrt n)))
(= (* x x) n)))
(define (fibonacci? x)
(if (< x 1) #f
(let loop ((prev 1) (fib 1))
(if (< fib x) (loop fib (+ fib prev))
(= fib x)))))
(display (fibonacci? 13)) (newline)
(display (fibonacci? 15)) (newline)
(define (fibonacci? x)
(let ((5xx (* 5 x x)))
(or (square? (+ 5xx 4))
(square? (- 5xx 4)))))
(display (fibonacci? 13)) (newline)
(display (fibonacci? 15)) (newline)
OyByZWNvZ25pemluZyBmaWJvbmFjY2kgbnVtYmVycwoKICAoZGVmaW5lIChzcXVhcmU/IG4pCiAgICAoZGVmaW5lIChpc3FydCBuKQogICAgICAoaWYgKG5vdCAoYW5kIChwb3NpdGl2ZT8gbikgKGludGVnZXI/IG4pKSkKICAgICAgICAgIChlcnJvciAnaXNxcnQgIm11c3QgYmUgcG9zaXRpdmUgaW50ZWdlciIpCiAgICAgICAgICAobGV0IGxvb3AgKCh4IG4pKQogICAgICAgICAgICAobGV0ICgoeSAocXVvdGllbnQgKCsgeCAocXVvdGllbnQgbiB4KSkgMikpKQogICAgICAgICAgICAgIChpZiAoPCB5IHgpIChsb29wIHkpIHgpKSkpKQogICAgKGxldCAoKHggKGlzcXJ0IG4pKSkKICAgICAgKD0gKCogeCB4KSBuKSkpCgooZGVmaW5lIChmaWJvbmFjY2k/IHgpCiAgKGlmICg8IHggMSkgI2YKICAgIChsZXQgbG9vcCAoKHByZXYgMSkgKGZpYiAxKSkKICAgICAgKGlmICg8IGZpYiB4KSAobG9vcCBmaWIgKCsgZmliIHByZXYpKQogICAgICAgICg9IGZpYiB4KSkpKSkKCihkaXNwbGF5IChmaWJvbmFjY2k/IDEzKSkgKG5ld2xpbmUpCihkaXNwbGF5IChmaWJvbmFjY2k/IDE1KSkgKG5ld2xpbmUpCgooZGVmaW5lIChmaWJvbmFjY2k/IHgpCiAgKGxldCAoKDV4eCAoKiA1IHggeCkpKQogICAgKG9yIChzcXVhcmU/ICgrIDV4eCA0KSkKICAgICAgICAoc3F1YXJlPyAoLSA1eHggNCkpKSkpCgooZGlzcGxheSAoZmlib25hY2NpPyAxMykpIChuZXdsaW5lKQooZGlzcGxheSAoZmlib25hY2NpPyAxNSkpIChuZXdsaW5lKQ==