Problem27

30分プログラム、その298。Problem27 via Project Euler。

オイラーは以下の二次式を考案している:

n^2 + n + 41

この式は, nを0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40のとき402 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる. また, n = 41のときは412 + 41 + 41であり明らかに41で割り切れる.

計算機を用いて, 二次式n^2 - 79n + 1601という式が発見できた. これはn = 0 から 79 の連続する整数で素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値):
n^2 +an+b
n=0から初めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.

とりあえずは、素直に全部生成して素数かどうかをチェックするようにしてみた。予想通り終わらない。
素数生成は、id:mzp:20080330:primeで書いたコードを使った。

使い方

$ erlc problem27.erl
$ erl -noshell -s problem27 main 999
....

ソースコード

-module(problem27).
-compile([export_all]).

poly(A,B,N) ->
    N*N + A*N + B.

times(N,F) ->
    M = F(N),
    case lists:member(M,prime_srv:get(M)) of
	true ->
	    times(N+1,F);
	_ ->
	    N
    end.
    
times(F) ->
    times(0,F).

main([X]) ->
    prime_srv:start(),
    From = - list_to_integer(atom_to_list(X)),
    To = list_to_integer(atom_to_list(X)),
    As = lists:seq(From,To),
    Bs = lists:seq(From,To),
    Xs = lists:flatmap(fun(A)->
			       lists:map(fun (B)-> io:format("[~p, ~p]~n",[A,B]),
						   {times(fun(N)->poly(A,B,N) end),A,B}
					 end,Bs) end,As),
    io:format("~p~n",[lists:max(Xs)]),
    init:stop().

参考

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