extra/project-euler/148/148.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions sequences project-euler.common ;
   4 IN: project-euler.148
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=148
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! We can easily verify that none of the entries in the first seven rows of
  12 ! Pascal's triangle are divisible by 7:
  13
  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
  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.
  24
  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.
  27
  28
  29 ! SOLUTION
  30 ! --------
  31
  32 <PRIVATE
  33
  34 : sum-1toN ( n -- sum )
  35     dup 1 + * 2/ ; inline
  36
  37 : >base7 ( x -- y )
  38     [ dup 0 > ] [ 7 /mod ] produce nip ;
  39
  40 : (use-digit) ( prev x index -- next )
  41     [ [ 1 + * ] [ sum-1toN 7 sum-1toN ] bi ] dip ^ * + ;
  42
  43 : (euler148) ( x -- y )
  44     >base7 0 [ (use-digit) ] reduce-index ;
  45
  46 PRIVATE>
  47
  48 : euler148 ( -- answer )
  49     10 9 ^ (euler148) ;
  50
  51 ! [ euler148 ] 100 ave-time
  52 ! 0 ms ave run time - 0.17 SD (100 trials)
  53
  54 SOLUTION: euler148