正整数のゲーデル数化？ in Haskell DouKaku?

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数
goedel を定義してください．

ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk]
をなすとし，dk が 1 の位，d1 が 10^(k-1) の位です．また，pk は k番目の素数です．

goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108

see: ゲーデル数

やっぱり一度文字列化するの一番効率的で簡単みたいです。

import Data.Char

primes = sieve [2..] 
  where 
  sieve (x:xs) = x : sieve [y| y<-xs, y `mod` x /= 0]

goedel x = product $ zipWith (^) primes (map digitToInt (show x))

{-
*Main> goedel 9
512
*Main> goedel 81
768
*Main> goedel 230
108
-}

ちょっとparallel list comprehension使ってみたかったんので...。 zipWith (^)より可読性いいかもしれないですね。

{-# OPTIONS_GHC -fglasgow-exts #-}
import Data.Char

primes = sieve [2..] 
  where 
  sieve (x:xs) = x : sieve [y| y<-xs, y `mod` x /= 0]

goedel x = product [p^(digitToInt c) | p <- primes | c <- show x]

{-
*Main> goedel 9
512
*Main> goedel 81
768
*Main> goedel 230
108
-}

素数生成の部分はHaskellでは有名なコードなのでコピペです。

import List

goedel n = product $ zipWith (\p d->p^d) primes (digits n)


-- copy & paste
primes = 2:(sieve [3, 5 ..])
  where sieve (p:xs) = p: (sieve [ x | x <- xs, x `mod` p /= 0])


digits num  = reverse $ unfoldr f num
  where f a = let (c,d) = divMod a 10
              in  if (c,d) == (0,0) then Nothing
                                    else Just (d,c)

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq