Programming Praxis

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 FN_n can be calculated in terms of fibonacci numbers F_n by the following formula:

FN_n = F_2n-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 F₀ 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.

Pages: 1 2