「プロジェクトオイラー問２３」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問２３」(2014/02/13 (木) 20:10:06) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2023
*Problem 23 「非過剰数和」 †
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.



解法
最初に1～28123までのリストを作り。
小さいほうから完全数のリストを作っていって、そこまでの完全数２数の和と同じになったものを削除したリストを得ることを繰り返せばまあ遅いけど答えは出ます。
この問題すこし検索してみましたが、２数の和を全部試す以外の答えを出してる人はいませんでした。
きちんと検索したり正答者掲示板をよく探したらかしこい人がいるかもしれません。


 yakusu(_,1,1):-!.
 yakusu(N,P,P):-N mod P=:=0.
 yakusu(N,P,N1):-N>P*P,N mod P=:=0,!,N1 is N // P. 
 
 sum([],0):-!.
 sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.
 
 yakusu_list(N,Y1):-
 	between(1,N,Y),
 	Y2 is Y*Y,
 	(Y2>N->!,fail;true),
 	yakusu(N,Y,Y1).
 is_kazyo(N):-
 	!,
 	findall(Y,yakusu_list(N,Y),Ys),
 	sum(Ys,Sum),
 	N<Sum. 
 
 list_dell(Xs,[],Xs):-!.
 list_dell([],_,[]):-!.
 list_dell([X|Xs],[Y|Ys],[X|Result]):-
 	X<Y,
 	!,
 	list_dell(Xs,[Y|Ys],Result).
 list_dell([X|Xs],[X|Ys],Result):-
 	!,
 	list_dell(Xs,Ys,Result).
 list_dell(Xs,[_|Ys],Result):-
 	!,
 	list_dell(Xs,Ys,Result).
 
 addList([],_,[]):-!.
 addList([X|_],Add,[]):-
	Y is X+Add,
 	Y>28123,
 	!.
 addList([X|Xs],Add,[Y|Result]):-
 	Y is X+Add,
 	addList(Xs,Add,Result).
  
 search(28123,Seed,_):-
 	!,
 	sum(Seed,Ans),
 	write(Ans).
 search(N,Seed,Kazyo):-
 	is_kazyo(N),
 	!,
 	write(a),
 	append(Kazyo,[N],Kazyo1),
 	addList(Kazyo1,N,Kazyo2),
 	write(b),
 	length(Seed,Len),
 	nl,
 	write(Len),
 	nl,
 	list_dell(Seed,Kazyo2,Seed1),
 	N1 is N+1,
 	search(N1,Seed1,Kazyo1).
 search(N,Seed,Kazyo):-
 	!,
 	N1 is N+1,
 	search(N1,Seed,Kazyo).
 
 
 seed(N):-
 	between(1,28123,N).
 
 main23:-findall(N,seed(N),Seed),
 	search(12,Seed,[]).