Problem 49 「素数数列」 †
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.
(i)3つの項はそれぞれ素数である.
(ii)各項は他の項の置換で表される.
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.
それではこの数列の3つの項を連結した12桁の数を求めよ.
解法
まずa1<=a2<=a3<=a4でa1~a4は0~9の数という条件を満たす
[a1,a2,a3,a4]というリストを全探索する。
ある[a1,a2,a3,a4]を並べ替えたものを4桁の整数とみて、これが素数であるか判定し
素数のリストを得る。
その中から素数2つを得て、n=差分*2+小さいほうの素数 が素数のリストにありかつnが一番大きな数であるならそれを答えとする。
計算量は2万回以下。
not_prime(P):-P<2,!.
not_prime(P):-
between(2,P,Div),
(Div^2>P->!,fail;true),
P mod Div=:=0,
!.
is_prime(P):-!,not(not_prime(P)).
seed(0,_,[]):-!.
seed(Keta,P,[P|Xs]):-
Keta1 is Keta-1,
seed(Keta1,P,Xs).
seed(Keta,P,Xs):-
P<9,
!,
P1 is P+1,
seed(Keta,P1,Xs).
seed_w(Perm):-
seed(4,0,Perm),
sum(Perm,A),
A mod 3>0.
sum([],0):-!.
sum([X|Xs],Result):-!,sum(Xs,Re),Result is Re+X.
perm([],0):-!.
perm(Xs,Result):-
select(X,Xs,Xs1),
perm(Xs1,Re),
Result is Re*10+X.
perm_w(Xs,Result):-
perm(Xs,Result),
Result>999,
is_prime(Result).
main49:-seed_w(Seed),
findall(Perm1,perm_w(Seed,Perm1),Ps),
sort(Ps,Perms),
member(N1,Perms),
member(N2,Perms),
N1<N2,
N3 is 2*(N2-N1)+N1,
N2<N3,
member(N3,Perms),
write([N1,N2,N3]),
fail.
最終更新:2014年02月18日 08:44