1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: fry kernel math math.primes.factors math.vectors sequences sets
7 ! http://projecteuler.net/index.php?section=problems&id=203
12 ! The binomial coefficients nCk can be arranged in triangular form, Pascal's
13 ! triangle, like this:
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.
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.
33 ! Find the sum of the distinct squarefree numbers in the first 51 rows of
42 : iterate ( n initial quot -- results )
43 swapd '[ @ dup ] replicate nip ; inline
45 : (generate) ( seq -- seq )
46 [ 0 prefix ] [ 0 suffix ] bi v+ ;
48 : generate ( n -- seq )
49 1 - { 1 } [ (generate) ] iterate union-all ;
51 : squarefree ( n -- ? )
55 generate [ squarefree ] filter sum ;
62 ! [ euler203 ] 100 ave-time
63 ! 12 ms ave run time - 1.6 SD (100 trials)