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.

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年02月18日 08:44