c21coterie @ ウィキ
c21coterie @ ウィキ

「プロジェクトオイラー問９２」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問９２ - (2014/03/04 (火) 19:37:29) の編集履歴(バックアップ)


Problem 92 「桁の2乗による連鎖」 †

各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す.

例えば

　　44 → 32 → 13 → 10 → 1 → 1
　　85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である. どちらも1か89で無限ループに陥っている.
驚くことに, どの数から始めても最終的に1か89に到達する.
では, 10,000,000より小さい数で89に到達する数はいくつあるか.

解法
まずは素朴な方法。
999万9999を変換しても567にしかなりません１回変換すると１０００万までのどんな数も567以下になります。
少し多めに見積もってまずは600までで1に到達したものをメモ化して置きます。
1に到達しなかったものが８９に到達するのですから、600-（1に到達したものの数）が600までの８９に到達する数です。
601～999万9999までは一回変換した数字が1に到達する数にならなければそれは８９に到達します。
しかしこの方法は遅いです。
もっと早い方法があります。 



next_calc1([],0):-!.
next_calc1([X|Xs],Result):-
	!,
	next_calc1(Xs,Re),
	Result is Re+(X-48)^2.

next_calc(N,Result):-
	!,
	number_codes(N,L),
 	next_calc1(L,Result).


searchN(1):-!,fail.
searchN(89):-!.
searchN(N):-
	next_calc(N,N1),
	searchN(N1).
list1(N):-
	between(1,600,N),
	not(searchN(N)).
search(10000000,_,Ans):-
	!,
	write(Ans).
search(N,List1,Ans):-

	next_calc(N,NN),
	not(member(NN,List1)),
	!,
	N1 is N+1,
	Ans1 is Ans+1,
	search(N1,List1,Ans1).
search(N,List1,Ans):-
	!,
	N1 is N+1,
	search(N1,List1,Ans).

main92:-
	findall(N,list1(N),List1),
	length(List1,Len),
	Ans is 600-Len,
	search(601,List1,Ans).