こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 41から45を解いてみました。
Problem 41
自分なりに直訳してみました。
n桁のpandigitalな素数で最大のものは何か。
ソース
private void test() {
int num = 0;
for (int i = 12; i < 100000000; i++) {
if (checkPandigitalicity(i) && checkPrimaryOf(i)) {
num = i;
}
}
System.out.println(num);
}
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 boolean checkPandigitalicity(int n) {
String s = String.valueOf(n);
int[] counts = new int[s.length() + 1];
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - '0';
if (index > s.length()) {
return false;
}
counts[index] ++;
}
if (counts[0] > 0) {
return false;
}
for (int i = 1; i < counts.length; i++) {
if (counts[i] != 1) {
return false;
}
}
return true;
}checkPrimaryOf()メソッドは素数判定のメソッドです。何度も定義しています。引数の自然数nに対して、2からnの平方根の整数部分までについて、割り切れるかを判定しています。
checkPandigitalicity()メソッドは自然数nがpandigitalかを判定するメソッドです。引数nの各桁に対して、1からnまでの数が登場するかを調べています。nより大きい数値が登場した場合はその場でfalseを返却します。例えば、124という数の場合です。3桁ですので、1から3までが登場してよい数で、3より大きい数字4が登場しているため、falseです。
for文の開始は12にしました。もっと大きくても良いはずですが、深く考えませんでした。for文の繰り返しカウンタiの条件は100000000未満にしました。pandigitalである自然数の桁数は9以下です。なので、今回調べる範囲はint型変数で宣言しておけば十分です。int型で扱える正の整数は2147483647までです。
Problem 42
自分なりに直訳してみました。
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
文字列中の文字とアルファベットの位置を対応させて変換し、それらを加算することで、単語の値を形成する。例えば、SKYの単語の値は19 + 11 + 25 = 55 = t_10である。単語の値が三角数であるとき、三角語と呼ぶ。
2000語の英単語を含む16Kのファイルwords.txtを使うと、三角語の数はいくつあるか？
ソース
private void test() {
// リストに英単語を格納する。
List<String> list = getWords();
// 最大値になりえる値を計算する。
int maxOfLength = 0;
for (String s : list) {
maxOfLength = Math.max(maxOfLength, s.length());
}
// 最大値を超えない三角数を格納する。
Set<Integer> set = new TreeSet<>();
int max = maxOfLength * ('Z' - 'A' + 1);
int n = 1;
int t = 1;
do {
set.add(t);
n ++;
t = n * (n + 1) / 2;
} while (t < max);
// 三角数をカウントし、出力する。
int count = 0;
for (String s : list) {
if (set.contains(getValueOf(s))) {
count ++;
}
}
System.out.println(count);
}
private List<String> getWords() {
List<String> list = new ArrayList<>();
File file = new File("resource/p042_words.txt");
try (BufferedReader br = new BufferedReader(new FileReader(file))) {
String line = null;
while ((line = br.readLine()) != null) {
String[] words = line.split(",");
for (String word : words) {
list.add(word.replace("\"", ""));
}
}
} catch (FileNotFoundException e) {
System.out.println("ファイルが存在しません。");
} catch (IOException e) {
System.out.println("エラーが発生しました。");
}
return list;
}
private int getValueOf(String s) {
int sum = 0;
for (int i = 0; i < s.length(); i++) {
sum += s.charAt(i) - 'A' + 1;
}
return sum;
}テキストファイルに”A”,”ABILITY”,…と英単語が記述されています。これをソースの方に直に貼り付けても良かったのですが、今回はファイル読み込みをしました。読み取り時、前後のダブルクォーテーションはString#replaceで削除し、Listに格納する方式にしました。replaceの代わりにsubstringでも良いと思います。
テキストファイルを見た結果、登場する英単語は大文字で構成されているようなので、大文字で構成されたの単語についての処理のみを考えます。
三角数を毎回計算するのは大変かと思い、先に取り得る三角数をSetオブジェクトに格納する方法にしました。[英単語の長さ最大値] * (‘Z’ – ‘A’ + 1)を求めてしまえば、登場する英単語の値はこの数値を超えることはありません。後はこの数値を超えない三角数を格納します。厳密には取り得る三角数を少しオーバーしている可能性ありますが、その点は気にしないことにしました。
英単語の値はgetValueOfメソッドで求めることにしました。
set.contains(getValueOf(s))が英単語の値が三角数であるかを判定している個所です。これを使ってカウントしています。
Problem 43
自分なりに直訳してみました。
d_1を最初の桁、d_2を2番目の桁というふうにしよう。この方法で、次のことに注意：
- d_2d_3d_4=406 は 2で割り切れる
- d_3d_4d_5=063 は 3で割り切れる
- d_4d_5d_6=635 は 5で割り切れる
- d_5d_6d_7=357 は 7で割り切れる
- d_6d_7d_8=572 は 11で割り切れる
- d_7d_8d_9=728 は 13で割り切れる
- d_8d_9d_10=289 は 17で割り切れる
この性質をもつ0から9のpandigital数の合計を求めよ。
ソース
private void test() {
long sum = 0;
PermutationGenerator<Integer> gen = new PermutationGenerator<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
while (gen.hasMore()) {
List<Integer> list = gen.nextPermutationAsList();
if (!list.get(0).equals(0) && checkDivideProp(list)) {
sum += createLongValueFrom(list);
}
}
System.out.println(sum);
}
private boolean checkDivideProp(List<Integer> list) {
int[] primes = { 2, 3, 5, 7, 11, 13, 17 };
for (int i = 0; i < primes.length; i++) {
int num = list.get(i + 1) * 100 + list.get(i + 2) * 10 + list.get(i + 3);
if (num % primes[i] != 0) {
return false;
}
}
return true;
}
private long createLongValueFrom(List<Integer> list) {
StringBuilder sb = new StringBuilder();
for (Integer integer : list) {
sb.append(String.valueOf(integer));
}
return Long.parseLong(sb.toString());
}試しにfor文で0から9のpandigital数を出力しようとしたら、それだけですごい時間がかかってました。いままでfor文で数値を増やしてpandigital数か判定をするという方法を使ったのですが、今回は方針を変えました。0から9のpandigital数というのは文字の順列で考えると一番左が0でない順列です。なので順列を計算できるライブラリーを使いました。uncommons-maths-1.2.3.jarというjarファイルを使いました。
checkDividePropというメソッドを作りました。左から2番目から3桁ずつ取ってきて順番に素数で割っていくというメソッドです。問題文にある面白い性質というのを持っているかチェックしています。
uncommons-maths-1.2.3.jarでは順列をList<Integer>で取得できるようです。題意を満たす自然数の合計を求めるため、List<Integer>をlong型変数に直すメソッドを作りました。単純にStringBuilderで順番に連結して、最後にLong#parseLongメソッドで変換しています。
Problem 44
自分なりに直訳してみました。
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
P_4 + P_7 = 22 + 70 = 92 = P_8である。しかしながら、その差70 − 22 = 48は五角数ではない。
その差と和が五角数であるペアP_jとP_kを見つけよ。D = |P_k − P_j|の最小は何か？
ソース
private void test() {
// 五角数をある程度格納する。
final int size = 9999;
int[] nums = new int[size];
for (int i = 1; i <= size; i++) {
nums[i - 1] = i * (3 * i - 1) / 2;
}
// 題意の差を求める。
for (int i = 0; i < size; i++) {
for (int j = 0; j < i; j++) {
if (Arrays.binarySearch(nums, nums[i] + nums[j]) > 0
&& Arrays.binarySearch(nums, nums[i] - nums[j]) > 0) {
System.out.println(nums[i] - nums[j]);
}
}
}
}五角数をある程度、配列に格納して検索する方法にしました。第9999項まで調べて1個だけ題意を満たすものが見つかったので、それをプロジェクトオイラーの問題ページで入力したら正解でした。ということは第9999項より先は五角数の差がもっと大きいのか、五角数にならないかなのですが、それは証明が分かりませんでした。正解してしまったのでこれ以上は追及しないことにします。
五角数を配列に格納して、和と差が配列に含まれているかを調べてのですが、Arrays#binarySearchメソッドを使いました。配列に五角数が順番に並んでいるため、検索用のメソッドを自作するとより速くなるかもしれません。
配列に代わりにListを使っても良いのですが、ListにはラッパークラスであるInteger型を格納することになります。なので配列より処理時間が長くかかると思います。
Problem 45
自分なりに直訳してみました。
| 三角数 | T_n=n(n+1)/2 | 1, 3, 6, 10, 15, … |
| 五角数 | P_n=n(3n−1)/2 | 1, 5, 12, 22, 35, … |
| 六角数 | H_n=n(2n−1) | 1, 6, 15, 28, 45, … |
T_285 = P_165 = H_143 = 40755であることが分かる。
次の三角数で五角数と六角数と同じものを求めよ。
ソース
Map<Integer, BigInteger> pentagonalMap = new HashMap<>();
Map<Integer, BigInteger> hexagonalMap = new HashMap<>();
private void test() {
BigInteger triangle;
for (int i = 286; i < 100000; i++) {
triangle = getTriangleOf(i);
if (pentagonalOf(triangle) && hexagonalOf(triangle)) {
System.out.println(triangle);
break;
}
}
}
private boolean pentagonalOf(BigInteger triangle) {
int i = 1;
BigInteger pentagonal;
do {
pentagonal = getPentagonalOf(i++);
if (pentagonal.equals(triangle)) {
return true;
}
} while (pentagonal.compareTo(triangle) < 0);
return false;
}
private boolean hexagonalOf(BigInteger triangle) {
int i = 1;
BigInteger hexagonal;
do {
hexagonal = getHexagonalOf(i++);
if (hexagonal.equals(triangle)) {
return true;
}
} while (hexagonal.compareTo(triangle) < 0);
return false;
}
private BigInteger getTriangleOf(int n) {
return new BigInteger(String.valueOf(n))
.multiply(new BigInteger(String.valueOf(n + 1)))
.divide(new BigInteger("2"));
}
private BigInteger getPentagonalOf(int n) {
BigInteger bigInteger = pentagonalMap.get(n);
if (bigInteger == null) {
bigInteger = new BigInteger(String.valueOf(n))
.multiply(new BigInteger(String.valueOf(3 * n - 1)))
.divide(new BigInteger("2"));
pentagonalMap.put(n, bigInteger);
}
return bigInteger;
}
private BigInteger getHexagonalOf(int n) {
BigInteger bigInteger = hexagonalMap.get(n);
if (bigInteger == null) {
bigInteger = new BigInteger(String.valueOf(n))
.multiply(new BigInteger(String.valueOf(2 * n - 1)));
hexagonalMap.put(n, bigInteger);
}
return bigInteger;
}最初はint型やlong型で計算していたのですが、様子がおかしいと思って調べたらオーバーフローしていました。なので、BigIntegerを使うことにしました。
考え方は単純で、for文で順番に三角数を算出し、五角数、六角数と同じになるか調べてます。そのときの五角数、六角数は三角数を超えない数まで調べれば良いです。ですが、毎回第1項から計算しなおすのは時間がかかると判断して、五角数と六角数はMapを使って計算結果を残す方針にしました。Mapに格納されてない項はBigIntegerのメソッドを使って計算するというやり方です。この方法で五角数、六角数を取得しと三角数と比較しています。
最初のfor文はiの開始が286です。これは問題文で第285項より後の三角数を求めるという指定があるからです。getTriangleOfで三角数の第n項を取得しています。if文で使っているpentagonalOfメソッド、hexagonalOfメソッドは引数に指定された三角数と等しくなるような五角数、六角数が存在するかを判定するメソッドです。それぞれで上記のアイデアを使って第1項から順番に等しいかを調べています。