DouKaku?

1以上200未満の整数nのうち、 exp(pi * sqrt(n))がほとんど整数であるようなnを求めるコードを書いてください。 なお、expは底がeである指数関数 - Wikipedia、 piは円周率、sqrtは平方根です。また「ほとんど整数である」とは 整数からプラスマイナス0.0001の範囲にあることとします。

Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。

37 199148647.999978
58 24591257752.000000
67 147197952743.999999
163 262537412640768744.000000 

この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。

もともとかなり古いライブラリだけど。。。使い勝手は悪くないと思う。

CReal モジュールを使う

このモジュールではデフォルトで小数点以下40桁まで表示。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

module Main (main) where

import CReal

default (CReal)

f :: CReal -> (Int, CReal)
f n = (ceiling n, exp $ pi * sqrt n)

g :: CReal -> Bool
g n = 0.0001 > if 0.5 > n' - n then n' - n else 1 - (n' - n)
  where n' = fromInteger $ ceiling n

main :: IO ()
main = mapM_  (putStrLn . show) $ filter (g . snd) $ map f $ [1..200]

{-
*Main> :main
(37,199148647.9999780465518567665009238753359004336659)
(58,24591257751.9999998222132414695761923552658122276102)
(67,147197952743.9999986624542245068292613125786285081833)
(163,262537412640768743.9999999999992500725971981856888793538563)
-}

20000以下で調べてみたら，

(37,199148647.9999780465518567665009238753359004336659)
(58,24591257751.9999998222132414695761923552658122276102)
(67,147197952743.9999986624542245068292613125786285081833)
(163,262537412640768743.9999999999992500725971981856888793538563)
(232,604729957825300084759.9999921715268564302785946808125512858845)
(652,68925893036109279891085639286943768.0000000001637386442092346075723290625709)
(719,3842614373539548891490294277805829192.9999872495660121875632701836570684449713)
(1169,44555719382988281777368496770130045948309444044.9999608028638684615024311524958053653676)
(1467,18095625621654510801615355531263454706630064771074975.9999999901236936712413276522472419790897)
(2608,4750778730825177725463920948909726618214491718039471366318747406368792.0000003084643221299811801879962000157848)
(4075,1247257156019637304856107520018074552566824585862995272173368815794085495792299621093743.9999936541874689715769690801805608661462)
(5773,46309587632860353087565367053742331250287153098248715578209888177688338779879045292937243508078581367989.9999155688538141662485158867634827239495)
(5868,327451666639079200503292535866541250265248788274691526825971156747731856100971255480468836963064283775072.0000971752541625920841201776565931010652)
(14370,35853082260707987565058966569844138230073788113687426211111838655289387060751425253235617998546754095483027646820100689677619375065141669969772221012766669726610356.0000809961676073067730760452585504610564)
(19183,932865712335864748985892137487224407024879778525651187858506512365813448395651706659915858370562540302669863675912417090372354324023009941419688829317421179304232837551154837099435561184585.9999366484683843100572967742009198686654)

という結果でした．163が題意の意味で一番整数に近いようです．
所要時間は，time ではかって，

2128.54s user 8.40s system 96% cpu 36:49.42 total

でした．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

module Main (main) where

import Data.List
import System.Environment
import System.IO
import CReal

default (CReal)

f :: CReal -> (Int, CReal)
f n = (ceiling n, exp $ pi * sqrt n)

g :: CReal -> Bool
g n = 0.0001 > h n

h :: CReal -> CReal
h n = if 0.5 > n' - n then n' - n else 1 - (n' - n)
  where n' = fromInteger $ ceiling n

main :: IO ()
main = do { args <- getArgs
          ; case args of
              []  -> loop 100 0
              n:_ -> loop (read n) 0
          }
loop n m 
 | n == m = return ()
 | True   = mapM_ (k . f) [(m*100)+1 .. (m+1)*100] >> loop n (m+1)

k :: (Int,CReal) -> IO ()
k n@(i,r) = if g r then hPutStrLn stdout (show n) >> hFlush stdout
	    else putStr (show i ++ "\r") >> hFlush stdout