2^i * 3^j * 5^k なる整数 in Haskell DouKaku?

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

軽く候補の絞込み(2と3と5の倍数しか回答は無いので)を入れてみました。

list max b n
    | (b^n) > max   =   []
    | otherwise = n : list max b (n+1)

scan n = [(n,i,j,k)|i<-list n 2 0,j<-list n 3 0,k<-list n 5 0,n == (2^i*3^j*5^k)]

result = take 100 $ concatMap (scan) $ filter (check) [1..]

check n
    | n == 1            =   True
    | (n `mod` 2) == 0  =   True
    | (n `mod` 3) == 0  =   True
    | (n `mod` 5) == 0  =   True
    | otherwise         =   False

main=do
    mapM (\x-> putStrLn $ format x) result
    where
        format (n,i,j,k) = concat [show n," = ",fmt 2 i," * ",fmt 3 j," * ",fmt 5 k]
        fmt b n = show b ++ "^" ++ show n

ハミング数ですね。
anarchy golf の Hamming Numbers問題
http://golf.shinh.org/p.rb?Hamming+Numbers
のときに投稿した golf用の富豪コードです。

30のx乗 ≡ 0 (mod x) となる x がハミング数に
なることを使っています。（30 は 2,3,5 の最小公倍数）

富豪だから、け、計算量なんて気にしてないんだからね！

main = do
  n <- readLn
  mapM_ print $ take n [x| x <- [1..], mod (30^x) x == 0]

{- anarchy golf に投稿したコードはこちら

main=readLn>>=mapM print.(`take`[x|x<-[1..],mod(30^x)x<1])

-}

Haskellらしく素直に無限リストで :)

main :: IO ()
main = print $ take 100 hamming

hamming :: [Integer]
hamming = 1 : foldr1 (#) (zipWith map (map (*) [2,3,5]) (repeat hamming))

(#) :: Ord a => [a] -> [a] -> [a]
xxs@(x:xs) # yys@(y:ys) | x < y     = x : xs  # yys
                        | y < x     = y : xxs # ys
                        | otherwise = x : xs  # ys

もりっとArrowで

module Main where

import Control.Arrow

f = Left >>> f' 2 >>> f' 3 >>> f' 5 >>> const False ||| const True                                                           
  where f' n = g n ||| Right

g n = loop ((snd &&& fst >>> app) &&& (snd >>> g'))
  where g' f m | n > m = Right ()
               | True  = case m `divMod` n of (x,0) -> f x; _ -> Left m

main = runKleisli func [1..]
  where func = arr (filter f) >>> arr (take 100) >>> Kleisli (mapM_ print)

有名なエラトステネスのふるいを変形して。Haskellはあんまりやったことがないから勝手が分かりませんが。

sieve (x:xs) | divide235 x = x:sieve xs
             | otherwise = sieve [a | a <- xs, a `mod` x /= 0]
    where divide235 x = x `mod` 2 == 0 || x `mod` 3 == 0 || x `mod` 5 == 0

take 100 $ [1..6] ++ sieve [7..]

オーダーは考えていませんが。

1 2	import List main = print $ take 100 $ sort $ [2^i3^j5^k\|lm<-[0..99],i<-[0..lm],j<-[0..lm-i],let k = lm-i-j]

DouKaku?

2^i * 3^j * 5^k なる整数

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq