extra/project-euler/203/203.factor

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