java-beginner.com ブログ

プログラミングを学習するブログ(Javaをメインに)

Project EulerのProblem 55~56をやってみた

投稿日:

最終更新日:2018年02月12日

アイキャッチ

こんにちは。「Javaを復習する初心者」です。

Project Eulerという数学の問題サイトがあります。そのサイトのProblem 55から56を解いてみました。

Problem 55

自分なりに直訳してみました。

47を反転して加算すると、47 + 74 = 121であり、これは回文数である。

全ての数が回分数をすぐに生成するとは限らない。例えば、

  1. 349 + 943 = 1292
  2. 1292 + 2921 = 4213
  3. 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

自分なりに直訳してみました。

グーゴル(10^100)は大規模な数である: 1の後に0が100個続く。100^100は想像できないくらい大きい: 1の後に0が200個続く。それらの大きさにもかかわらず、その桁の和は1である。

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’の差を加算するということをしています。