Problem 58 - Project Euler

30分プログラム、その336。Problem 58 - Project Euler。

1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

37	36	35	34	33	32	31
38	17	16	15	14	13	30
39	18	5	4	3	12	29
40	19	6	1	2	11	28
41	20	7	8	9	10	27
42	21	22	23	24	25	26
43	44	45	46	47	48	49

面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.
渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

前に解いたProblem28 - みずぴー日記と類似していたので、コードを流用した。

使い方

$ ./problem58
0.10001906214258482
...
13118
0.10001524622655893
13119
0.1000076225322052
13120
0.1
13121
9.999237862967762e-2
13121

ソースコード

import Debug.Trace
diag size = if size == 1 then
                take 1 xs
            else
                take 4 xs
    where
      xs = [a,a+k..]
      k = size - 1
      prev = size - 2
      a = prev * prev + k

squares = map diag [3,5..]

isPrime 1 = False
isPrime 2 = True
isPrime n = and $ map (\x-> n `mod` x /= 0) [2..m]
    where m = ceiling $ sqrt $ fromInteger n


solve (prime,all,n) (x:xs) =
    let all'   = all   + length (trace (show n) x)
        prime' = prime + length (filter isPrime x) 
        ratio  = toF prime' / toF all' in
    if (trace (show ratio) ratio) < 0.1 then
        2*n-1
    else
        solve (prime',all',n+1) xs
    where toF = fromInteger.toInteger

main = print $ solve (0,0,1) squares

参考

• 過去の30分プログラム
• Problem 58 - PukiWiki