extra/project-euler/169/169.factor

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