Project EulerのProblem 57~58をやってみた

Project EulerをJavaで解く

スポンサーリンク

こんにちは。「Javaを復習する初心者」です。Project Eulerという数学の問題サイトがあります。そのサイトのProblem 57から58を解いてみました。

スポンサーリンク

Problem 57

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

2の平方根は無限に続く平方根で展開されることを示すことができる。

  • √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

最初の4つの繰り返しに対してこの展開をすることにより、以下を得る:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

その次の3つの項は99/70、239/169、そして577/408であるが、第8項は1393/985であり、分子の桁数が分母の桁数を超える最初の例である。

最初の1000項で、分子の桁数が分母の桁数より大きいような分数はいくつあるか?

連分数の計算を既存のライブラリでやってみたのですが、第50項でオーバーフローしました。なので、自前のクラスを作りました。

package problem00057;

import java.math.BigInteger;

public class MyFraction {

    private static final BigInteger ZERO = new BigInteger("0");
    private static final BigInteger ONE  = new BigInteger("1");

    /** 分子 */
    private BigInteger numerator;
    /** 分母 */
    private BigInteger denominator;

    MyFraction (BigInteger bigInteger) {
        numerator   = bigInteger;
        denominator = ONE;
    }

    public MyFraction(BigInteger p ,BigInteger q) {
        if (q.equals(ZERO)) {
            throw new RuntimeException("分母を0に指定できません。");
        }
        numerator   = p;
        denominator = q;

        BigInteger gcd = p.gcd(q);
        numerator   = numerator.divide(gcd);
        denominator = denominator.divide(gcd);
    }

    public MyFraction add(MyFraction n) {

        BigInteger p1 = n.getNumerator();
        BigInteger q1 = n.getDenominator();

        BigInteger p2 = numerator;
        BigInteger q2 = denominator;

        MyFraction f = new MyFraction(
                p1.multiply(q2).add(p2.multiply(q1)),
                q1.multiply(q2));

        return f;
    }

    public MyFraction reverse() {
        return new MyFraction(denominator, numerator);
    }

    @Override
    public String toString() {
        if (denominator.equals(new BigInteger("1"))) {
            return numerator.toString();
        }
        return numerator + "/" + denominator;
    }

    /**
     * @return 分子
     */
    public BigInteger getNumerator() {
        return numerator;
    }

    /**
     * @return 分母
     */
    public BigInteger getDenominator() {
        return denominator;
    }

}

上記クラスは分母と分子をフィールドに持つMyFractionクラスです。分数の足し算と逆数を求めるというメソッドのみ実装しています。約分するには最小公倍数を求める必要がありますが、BigIntegerクラスにはgcd()メソッドが用意されていたので、それを使いました。

上記クラスを使って以下のようにプログラミングしました。

package problem00057;

import java.math.BigInteger;

public class Test {

    public static void main(String[] args) {
        new Test().test();
    }

    private void test() {

        int count = 0;
        for (int i = 1; i <= 1000; i++) {
            MyFraction f = calc(i);
            String p = f.getNumerator().toString();
            String q = f.getDenominator().toString();

            if (p.length() > q.length()) {
                count ++;
            }
        }

        System.out.println(count);
    }

    private MyFraction ZERO = new MyFraction(new BigInteger("0"));
    private MyFraction ONE  = new MyFraction(new BigInteger("1"));
    private MyFraction TWO  = new MyFraction(new BigInteger("2"));

    private MyFraction calc(int numberOfIteration) {
        MyFraction r = ZERO;

        for (int i = 0; i < numberOfIteration; i++) {
            r = r.add(TWO);
            r = r.reverse();
        }
        r = r.add(ONE);

        return r;
    }
}

calc()メソッドが第n項の計算をするメソッドです。連分数を最初から計算しなおすやり方なので、もっと工夫できるかもしれません。

Problem 58

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

1から始めて、次のように反時計回りに螺旋を描き、辺の長さ7の螺旋渦巻が形成される。

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

興味深いことは、奇数の平方数が右下の対角線上にあることであるが、より興味深いことは、両方の対角線にある13個の数字のうち8個が素数である; 比率は8/13で約62%である。

渦巻に新しい層を計算し、長さ9の螺旋渦巻が形成される。この操作を続けていくと、対角線上の素数の割合が10%未満になるような最初の辺の長さを求めよ。

渦巻状の点を表すクラスSpiralPointを作りました。

package problem00058;

public class SpiralPoint {

    private int x;
    private int y;
    private int number;

    SpiralPoint() {
        x = 0;
        y = 0;
        number = 1;
    }

    public void moveRight() {
        x += 1;
        number ++;
    }

    public void moveLeft() {
        x -= 1;
        number ++;
    }

    public void moveTop() {
        y += 1;
        number ++;
    }

    public void moveBottom() {
        y -= 1;
        number ++;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getNumber() {
        return number;
    }

    @Override
    public String toString() {
        return "SpiralPoint [x=" + x + ", y=" + y + ", number=" + number + "]";
    }

}

移動した方向でフィールドx、yどちらかを変化させ、フィールドnumberの値が加算されます。フィールドx、yはデバッグで使いました。

このクラスを使い、以下のプログラムを書きました。

    private void test() {

        SpiralPoint spiralPoint = new SpiralPoint();

        int total = 1;
        int countOfPrimes = 0;

        for (int i = 0; i < 10000000; i++) {
            // 右に移動
            spiralPoint.moveRight();

            // 上に移動
            int step = 2 * i + 1;
            for (int j = 0; j < step; j++) {
                spiralPoint.moveTop();
            }
            total ++;
            if (check(spiralPoint.getNumber())) {
                countOfPrimes++;
            }

            // 左に移動
            step ++;
            for (int j = 0; j < step; j++) {
                spiralPoint.moveLeft();
            }
            total ++;
            if (check(spiralPoint.getNumber())) {
                countOfPrimes++;
            }

            // 下に移動
            for (int j = 0; j < step; j++) {
                spiralPoint.moveBottom();
            }
            total ++;
            if (check(spiralPoint.getNumber())) {
                countOfPrimes++;
            }

            // 右に移動
            for (int j = 0; j < step; j++) {
                spiralPoint.moveRight();
            }
            total ++;
            if (check(spiralPoint.getNumber())) {
                countOfPrimes++;
            }

            if ((double)countOfPrimes / total < 0.1) {
                System.out.println(2 * i + 3);
                break;
            }
        }

    }

    private boolean check(int n) {
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

check()メソッドは素数判定です。対角線上の数を素数判定して、素数ならば素数の個数用の変数countOfPrimesを加算します。

「new SpiralPoint()」を宣言した時点で、点は中央の「1」の位置にある想定です。変数totalの初期値が1なのは、「1」が対角線上にあるからです。

for文のループ内の処理は以下のようになってます。

  1. 右に移動(1回)
  2. 上に移動(iに依存する回数)
  3. 左に移動(iに依存する回数)
  4. 下に移動(iに依存する回数)
  5. 右に移動(iに依存する回数)

これで渦巻を一回り大きくする処理になってます。右に1回移動した後は、上、左、下、右に規定回数移動したときにSpiralPointが対角線上の数になります。それぞれでtotalを加算し、素数判定をしています。ループの最後で比率を計算して、題意を満たすなら、辺の長さを出力するということをしています。

スポンサーリンク

おすすめQAサイト

エンジニア特化型Q&Aサイト【teratail(テラテイル)】:
このサイトはプログラミング特化型のQAサイトです。ソースを見やすく整形させた状態で表示させることが出来ます。