Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BECAUSE TYPE SYSTEMS ARE SUPPOSED TO RUN COMPUTATIONS!!1!1!

Write a program in your favourite programming language to compute the sum of the first N even numbers in the Fibonacci sequence, then display the sum of its digits.

E.g.: Where N = 5, the answer is 17, since:

  1. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...;
  2. The first 5 even numbers are 0, 2, 8, 34, and 144;
  3. The sum of these numbers is 188;
  4. The sum of the digits of this answer is 17 (1 + 8 + 8).

The implementation below is written in typo: https://github.com/seliopou/typo, a Scheme dialect that runs on Haskell's type system.

;; Co-recursive definition of Fibonacci for K index
;; N N N → N
(define (fib k a b)
(if (== k 0) a
(fib (- k 1) b (+ a b))))
;; Sums the digits of a number
;; N → N
(define (sum_digits n)
(if (== n 0) 0
(+ (% n 10) (sum_digits (/ n 10)))))
;; Tests if a number is even
;; N → B
(define (isEven n)
(== 0 (% n 2)))
;; Sums the first even KK elements of Fibonacci
;; N N N → N
(define (sum_seq kk k)
(if (== kk 0) 0
(let (a (fib k 0 1))
(if (isEven a) (+ a (sum_seq (- kk 1) (+ k 1)))
(sum_seq kk (+ k 1))))))
(sum_digits (sum_seq 5 0))
;; Run with: cat 1-fibs.typo.scm | typo
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment