1405 Heritage

問題概要

1 - (1/k1 + 1/k2 + … + 1/kn)を正で最小にするような数列、
k1,k2……を求めよ。


ただしkiは自然数でありki<ki+1を満たすものとする。
n≦18とする。

解法

ぐぐったら、tsukunoさんのブログがヒットした。
ki=k1*k2*…*ki-1 +1とすると何故か通るらしい。理由は謎らしい。

ソースコード

import java.math.*;
import java.util.*;

class Main {
	public static void main(String[] args) {
		new Main().new pku1405().run();
	}
	class pku1405{
		void run(){
			int n;
			BigInteger ans[]=new BigInteger[20];
			Scanner sc=new Scanner(System.in);
			
			ans[1]=BigInteger.valueOf(2); ans[2]=BigInteger.valueOf(3);
			for(int i=3;i<=18;i++){
				ans[i]=BigInteger.ONE;
				for(int j=1;j<i;j++)ans[i]=ans[i].multiply(ans[j]);
				ans[i]=ans[i].add(BigInteger.ONE);
			}
			
			n=sc.nextInt();
			for(int i=1;i<=n;i++)System.out.println(ans[i]);
		}
	}
}