{- | <https://en.wikipedia.org/wiki/Figurate_number Figurate numbers> are sets of numbers related to polygon shapes. -} module Euler.Util.FigurateNumbers ( -- $setup -- * Triangle triangles , triangleN , isTriangle -- ** Properties -- $triangleProperties -- * Pentagonal , pentagonals , pentagonalN , isPentagonal -- ** Properties -- $pentagonalProperties -- * Hexagonal , hexagonals , hexagonalN , isHexagonal -- ** Properties -- $hexagonalProperties ) where import Euler.Prelude import qualified Euler.Util.Polynomial as Poly import qualified Data.List as List {- $setup >>> import Test.QuickCheck >>> import Data.List.Ordered (member, isSorted) -} -------------------------------------------------------------------------------- -- Triangle -------------------------------------------------------------------------------- {- | All of the triangle numbers, ascending. >>> take 5 triangles [1,3,6,10,15] -} triangles :: Integral a => [a] {- | @'triangleN' n@ is the /n/th triangle number. -} triangleN :: Integral a => a -> a {- | @'isTriangle' x@ denotes whether 'triangles' contains @x@. -} isTriangle :: Integral a => a -> Bool {- $triangleProperties prop> \(Positive n) -> isTriangle n == member n triangles prop> isSorted (take 100 triangles) -} -------------------------------------------------------------------------------- -- Pentagonal -------------------------------------------------------------------------------- {- | All of the pentagonal numbers, ascending. >>> take 10 pentagonals [1,5,12,22,35,51,70,92,117,145] -} pentagonals :: Integral a => [a] {- | @'pentagonalN' n@ is the /n/th pentagonal number. -} pentagonalN :: Integral a => a -> a {- | @'isPentagonal' x@ denotes whether 'pentagonals' contains @x@. -} isPentagonal :: Integral a => a -> Bool {- $pentagonalProperties prop> \(Positive n) -> isPentagonal n == member n pentagonals prop> isSorted (take 100 pentagonals) -} -------------------------------------------------------------------------------- -- Hexagonal -------------------------------------------------------------------------------- {- | All of the hexagonal numbers, ascending. >>> take 5 hexagonals [1,6,15,28,45] -} hexagonals :: Integral a => [a] {- | @'hexagonalN' n@ is the /n/th hexagonal number. -} hexagonalN :: Integral a => a -> a {- | @'isHexagonal' x@ denotes whether 'hexagonals' contains @x@. -} isHexagonal :: Integral a => a -> Bool {- $hexagonalProperties prop> \(Positive n) -> isHexagonal n == member n hexagonals prop> isSorted (take 100 hexagonals) -} -------------------------------------------------------------------------------- -- Lookup by index -------------------------------------------------------------------------------- triangleN n = ( n * ( n + 1) ) `div` 2 pentagonalN n = ( n * (3 * n - 1) ) `div` 2 hexagonalN n = n * (2 * n - 1) -------------------------------------------------------------------------------- -- Iteration -------------------------------------------------------------------------------- triangles = fmap triangleN [1..] pentagonals = fmap snd $ List.iterate (\(n, p) -> (n + 1, p + 3 * (n + 1) - 2)) (1, 1) hexagonals = fmap hexagonalN [1..] -------------------------------------------------------------------------------- -- Testing -------------------------------------------------------------------------------- {- Tests are done by checking whether the solution of some polynomial is integral. -} -- 0 = -2x + n + n^2 isTriangle x = Poly.hasIntRootBetween [ -2 * x, 1, 1 ] 0 x -- 0 = 3n^2 - n - 2x isPentagonal x = Poly.hasIntRootBetween [ -2 * x, -1, 3 ] 0 x -- 0 = -2x -n + 2n^2 isHexagonal x = Poly.hasIntRootBetween [ -x, -1, 2 ] 0 x