remove math.blas.syntax and merge parsing words into math.blas.vectors/matrices
[factor/jcg.git] / extra / project-euler / 203 / 203.factor
blobf2b5a2e212e10ba6791686ab74d4a4dda141b98b
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 ;
4 IN: project-euler.203
6 ! http://projecteuler.net/index.php?section=problems&id=203
8 ! DESCRIPTION
9 ! -----------
11 ! The binomial coefficients nCk can be arranged in triangular form, Pascal's
12 ! triangle, like this:
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 !               .........
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.
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.
32 ! Find the sum of the distinct squarefree numbers in the first 51 rows of
33 ! Pascal's triangle.
36 ! SOLUTION
37 ! --------
39 <PRIVATE
41 : iterate ( n initial quot -- results )
42     swapd '[ @ dup ] replicate nip ; inline
44 : (generate) ( seq -- seq )
45     [ 0 prefix ] [ 0 suffix ] bi [ + ] 2map ;
47 : generate ( n -- seq )
48     1- { 1 } [ (generate) ] iterate concat prune ;
50 : squarefree ( n -- ? )
51     factors all-unique? ;
53 : solve ( n -- n )
54     generate [ squarefree ] filter sum ;
56 PRIVATE>
58 : euler203 ( -- n )
59     51 solve ;
61 ! [ euler203 ] 100 ave-time
62 ! 12 ms ave run time - 1.6 SD (100 trials)
64 MAIN: euler203