1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions sequences sequences.lib ;
6 ! http://projecteuler.net/index.php?section=problems&id=148
11 ! We can easily verify that none of the entries in the first seven rows of
12 ! Pascal's triangle are divisible by 7:
22 ! However, if we check the first one hundred rows, we will find that only 2361
23 ! of the 5050 entries are not divisible by 7.
25 ! Find the number of entries which are not divisible by 7 in the first one
26 ! billion (10^9) rows of Pascal's triangle.
34 : sum-1toN ( n -- sum )
38 [ dup 0 > ] [ 7 /mod ] [ ] produce nip ;
40 : (use-digit) ( prev x index -- next )
41 [ [ 1+ * ] [ sum-1toN 7 sum-1toN ] bi ] dip ^ * + ;
43 : (euler148) ( x -- y )
44 >base7 0 [ (use-digit) ] reduce-index ;
48 : euler148 ( -- answer )
51 ! [ euler148 ] 100 ave-time
52 ! 0 ms run time - 100 trials