-- ---------------------------------------- -- Haskell programs for Goodstein sequences -- ---------------------------------------- goodstein, goodstein' :: Integer -> [Integer] goodstein = g (\x b -> inflate b x - 1) goodstein' = g (\x b -> inflate b (x - 1)) g :: (Integer -> Integer -> Integer) -> Integer -> [Integer] g f = (++ [0]) . takeWhile (/= 0) . flip (scanl f) [2..] inflate :: Integer -> Integer -> Integer inflate b = sum . map (((b + 1) ^) . (inflate b)) . (h [] 0) where h :: [Integer] -> Integer -> Integer -> [Integer] h es _ 0 = es h es i x = h (replicate (fromInteger d) i ++ es) (i + 1) x' where (x', d) = divMod x b -- --------------------------------------------------------------------- {- goodstein n and goodstein' n are integer sequences starting with n and base b = 2 calculated as follows: - for goodstein: in base b hereditary representation of x replace b by b+1 and subtract 1, - for goodstein': in base b hereditary representation of x - 1 replace b by b+1. Both versions are equivalent concerning Goodstein's theorem. Weisstein's Mathworld and Wikipedia mention the first version, wheras the second version is used, e.g., in the book of Schwichtenberg and Wainer. -} {- function goodstein is used for: A056004, A057650, A059934, A059935, A059936, A215409, A056193, A222117, A059933, A211378. function goodstein' is used for: A222112, A222113. -} -- --------------------------------------------------------------------- -- A056004 Initial step in Goodstein sequences, ... a056004 = (!! 1) . goodstein -- A057650 Second step in Goodstein sequences, ... a057650 = (!! 2) . goodstein -- A059934 Third step in Goodstein sequences, ... a059934 = (!! 3) . goodstein -- A059935 Fourth step in Goodstein sequences, ... a059935 = (!! 4) . goodstein -- A059936 Fifth step in Goodstein sequences, ... a059936 = (!! 5) . goodstein -- A215409 The Goodstein sequence G(3). a215409 n = a215409_list !! (n-1) a215409_list = goodstein 3 -- A056193 Goodstein sequence with a(2)=4: ... a056193 n = a056193_list !! (n-2) a056193_list = goodstein 4 -- A222117 Goodstein sequence starting with 15. a222117 n = a222117_list !! (n-2) a222117_list = goodstein 15 -- A059933 Goodstein sequence with a(2)=16: ... a059933 n = a059933_list !! (n-2) a059933_list = goodstein 16 -- A211378 Goodstein sequence starting with 19. a211378 n = a211378_list !! (n-2) a211378_list = goodstein 19 -- ------------------------------------------------------------- -- A222112 Initial step in Goodstein sequences, ... a222112 = (!! 1) . goodstein' -- A222113 Goodstein sequence starting with 16. a222113 n = a222113_list !! (n-1) a222113_list = goodstein' 16 -- ------------------------------------------------------------- -- Reinhard Zumkeller, Feb 13 2013, reinhard.zumkeller@gmail.com