Fibonacho Numbers
January 6, 2017
We begin by calculating the fibonacci numbers and the successive sums of fibonacci numbers:
> (define fibs (iterate 20 + 1 1)) > fibs (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) > (define sums (cdr (scan-left + 0 fibs))) > sums (1 2 4 7 12 20 33 54 88 143 232 376 609 986 1596 2583 4180 6764 10945 17710)
We can calculate the number of restarts for a given n like this: Consider n = 227. The largest fibonacci sum less than or equal to 227 is 143, so we count 1 and restart with n = 227 – 143 = 84. The largest fibonacci sum less than or equal to 84 is 54, so we count 2 and restart with n = 84 – 54 = 30. The largest fibonaci sum less than or equal to 30 is 20, so we count 3 and restart with n = 30 – 20 = 10. The largest fibonacci sum less than or equal to 10 is 7, so we count 4 and restart with n = 7 – 4 = 3. The largest fibonacci sum less than or equal to 3 is 2, so we count 5 and restart with n = 3 – 1 = 1. The largest fibonacci sum less than or equal to 1 is 1, so we count 6 and are finished. This program does the calculations for us:
(define (restarts n) (define (max-less-or-equal n xs) (let loop ((prev 0) (xs xs)) (if (< n (car xs)) prev (loop (car xs) (cdr xs))))) (let loop ((n n) (r 0)) (if (zero? n) r (loop (- n (max-less-or-equal n sums)) (+ r 1)))))
Here are some examples:
> (restarts 1) 1 > (restarts 3) 2 > (restarts 10) 3 > (restarts 11) 2 > (restarts 227) 6
We can use the records
function of a previous exercise to find all the fibonacho numbers less than a thousand:
> (for-each (lambda (idx/val) (display (cdr idx/val)) (display " ") (display (+ (car idx/val) 1)) (newline)) (records < (map restarts (range 1 1000)))) 1 1 2 3 3 10 4 30 5 84 6 227 7 603
Thus, the answer to the question posed at the beginning of the exercise is 227, which restarts 6 times.
Clever mathematicians have figured out that the nth fibonacho number FNn can be calculated in terms of fibonacci numbers Fn by the following formula:
FNn = F2n-1 – n
Using the calculation of the nth fibonacci number from a previous exercise, we write:
(define (fibonacho n) (- (fib (+ n n 1) n)))
The difference in the subscript is due to whether we count F0 as 0 or 1:
> (map fibonacho (range 1 50)) (1 3 10 30 84 227 603 1589 4172 10936 28646 75013 196405 514215 1346254 3524562 9227448 24157799 63245967 165580121 433494416 1134903148 2971215050 7778742025 20365011049 53316291147 139583862418 365435296134 956722026012 2504730781931 6557470319811 17167680177533 44945570212820 117669030460960 308061521170094 806515533049357 2111485077978013 5527939700884719 14472334024676182 37889062373143866 99194853094755456 259695496911122543 679891637638612215 1779979416004714145 4660046610375530264 12200160415121876692 31940434634990099858 83621143489848422929 218922995834555168977)
You can run the program at http://ideone.com/0sDZQo, where you will see functions iterate
, scan-left
, records
and fib
.
A solution in Racket.