extra/project-euler/044/044.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math ranges math.order project-euler.common
   4 sequences layouts ;
   5 IN: project-euler.044
   6
   7 ! https://projecteuler.net/problem=44
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2.
  13 ! The first ten pentagonal numbers are:
  14
  15 !     1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
  16
  17 ! It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However,
  18 ! their difference, 70 − 22 = 48, is not pentagonal.
  19
  20 ! Find the pair of pentagonal numbers, Pj and Pk, for which
  21 ! their sum and difference is pentagonal and D = |Pk − Pj| is
  22 ! minimised; what is the value of D?
  23
  24
  25 ! SOLUTION
  26 ! --------
  27
  28 ! Brute force using a cartesian product and an arbitrarily
  29 ! chosen limit.
  30
  31 <PRIVATE
  32
  33 : nth-pentagonal ( n -- seq )
  34     dup 3 * 1 - * 2 /i ; inline
  35
  36 : sum-and-diff? ( m n -- ? )
  37     [ + ] [ - ] 2bi [ pentagonal? ] both? ; inline
  38
  39 : euler044-step ( min m n -- min' )
  40     [ nth-pentagonal ] bi@
  41     2dup sum-and-diff? [ - abs min ] [ 2drop ] if ; inline
  42
  43 PRIVATE>
  44
  45 : euler044 ( -- answer )
  46     most-positive-fixnum
  47     2500 [1..b] [
  48         dup [1..b] [
  49             euler044-step
  50         ] with each
  51     ] each ;
  52
  53 ! [ euler044 ] 10 ave-time
  54 ! 289 ms ave run time - 0.27 SD (10 trials)
  55
  56 SOLUTION: euler044