猿の桃

タイトル:
5匹のサルが桃の山を分けている.夜中、最初のサルが先に起きて、桃を等しい5つの山に分けて、1匹増えました.そこで、それは1つ食べて、たくさん持って行きました;2匹目のサルが起きてみると、桃の山が4つしかありません.そこで4つの山を合わせて、等しい5つの山に分けて、また1つ増えました.そこで、それも1つ食べて、たくさん持って行きました;......他の何匹かのサルもこのように分けられています.問:この桃の山は少なくともいくつありますか.
分析:
1匹目から5匹目のサルが分ける各スタックの大きさをそれぞれa,b,c,d,eとする.では、次の関係を満たします.
4*a = 5*b+1  ....(1)//1匹目のサルが去った後に残った桃の数は4*a;2匹目のサルはこれらの桃を5つの山に分け、各山の大きさはb(以下関係式類似)4*b=5*c+1...(2)4*c=5*d+1...(3)4*d=5*e+1...(4)/5匹目のサルが4匹目のサルを歩いた後の分法は5*e+1
中間変数を除去し、aとeだけを保持し、関係式を得る.
4^4*a=5^4*e + 369
つまり256*a=625*e+369...(5)
総桃数はS=5*a+1
要求Sの最小値は、aを求める最小値、すなわちeを求める最小値に相当するので、式(5)で正の整数eを初期値1からループするだけで、aも正の整数を満たす結果がSの最小値となる.
注:(5)式のみを満たすと、上記(1)~(4)式の成立を完全に保証することはできないので、算出したaを(1)~(4)式に順次代入して正しいかどうかを検査することができる(ここのコードでは検証していない).
コード:

public class MonkeyPeaches {

	
	public static void main(String[] args) {
		//4^4.x=5^4.y + 369
		//or: 256x = 625y + 369
		int sum = 625+369;
		while(true){
			int r = sum%256;
			if(r==0){
				int total = sum/256 * 5 + 1;
				System.out.format("total peaches:%d%n",total);
				break;
			}
			sum+=625;				
		}
	}
}

出力:
total peaches:3121