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 than
  13 ! 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(10^25)?
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 MEMO: fn ( n -- x )
  30     {
  31         { [ dup 2 < ]  [ drop 1 ] }
  32         { [ dup odd? ] [ 2/ fn ] }
  33         [ 2/ [ fn ] [ 1- fn ] bi + ]
  34     } cond ;
  35
  36 : euler169 ( -- result )
  37     10 25 ^ fn ;
  38
  39 ! [ euler169 ] 100 ave-time
  40 ! 0 ms ave run time - 0.2 SD (100 trials)
  41
  42 MAIN: euler169