Knuth's power tree: Difference between revisions
Haskell solution
m (→{{header|Phix}}: replaced with gmp version) |
(Haskell solution) |
||
Line 453:
191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191]
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347</pre>
=={{header|Haskell}}==
{{works with|GHC|8.8.1}}
{{libheader|containers|0.6.2.1}}
<lang haskell>{-# LANGUAGE ScopedTypeVariables #-}
module Rosetta.PowerTree
( Natural
, powerTree
, power
) where
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.List (foldl')
import Numeric.Natural (Natural)
type M = Map Natural [Natural]
levels :: [M]
levels = iterate step $ Map.singleton 1 [1]
step :: M -> M
step m = foldl' f m $ Map.keys m
where
f :: M -> Natural -> M
f m' n = foldl' g m' ns
where
ns :: [Natural]
ns = m' Map.! n
g :: M -> Natural -> M
g m'' k =
let l = n + k
in Map.insertWith (flip const) l (ns ++ [l]) m''
powerTree :: Natural -> [Natural]
powerTree n
| n <= 0 = []
| otherwise = go levels
where
go :: [M] -> [Natural]
go [] = error "impossible branch"
go (m : ms) = case Map.lookup n m of
Nothing -> go ms
Just xs -> xs
power :: forall a. Num a => a -> Natural -> a
power _ 0 = 1
power a n = go a 1 (Map.singleton 1 a) $ tail $ powerTree n
where
go :: a -> Natural -> Map Natural a -> [Natural] -> a
go b _ _ [] = b
go b k m (l : ls) =
let b' = b * m Map.! (l - k)
m' = Map.insert l b' m
in go b' l m' ls</lang>
{{out}}
{{libheader|numbers|3000.2.0.2}}
(The <tt>CReal</tt> type from package <tt>numbers</tt> is used to get the ''exact'' result for the last example.)
<pre>powerTree 0 = [], power 2 0 = 1
powerTree 1 = [1], power 2 1 = 2
powerTree 2 = [1,2], power 2 2 = 4
powerTree 3 = [1,2,3], power 2 3 = 8
powerTree 4 = [1,2,4], power 2 4 = 16
powerTree 5 = [1,2,3,5], power 2 5 = 32
powerTree 6 = [1,2,3,6], power 2 6 = 64
powerTree 7 = [1,2,3,5,7], power 2 7 = 128
powerTree 8 = [1,2,4,8], power 2 8 = 256
powerTree 9 = [1,2,3,6,9], power 2 9 = 512
powerTree 10 = [1,2,3,5,10], power 2 10 = 1024
powerTree 11 = [1,2,3,6,9,11], power 2 11 = 2048
powerTree 12 = [1,2,3,6,12], power 2 12 = 4096
powerTree 13 = [1,2,3,5,10,13], power 2 13 = 8192
powerTree 14 = [1,2,3,5,7,14], power 2 14 = 16384
powerTree 15 = [1,2,3,6,9,15], power 2 15 = 32768
powerTree 16 = [1,2,4,8,16], power 2 16 = 65536
powerTree 17 = [1,2,4,8,16,17], power 2 17 = 131072
powerTree 191 = [1,2,4,8,16,17,25,29,58,87,174,191], power 3 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
powerTree 81 = [1,2,3,6,9,18,27,54,81], power 1.1 81 = 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811
</pre>
=={{header|J}}==
| |||