こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 55から56を解いてみました。
Problem 55
自分なりに直訳してみました。
全ての数が回分数をすぐに生成するとは限らない。例えば、
- 349 + 943 = 1292
- 1292 + 2921 = 4213
- 4213 + 3124 = 7337
つまり、349は3回の繰り返しで回文数になる。
証明はまだないが、196のようないくつかの数は回分数にならないと考えれている。反転して加算する過程を経ても回分数にならない数をLychrel数と呼ぶ。この問題の目的のため、Lychrelでないと証明されてない数はLychrel数であると仮定する。さらに、10000未満の数については、(i) 50回未満の操作で回文数になる (ii) 回文数に到達しない、のどちらかを一方が成り立つと仮定する。実際、10677は50回以上の繰り返しが必要な最初の数である: 4668731596684224866951378664 (53回の繰り返しで、28桁)。
驚くべきことに、回文数自身がLychrel数であるものが存在する; 最初の例は4994。
10000未満のLychrel数の個数はいくらか。
注: Lychrel数の理論的な性質を強調するために2007年4月24日に文面が修正された
ソース
private void test() {
int count = 0;
for (int i = 10; i < 10000; i++) {
BigInteger bigInteger = new BigInteger(Integer.toString(i));
boolean isPalindrome = false;
for (int j = 1; j < 50; j++) {
bigInteger = iterate(bigInteger);
if (checkPalindromelyOf(bigInteger)) {
isPalindrome = true;
break;
}
}
if (!isPalindrome) {
count ++;
}
}
System.out.println(count);
}
private BigInteger iterate(BigInteger bigInteger) {
return bigInteger.add(new BigInteger(new StringBuilder(bigInteger.toString()).reverse().toString()));
}
private boolean checkPalindromelyOf(BigInteger bigInteger) {
return bigInteger.equals(new BigInteger(new StringBuilder(bigInteger.toString()).reverse().toString()));
}今回の問題は、自然数の桁を反転させて元の数に加算するという話です。この操作を繰り返して回文数になるかという問題ですが、おそらく前提条件は2桁以上の自然数です。反転させるという文言に2桁以上の自然数を考えるという暗黙の了解があるようです。
加算の繰り返しは50回未満と仮定しています。なので繰り返し文は1から50未満にしました。
加算した結果が何桁になるか詳しく考慮はしませんでしたが、念のためBigIntegerを使いました。反転するという操作はStringBuilderクラスのreverse()メソッドを使いました。
iterateというメソッドを作りました。引数に対して反転して加算した結果を返却しています。
checkPalindromelyOfというメソッドを作りました。引数が回分数か判定するメソッドです。
全体の処理の流れはfor文で10から10000未満までの自然数それぞれ対して、反転して加算を繰り返して判定をするという流れです。49回まで繰り返して回文にならなければカウントを+1しています。
Problem 56
自分なりに直訳してみました。
a^bという形式の自然数を考える。ここでa, b < 100である。桁の和の最大は何か？
ソース
private void test() {
int max = 0;
for (int a = 1; a < 100; a++) {
BigInteger base = new BigInteger(Integer.toString(a));
BigInteger pow = null;
for (int b = 1; b < 100; b++) {
pow = base.pow(b);
int digitalSum = calDigitalSumOf(pow);
if (max < digitalSum) {
max = digitalSum;
}
}
}
System.out.println(max);
}
private int calDigitalSumOf(BigInteger bigInteger) {
String s = bigInteger.toString();
int sum = 0;
for (int i = 0; i < s.length(); i++) {
sum += s.charAt(i) - '0';
}
return sum;
}大きな数を扱うので、BigIntegerクラスを使うことにしました。また、このクラスにはpowメソッドが用意されているので、べき乗が簡単に計算できます。
各桁の数値の和を計算するために、calDigitalSumOf()メソッドを定義しました。引数のBigIntegerに対して、各桁の和を計算するメソッドです。方法は単純にBigInteger型をString型に変換して、String#charAt()メソッドで各桁の文字を取得して加算しています。ただし、取得した文字は文字コードなので’0’の差を加算するということをしています。