こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 46から50を解いてみました。
Problem 46
自分なりに直訳してみました。
- 9 = 7 + 2×1^2
- 15 = 7 + 2×2^2
- 21 = 3 + 2×3^2
- 25 = 7 + 2×3^2
- 27 = 19 + 2×2^2
- 33 = 31 + 2×1^2
この予想は誤りであった。
素数と平方の2倍の和で表すことができない最小の奇数の合成数は何か？
ソース
private Set<Integer> setOfPrimes = new HashSet<>();
private void test() {
int requiredNumber = 0;
for (int i = 2; i < 10000; i++) {
if (checkPrimalyOf(i)) {
setOfPrimes.add(i);
} else {
boolean satisfiesGoldbachConjecture = false;
Iterator<Integer> iterator = setOfPrimes.iterator();
while (iterator.hasNext()) {
int prime = iterator.next();
double sqrt = Math.sqrt((i - prime) / 2);
if (sqrt - (int) sqrt == 0.0) {
satisfiesGoldbachConjecture = true;
break;
}
}
if (!satisfiesGoldbachConjecture) {
requiredNumber = i;
break;
}
}
}
System.out.println(requiredNumber);
}
private boolean checkPrimalyOf(int n) {
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}まず、素数かどうかを判定する必要があったため、checkPrimalyOf()というメソッドを定義しました。素数判定は以前から用いている方法です。2から順に引数の平方根の整数部分までの数で割り切れるかを判定しています。
奇数の合成数nに対して、Goldbachの性質を満たすかを判定するアイデアは単純で、nより小さい素数それぞれに対応する平方根があるかを判定してます。方程式を解くように計算している個所が「double sqrt = Math.sqrt((i – prime) / 2)」の部分です。後はsqrtの小数部分が0になっているかを判定します。小数部分を「sqrt – (int) sqrt」という式で計算していますが、ほかに良い方法があるかもしれません。
Goldbachの性質を満たすかをfor文で2から順番に調べる方法で、10000未満まで調べてますが、この数は適当です。素数を繰り返し使うため、フィールドにMapを定義して、計算した素数はそこに格納しています。このMapはnより小さい素数を取得するために使っています。
Problem 47
自分なりに直訳してみました。
- 14 = 2 × 7
- 15 = 3 × 5
3つの異なる素数因子を持つ3つの連続した最初の数は次である。
- 644 = 2^2 × 7 × 23
- 645 = 3 × 5 × 43
- 646 = 2 × 17 × 19
4つの異なる素数因子を持つ4つの連続した数を求めよ。その最初の数は何か？
ソース
private final int numOffactors = 4;
private void test() {
List<Integer> factors1 = new ArrayList<>();
List<Integer> factors2 = new ArrayList<>();
List<Integer> factors3 = new ArrayList<>();
List<Integer> factors4 = new ArrayList<>();
factors2 = getPrimeFactors(3);
factors3 = getPrimeFactors(4);
factors4 = getPrimeFactors(5);
int numOfRequired = 0;
for (int i = 6; i < 1000000; i++) {
factors1 = factors2;
factors2 = factors3;
factors3 = factors4;
factors4 = getPrimeFactors(i);
// 素因数
if (factors1.size() == numOffactors
&& factors2.size() == numOffactors
&& factors3.size() == numOffactors
&& factors4.size() == numOffactors) {
numOfRequired = i - numOffactors + 1;
break;
}
}
System.out.println(numOfRequired);
}
private List<Integer> getPrimeFactors(int n) {
List<Integer> list = new ArrayList<>();
for (int i = 2; i < n; i++) {
if (n % i == 0 && checkPrimaryOf(i)) {
list.add(i);
}
}
return list;
}
private final Set<Integer> setOfPrimes = new HashSet<>();
private boolean checkPrimaryOf(int n) {
if (setOfPrimes.contains(n)) {
return true;
}
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
setOfPrimes.add(n);
return true;
}getPrimeFactors()というメソッドを定義しました。このメソッドは素数因子のリストを返却するメソッドです。Listを4つ用意して、連続する4つの自然数それぞれを引数にしたgetPrimeFactors()の結果を格納します。それぞれリストのサイズが4になれば題意を満たす自然数が求まるということです。
for文で1000000未満までの連続する4つの自然数について計算しました。この値は適当です。実行しながら決めた値です。
因数が素数であるか判定する必要がありますが、フィールドにHashSetを用意して素数を格納するやり方にしました。checkPrimaryOf()メソッドが素数か判定するメソッドです。そのすぐ上に定義してあるsetOfPrimesが、計算した素数を格納しておくHashSetです。Javaではフィールドの宣言をこのような位置にすることが可能です。
Problem 48
自分なりに直訳してみました。
級数1^1 + 2^2 + 3^3 + … + 1000^1000の最後の10桁を求めよ。
ソース
private void test() {
BigInteger bigInteger = new BigInteger("0");
for (int i = 1; i <= 1000; i++) {
bigInteger = bigInteger.add(calPow(i, i));
}
String s = bigInteger.toString();
System.out.println(s.substring(s.length() - 10));
}
private BigInteger calPow(int base, int exp) {
BigInteger baseBigInteger = new BigInteger(String.valueOf(base));
BigInteger rst = baseBigInteger;
for (int i = 1; i < exp; i++) {
rst = rst.multiply(baseBigInteger);
}
return rst;
}べき乗を求めるメソッドを作りました。今回の問題は数が大きくなるため、BigIntegerを使いました。計算した自然数の最後の10桁はString型を取得して、String#subStringメソッドで求めました。引数が一つの方のメソッドはその位置から最後までの部分文字列が取得できます。s.length() – 10でちょうど最後10桁が取得できました。このメソッドの引数は「開始インデックス(この値を含む)。」であることがポイントです。
Problem 49
自分なりに直訳してみました。
- 3つの項それぞれが素数である。
- 4桁の数値がもうひとつ別の項の置換である。
1、2、または3桁の素数で作られた数列で、このような性質を持つものは存在しないが、4桁の増加列はひとつ別のものが存在する。
この列のその3つの項を連結した12桁の数は何か？
ソース
private void test() {
List<Integer> list = new ArrayList<>();
for (int i = 1000; i < 10000; i++) {
if (checkPrimaryOf(i)) {
list.add(i);
}
}
for (int i = 0; i < list.size(); i++) {
int term1 = list.get(i);
for (int j = i + 1; j < list.size(); j++) {
int term2 = list.get(j);
int term3 = term2 + (term2 - term1);
String construction = getConstruction(term1);
if (list.contains(term3)
&& construction.equals(getConstruction(term2))
&& construction.equals(getConstruction(term3))) {
System.out.printf("%d%d%d", term1, term2, term3);
System.out.println();
}
}
}
}
private boolean checkPrimaryOf(int n) {
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
private String getConstruction(int n) {
int[] digits = new int[4];
digits[0] = n / 1000;
digits[1] = n / 100 % 10;
digits[2] = n / 10 % 10;
digits[3] = n % 10;
Arrays.sort(digits);
return Arrays.toString(digits);
}最初に4桁の素数すべてをArrayListに格納しました。最初の要素から順に差が等しくなる3項を求める方針です。第1項と第2項から第3項を求め、ArrayListに含まれるか調べるという方法にしました。containsメソッドで引数がリストに含まれるか判定できます。
getConstructionというメソッドを定義しました。これは4桁の自然数に対して、構成要素となる文字列を返却するメソッドです。digitsという配列を定義して、各桁の数字を格納しています。Arrays#sortを使って、この配列を昇順に並び替えてます。Arrays#toStringメソッドで[要素1,要素2…]という文字列が返却されます。これを使って、3項が互いに文字列置換であるか判定します。
Problem 45
自分なりに直訳してみました。
41 = 2 + 3 + 5 + 7 + 11 + 13
100未満の素数ではこの和が最も長い。
1000未満の素数で最も長いのは21項で953である。
100万未満の素数で、連続する素数の和が最も長くかけるのは何か？
ソース
private static final int UPPER_LIMIT_OF_NUM = 1000000;
private void test() {
List<Integer> list = new ArrayList<>();
for (int i = 2; i < UPPER_LIMIT_OF_NUM; i++) {
if (checkPrimaryOf(i)) {
list.add(i);
}
}
int[] primes = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
primes[i] = list.get(i);
}
int maxLength = 0;
long primeNumRequired = 0;
for (int i = 0 ; i < primes.length; i++) {
int sum = primes[i];
int length = 1;
for (int j = i + 1; j < primes.length; j++) {
sum += primes[j];
length ++;
if (sum >= UPPER_LIMIT_OF_NUM) {
j = primes.length;
} else {
if (maxLength < length && Arrays.binarySearch(primes, sum) > 0) {
maxLength = length;
primeNumRequired = sum;
}
}
}
}
System.out.println(primeNumRequired);
}
private boolean checkPrimaryOf(long n) {
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}100万未満の素数を最初に計算しました。この中の素数を合計して、再び素数になっているかを判定します。ただし、今回は計算回数が多いような気がしたので、int型配列に格納しています。配列の場合、Arrays#binarySearchが使えます。ArrayListでcontainsメソッドを使うよりも速くなると思って、今回は配列を使うようにしました。ただし、実際に測定はしていません。
for文でi番目の素数に対して、i+1番目から後の素数を順番に加算して素数であるかを判定しています。合計が素数になっている場合、その素数が題意を満たす素数の候補になります。ただし、100万未満であることが条件であるため、100万を超えた時点で繰り返しカウンタjに関する繰り返し処理を終えるようにしています。これで余計な処理を省いています。合計が素数であるかを判定する前に「maxLength < length」を判定してます。加算する素数の個数が少ないならば答えの候補にならないからです。