1 ! Copyright (c) 2008 Eric Mertens.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions sequences project-euler.common
7 ! https://projecteuler.net/problem=148
12 ! We can easily verify that none of the entries in the first
13 ! seven rows of Pascal's triangle are divisible by 7:
23 ! However, if we check the first one hundred rows, we will find
24 ! that only 2361 of the 5050 entries are not divisible by 7.
26 ! Find the number of entries which are not divisible by 7 in the
27 ! first one billion (10^9) rows of Pascal's triangle.
35 : sum-1toN ( n -- sum )
39 [ dup 0 > ] [ 7 /mod ] produce nip ;
41 : (use-digit) ( prev x index -- next )
42 [ [ 1 + * ] [ sum-1toN 7 sum-1toN ] bi ] dip ^ * + ;
44 : (euler148) ( x -- y )
45 >base7 0 [ (use-digit) ] reduce-index ;
49 : euler148 ( -- answer )
52 ! [ euler148 ] 100 ave-time
53 ! 0 ms ave run time - 0.17 SD (100 trials)