HaHaHa!(old)

2006-08-19

ShowS型

数値を16進表記の文字列に変換したい - 趣味的にっきより.

ShowS のありがたみってあまり解りやすくないんですよねぇ.

http://www.sampou.org/haskell/tutorial-j/stdclasses.html#sect8.3

すこし解説があります.蓄積引数を使うことで再帰途中の(++)による効率の

低下を防いでいるということです.

ha-tan さんのコードを難読化してみました.(^^;)

module Main (main) where

import Numeric (showHex)
import System.Environment (getArgs)

pprHexS :: Integral a => a -> ShowS
pprHexS n = ("[ 0x"++) . showHex n . (" ]"++)

main :: IO ()
main = getArgs >>= putStr . flip id "\n" . foldr (.) id . map (pprHexS . read)

実行例は

% runhaskell pprHex.hs 123 1234 12345
[ 0x7b ][ 0x4d2 ][ 0x3039 ]

ディリクレの算術級数

ディリクレの算術級数定理 - HaHaHa!(old) - haskellにいただいたコメントで示された応用問題

a と d が互いに素な正の整数とする。

a から始まり d ずつ増える等差数列に含まれる、自然数n以下の素数pの

個数をA(a,d,n)で表す。

たとえば、n=10の場合

A(1,4,10)={5}の要素数=1

A(3,4,10)={3,7}の要素数=2

さて、

A(1,4,n)、A(3,4,n)

の大小を比較をn=30000まで比較し

(i)30000以下のnについては、A(1,4,n) ≦ A(3,4,n) が成り立つ

または

(ii)A(1,4,n) > A(3,4,n) なるnがある場合には、最小のnを求める

を示してください。

ふむ.これは素数列を4で割った余りでフィルターすればいいのしらん.

というわけで,めちゃ素朴に.

fst3 (x,_,_) = x

type Table = ([Int],[Int],[Int])

primes = concatMap fst3 $ iterate sieve ([2],[2],[2..])

sieve :: Table -> Table
sieve (ps,q:qs,ss)
 = let (xs,ys) = span (q*q >) ss
   in (xs,qs++xs,filter ((/=0) . (`mod` q)) ys)

lem :: Int -> Int -> Int -> Int
lem a d n = length $ filter (\ m -> mod m d == a) $ takeWhile (n >=) primes

l14 = lem 1 4
l34 = lem 3 4

rng   = filter (\ m -> elem (mod m 4) [1,3]) [2..30000]
check = map fst $ filter snd $ zip rng $ zipWith (>) (map l14 rng) (map l34 rng)

で check を評価すると

Main> check
[26861]

というわけで, (ii) の場合になって, n = 26861 .かな.

タナカタナカ2006/08/19 18:57正解!。返答して頂いてありがとうございます。
速答している様子が目に見えるようです。
ついでに、A(1,4,n)、A(3,4,n)の増加の様子も出しておいても良かったかな…
実は、A(1,4,n)、A(3,4,n)はn→∞では無限回大小が変わるそうです。
Littlewoodという数学者が証明したそうです。(1914年)
証明される前は、チェビシェフChebyshevが、A(1,4,n)<=A(3,4,n)と予想していたとか。
最小数が26861なのは、1957年に分かったとか。
LL-Ringの"キミならどう書く"には数学に近すぎ(て好みの分かれ)る問題カナ?
http://homepage2.nifty.com/hiranouchi/asir/pari300.html
参考文献:「数論Ⅰ」加藤 他 著 岩波書店 p.272