extra/project-euler/044/044.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions math.ranges project-euler.common sequences ;
   4 IN: project-euler.044
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=44
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten
  12 ! pentagonal numbers are:
  13
  14 !     1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
  15
  16 ! It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference,
  17 ! 70 − 22 = 48, is not pentagonal.
  18
  19 ! Find the pair of pentagonal numbers, Pj and Pk, for which their sum and
  20 ! difference is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?
  21
  22
  23 ! SOLUTION
  24 ! --------
  25
  26 ! Brute force using a cartesian product and an arbitrarily chosen limit.
  27
  28 <PRIVATE
  29
  30 : nth-pentagonal ( n -- seq )
  31     dup 3 * 1- * 2 / ;
  32
  33 : sum-and-diff? ( m n -- ? )
  34     [ + ] [ - ] 2bi [ pentagonal? ] bi@ and ;
  35
  36 PRIVATE>
  37
  38 : euler044 ( -- answer )
  39     2500 [1,b] [ nth-pentagonal ] map dup cartesian-product
  40     [ first2 sum-and-diff? ] filter [ first2 - abs ] map infimum ;
  41
  42 ! [ euler044 ] 10 ave-time
  43 ! 4996 ms ave run time - 87.46 SD (10 trials)
  44
  45 ! TODO: this solution is ugly and not very efficient...find a better algorithm
  46
  47 MAIN: euler044