extra/project-euler/203/203.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: fry kernel math math.primes.factors sequences sets project-euler.common ;
   4 IN: project-euler.203
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=203
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! The binomial coefficients nCk can be arranged in triangular form, Pascal's
  12 ! triangle, like this:
  13
  14 !                   1
  15 !                 1   1
  16 !               1   2   1
  17 !             1   3   3   1
  18 !           1   4   6   4   1
  19 !         1   5  10  10   5   1
  20 !       1   6  15  20  15   6   1
  21 !     1   7  21  35  35  21   7   1
  22 !               .........
  23
  24 ! It can be seen that the first eight rows of Pascal's triangle contain twelve
  25 ! distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.
  26
  27 ! A positive integer n is called squarefree if no square of a prime divides n.
  28 ! Of the twelve distinct numbers in the first eight rows of Pascal's triangle,
  29 ! all except 4 and 20 are squarefree. The sum of the distinct squarefree numbers
  30 ! in the first eight rows is 105.
  31
  32 ! Find the sum of the distinct squarefree numbers in the first 51 rows of
  33 ! Pascal's triangle.
  34
  35
  36 ! SOLUTION
  37 ! --------
  38
  39 <PRIVATE
  40
  41 : iterate ( n initial quot -- results )
  42     swapd '[ @ dup ] replicate nip ; inline
  43
  44 : (generate) ( seq -- seq )
  45     [ 0 prefix ] [ 0 suffix ] bi [ + ] 2map ;
  46
  47 : generate ( n -- seq )
  48     1 - { 1 } [ (generate) ] iterate concat prune ;
  49
  50 : squarefree ( n -- ? )
  51     factors all-unique? ;
  52
  53 : solve ( n -- n )
  54     generate [ squarefree ] filter sum ;
  55
  56 PRIVATE>
  57
  58 : euler203 ( -- n )
  59     51 solve ;
  60
  61 ! [ euler203 ] 100 ave-time
  62 ! 12 ms ave run time - 1.6 SD (100 trials)
  63
  64 SOLUTION: euler203