extra/project-euler/045/045.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common ;
   4 IN: project-euler.045
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=45
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Triangle, pentagonal, and hexagonal numbers are generated by the following
  12 ! formulae:
  13 !     Triangle     Tn = n(n + 1) / 2    1, 3,  6, 10, 15, ...
  14 !     Pentagonal   Pn = n(3n − 1) / 2   1, 5, 12, 22, 35, ...
  15 !     Hexagonal    Hn = n(2n − 1)       1, 6, 15, 28, 45, ...
  16
  17 ! It can be verified that T285 = P165 = H143 = 40755.
  18
  19 ! Find the next triangle number that is also pentagonal and hexagonal.
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 ! All hexagonal numbers are also triangle numbers, so iterate through hexagonal
  26 ! numbers until you find one that is pentagonal as well.
  27
  28 <PRIVATE
  29
  30 : nth-hexagonal ( n -- m )
  31     dup 2 * 1 - * ;
  32
  33 DEFER: next-solution
  34
  35 : (next-solution) ( n hexagonal -- hexagonal )
  36     dup pentagonal? [ nip ] [ drop next-solution ] if ;
  37
  38 : next-solution ( n -- m )
  39     1 + dup nth-hexagonal (next-solution) ;
  40
  41 PRIVATE>
  42
  43 : euler045 ( -- answer )
  44     143 next-solution ;
  45
  46 ! [ euler045 ] 100 ave-time
  47 ! 12 ms ave run time - 1.71 SD (100 trials)
  48
  49 SOLUTION: euler045