extra/project-euler/045/045.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common ;
   4 IN: project-euler.045
   5
   6 ! https://projecteuler.net/problem=45
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Triangle, pentagonal, and hexagonal numbers are generated by
  12 ! the following 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
  20 ! hexagonal.
  21
  22
  23 ! SOLUTION
  24 ! --------
  25
  26 ! All hexagonal numbers are also triangle numbers, so iterate
  27 ! through hexagonal numbers until you find one that is
  28 ! pentagonal as well.
  29
  30 <PRIVATE
  31
  32 : nth-hexagonal ( n -- m )
  33     dup 2 * 1 - * ;
  34
  35 DEFER: next-solution
  36
  37 : (next-solution) ( n hexagonal -- hexagonal )
  38     dup pentagonal? [ nip ] [ drop next-solution ] if ;
  39
  40 : next-solution ( n -- m )
  41     1 + dup nth-hexagonal (next-solution) ;
  42
  43 PRIVATE>
  44
  45 : euler045 ( -- answer )
  46     143 next-solution ;
  47
  48 ! [ euler045 ] 100 ave-time
  49 ! 12 ms ave run time - 1.71 SD (100 trials)
  50
  51 SOLUTION: euler045