{"id":1177,"date":"2010-03-16T17:47:06","date_gmt":"2010-03-16T23:47:06","guid":{"rendered":"http:\/\/bililite.nfshost.com\/blog\/?p=1177"},"modified":"2010-03-16T17:47:06","modified_gmt":"2010-03-16T23:47:06","slug":"learning-scheme-euler-problem-2","status":"publish","type":"post","link":"https:\/\/bililite.com\/blog\/2010\/03\/16\/learning-scheme-euler-problem-2\/","title":{"rendered":"Learning Scheme, Euler problem 2"},"content":{"rendered":"<p>The second project Euler problem is:\r\n\r\n<blockquote>Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:\r\n\r\n1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\r\n\r\nFind the sum of all the even-valued terms in the sequence which do not exceed four million.<\/blockquote>\r\n\r\n<\/p><!--more-->\r\n<p>Brute force Fibonacci generator:<\/p>\r\n<pre><code class=\"language-lisp\">(define fibo\r\n  (lambda (n)\r\n    (cond\r\n      ((= n 1)\r\n       1)\r\n      ((= n 2)\r\n       2)\r\n      (else (+ (fibo (- n 1)) (fibo (- n 2)))))))<\/code><\/pre>\r\n<p>But that takes exponential time, and the problem requires generating all of the numbers anyway, so we can use something like:<\/p>\r\n<pre><code class=\"language-lisp\">(define fibo-sum\r\n  (lambda (a b lim)\r\n    (let* ((c (+ a b)))\r\n      (cond\r\n        ((< lim c) 0)\r\n        (else (+ c (fibo-sum b c lim)))))))<\/code><\/pre>\r\n<p> to get the sum of all the fibonacci numbers less than lim (use <code class=\"language-lisp\">(fibo-sum 1 2 4000000)<\/code>). I could add a test for even numbers to solve the problem, but more elegantly we notice that the pattern of the fibonacci numbers has to be odd-odd-even-odd-odd-even, so we have:<\/p>\r\n<pre><code class=\"language-lisp\">(define euler2\r\n  (lambda (a b lim)\r\n    (let* ((c (+ a b))\r\n           (d (+ b c))\r\n           (e (+ c d)))\r\n      (cond\r\n        ((< lim e) 0)\r\n        (else (+ e (euler2 d e lim)))))))\r\n(euler2 1 0 4000000)<\/code><\/pre>\r\n<p>We start the fibonacci sequence with 1 0 so that the 2 is part of our sum.  And we get the correct answer, 4613732, imperceptibly fast.<\/p>\r\n<p>One bug that took me forever to find was a mistyped line:<\/p>\r\n<pre><code class=\"language-lisp\">(let* ((c (+ a b))\r\n  (d (+ b c))\r\n   (e (+ d e)))\r\n<\/code><\/pre>\r\n<p>Where <code>e<\/code> was defined in terms of <code>d<\/code> and <code>e<\/code>, so it used the global value of <code>e<\/code>. If it hadn't been defined, it would have given me an error immediately, but unfortunately, DrScheme has it pre-defined as <code class=\"language-lisp\">#i2.718281828459045<\/code> so my code went happily along giving me the wrong answers.<\/p>\r\n\r\n","protected":false},"excerpt":{"rendered":"The second project Euler problem is: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence [&hellip;]","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[],"_links":{"self":[{"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/posts\/1177"}],"collection":[{"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/comments?post=1177"}],"version-history":[{"count":4,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/posts\/1177\/revisions"}],"predecessor-version":[{"id":1182,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/posts\/1177\/revisions\/1182"}],"wp:attachment":[{"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/media?parent=1177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/categories?post=1177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bililite.com\/blog\/wp-json\/wp\/v2\/tags?post=1177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}