※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


Problem 43 「部分列被整除性」 †

数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.

d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

d2d3d4=406 は 2 で割り切れる
d3d4d5=063 は 3 で割り切れる
d4d5d6=635 は 5 で割り切れる
d5d6d7=357 は 7 で割り切れる
d6d7d8=572 は 11 で割り切れる
d7d8d9=728 は 13 で割り切れる
d8d9d10=289 は 17 で割り切れる
このような性質をもつ0から9のパンデジタル数の総和を求めよ.



解法
左の桁から条件を満たす組み合わせを全探索していくだけで十分間に合います。



search(_,_,Num,[],Num):-!.
search([Da,Db],Nums,Num,[Div|Divs],Result):-
	!,
	select(Dc,Nums,Nums1),
	Num1 is Num*10+Dc,
	C is Da*100+Db*10+Dc,
	C mod Div=:=0,
	search([Db,Dc],Nums1,Num1,Divs,Result).

sum([],0):-!.
sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.



search(Result):-
	Nums=[0,1,2,3,4,5,6,7,8,9],
	select(D1,Nums,Nums1),
	D1>0,
	select(D2,Nums1,Nums2),
	select(D3,Nums2,Nums3),
 	Num is D1*100+D2*10+D3,
        search([D2,D3],Nums3,Num,[2,3,5,7,11,13,17],Result).

main43:-
	findall(A,search(A),Ans),
	write(Ans),
	sum(Ans,Ans1),
	write(Ans1).