extra/project-euler/169/169.factor

   1 ! Copyright (c) 2007 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 IN: project-euler.169
   4 USING: combinators kernel math math.functions memoize ;
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=169
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Define f(0)=1 and f(n) to be the number of different ways n can be
  12 ! expressed as a sum of integer powers of 2 using each power no more
  13 ! than twice.
  14
  15 ! For example, f(10)=5 since there are five different ways to express 10:
  16
  17 ! 1 + 1 + 8
  18 ! 1 + 1 + 4 + 4
  19 ! 1 + 1 + 2 + 2 + 4
  20 ! 2 + 4 + 4
  21 ! 2 + 8
  22
  23 ! What is f(1025)?
  24
  25 ! SOLUTION
  26 ! --------
  27
  28 MEMO: fn ( n -- x )
  29   {
  30     { [ dup 2 < ]  [ drop 1 ] }
  31     { [ dup odd? ] [ 2/ fn ] }
  32     { [ t ]        [ 2/ [ fn ] keep 1- fn + ] }
  33   } cond ;
  34
  35 : euler169 ( -- result )
  36   10 25 ^ fn ;
  37
  38 ! [ euler169 ] 100 ave-time
  39 ! 0 ms run / 0 ms GC ave time - 100 trials
  40
  41 MAIN: euler169