Factor solution to project Euler problem 169

diff --git a/extra/project-euler/169/169.factor b/extra/project-euler/169/169.factor
new file mode 100644 (file)
index 0000000..959715e
--- /dev/null
+++ b/extra/project-euler/169/169.factor
@@ -0,0 +1,41 @@
+! Copyright (c) 2007 Samuel Tardieu.
+! See http://factorcode.org/license.txt for BSD license.
+IN: project-euler.169
+USING: combinators kernel math math.functions memoize ;
+
+! http://projecteuler.net/index.php?section=problems&id=169
+
+! DESCRIPTION
+! -----------
+
+! Define f(0)=1 and f(n) to be the number of different ways n can be
+! expressed as a sum of integer powers of 2 using each power no more
+! than twice.
+
+! For example, f(10)=5 since there are five different ways to express 10:
+
+! 1 + 1 + 8
+! 1 + 1 + 4 + 4
+! 1 + 1 + 2 + 2 + 4
+! 2 + 4 + 4
+! 2 + 8
+
+! What is f(1025)?
+
+! SOLUTION
+! --------
+
+MEMO: fn ( n -- x )
+  {
+    { [ dup 2 < ]  [ drop 1 ] }
+    { [ dup odd? ] [ 2/ fn ] }
+    { [ t ]        [ 2/ [ fn ] keep 1- fn + ] }
+  } cond ;
+
+: euler169 ( -- result )
+  10 25 ^ fn ;
+
+! [ euler169 ] 100 ave-time
+! 0 ms run / 0 ms GC ave time - 100 trials
+
+MAIN: euler169

diff --git a/extra/project-euler/project-euler.factor b/extra/project-euler/project-euler.factor
index 9b5c41feedbc2c0bb61414b9a3898ccbab9ff4e0..f256f031389a8ee397638e2badac0ff74ecb8426 100644 (file)
--- a/extra/project-euler/project-euler.factor
+++ b/extra/project-euler/project-euler.factor
@@ -9,6 +9,7 @@ USING: definitions io io.files kernel math math.parser sequences strings
     project-euler.017 project-euler.018 project-euler.019
     project-euler.067
                       project-euler.134
+    project-euler.169
                                         project-euler.175 ;
 IN: project-euler