java-beginner.com ブログ

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

Project EulerのProblem 26~30をやってみた

投稿日:

最終更新日:2017年01月01日

アイキャッチ

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

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

Problem 26

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

単位分数は1を含む。単位分数で分母が2から10のものは次で与えられる。

  • 1/2 = 0.5
  • 1/3 = 0.(3)
  • 1/4 = 0.25
  • 1/5 = 0.2
  • 1/6 = 0.1(6)
  • 1/7 = 0.(142857)
  • 1/8 = 0.125
  • 1/9 = 0.(1)
  • 1/10 = 0.1

ここで0.1(6)は0.166666…を表し、1桁の循環節を持つ。1/7は6桁の循環節を持つ。

d < 1000の値で1/dが最も長い循環節を持つものを求めよ。

ソース

        int maxRecurringCycle = 0;
        int decimal = 0;
        for (int i = 2; i < 1000; i++) {
            List<Integer> list = new ArrayList<>();
            int target = 1;
            int rem;
            int recurringCycle;
            while (true) {
                target *= 10;
                if (target < i) {
                    list.add(null);
                    continue;
                }

                // 余り
                rem = target % i;
                if (rem == 0) {
                    recurringCycle = 0;
                    break;
                } else if (list.contains(rem)) {
                    recurringCycle = list.size() - list.indexOf(rem) + 1;
                    break;
                }
                list.add(rem);
                target = rem;
            }
            if (maxRecurringCycle < recurringCycle) {
                maxRecurringCycle = recurringCycle;
                decimal = i;
            }
        }
        System.out.println(decimal);

割り算を繰り返し、0以外の同じ余りが出現するかを判定します。余りが0ならば割り切れるということになります。Listに余りを格納して、0以外の余りが出現するかどうかを判定しています。

while文の最初のif文では条件がtrueの場合に、listにnullを格納しています。これは商の部分に0を書いて次の位で余りを求める箇所に対応する部分です。listのサイズで循環節の長さを求めるための処置です。

Problem 27

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

Eulerは以下の2次式を発見した。

$n^2 + n + 41$

0から39の連続した整数nで40個の素数を生成する。しかしながら、nが40では, 40^2 + 40 + 41 = 40(40 + 1) + 41は41で割り切れ、またnが41のときは41^2 + 41 + 41は明らかに41で割り切れる。

$n^2 – 79n + 1601$という式が発見された。nが0から79の連続した値に対して、80個の素数を生成する。係数−79と1601の積は−126479である。

以下の2次式を考える。

$n^2 + an + b$, ここで |a| < 1000かつ|b|<1000であり、

|n|はnの絶対値、つまり、|11| = 11そして|-4| = 4。

n=0から初めて、連続する値で素数を生成する2次式に対して最大長になる場合の、係数aとbの積を求めよ。

ソース

    private int coff_a = 0;
    private int coff_b = 0;

    private void test() {
        int maxLength = 0;
        int a = 0, b = 0;

        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 1000; j++) {
                int length;
                length = getLength(i, j);
                if (maxLength < length) {
                    maxLength = length;
                    a = coff_a;
                    b = coff_b;
                }
                length = getLength(i, -j);
                if (maxLength < length) {
                    maxLength = length;
                    a = coff_a;
                    b = coff_b;
                }
                length = getLength(-i, j);
                if (maxLength < length) {
                    maxLength = length;
                    a = coff_a;
                    b = coff_b;
                }
                length = getLength(-i, -j);
                if (maxLength < length) {
                    maxLength = length;
                    a = coff_a;
                    b = coff_b;
                }
            }
        }
        System.out.println(a * b);
    }

    private int valueFrom(int n) {
        return n * n + coff_a * n + coff_b;
    }

    private boolean checkPrimaryOf(int n) {
        if (n <=1) {
            return false;
        }

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

    private int getLength(int a, int b) {
        coff_a = a;
        coff_b = b;

        int n = 0;
        while (checkPrimaryOf(valueFrom(n))) {
            n ++;
        }
        return n;
    }

2次式の値はvalueFromメソッドで取得しています。係数は引数にしても良かったのですが、今回はフィールドにしました。

係数を与えて、n=0から順番に値が素数かどうかを求めてます。getLengthメソッドがその個所です。素数の判定はcheckPrimaryOfメソッドで行っています。素数は定義から1より大きい自然数なので、最初にif文を追加しています。引数が負の数、0、1の場合は素数ではないので最初に判定してfalseをreturnしています。

Problem 28

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

1から初めて右に進み、時計周りに次のように5つの螺旋を作る。

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

対角線の合計は101である。

同じように作った1001個の螺旋では対角線の合計を求めよ。

ソース

    private final int SIZE = 1001;
    private final int[][] NUMS = new int[SIZE][SIZE];

    private int row, col;
    private int number = 0;

    private void test() {
        // 1
        row = SIZE / 2 + 1 - 1;
        col = SIZE / 2 + 1 - 1;
        setNumber();
        // 2
        col ++;
        setNumber();
        // 3
        row ++;
        setNumber();
        // 4
        col --;
        setNumber();
        // 5
        col --;
        setNumber();
        // 6
        row --;
        setNumber();
        // 7
        row --;
        setNumber();
        // 8
        col ++;
        setNumber();
        // 9
        col ++;
        setNumber();

        while (col < SIZE - 1) {
            moveSpiral();
        }

        int sum = 0;
        for (int i = 0; i < NUMS.length; i++) {
            sum += NUMS[i][i];
            sum += NUMS[i][SIZE - 1 - i];
        }
        sum --;
        System.out.println(sum);
    }

    private void moveSpiral() {
        // 右に進む
        col ++;
        setNumber();

        int steps;

        // 下に進む
        steps = (SIZE / 2 - row) * 2 + 1;
        for (int i = 1; i <= steps; i++) {
            row ++;
            setNumber();
        }

        // 左に進む
        steps ++;
        for (int i = 1; i <= steps; i++) {
            col --;
            setNumber();
        }

        // 上に進む
        for (int i = 1; i <= steps; i++) {
            row --;
            setNumber();
        }

        // 右に進む
        for (int i = 1; i <= steps; i++) {
            col ++;
            setNumber();
        }
    }

    private void setNumber() {
        number ++;
        NUMS[row][col] = number;
    }

1から9までは直に設定し、そのあとはmoveSpiralメソッドで右に1つ進み、下、左、上、右という順に数字を埋める処理をしています。

Problem 29

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

2 ≤ a ≤ 5と2 ≤ b ≤ 5に対して、a^bという組み合わせのを全て考える。

同じ数を除いて、以下のように15個の異なる項を得る。

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100と2 ≤ b ≤ 100の場合はそのような列は異なる項をいくつ持つか。

ソース

        Set<BigInteger> set = new HashSet<>();
        for (int a = 2; a <= 100; a++) {
            BigInteger bigIntegerBase = new BigInteger(String.valueOf(a));
            BigInteger bigInteger = bigIntegerBase;
            for (int b = 2; b <= 100; b++) {
                bigInteger = bigInteger.multiply(bigIntegerBase);
                set.add(bigInteger);
            }
        }
        System.out.println(set.size());

べき乗は念のためBigIntegerを使って計算しました。重複を除く操作はHashSetに値を格納することで実現できます。

Problem 30

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

各桁の4乗の和で表すことができる数は3つのみである。

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

ただし、1 = 1^4は含めない。

それらの数の和は1634 + 8208 + 9474 = 19316である。

各桁の5乗で表すことができる数の全ての和を求めよ。

ソース

    private void test() {
        int bound = getBound();

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            map.put(i, (int)Math.pow(i, 5));
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 2; i < bound; i++) {
            int[] digits = split(i);
            int sum = 0;
            for (int digit : digits) {
                sum += map.get(digit);
            }
            if (i == sum) {
                list.add(i);
            }
        }
        int sum = 0;
        for (int num : list) {
            sum += num;
        }
        System.out.println(sum);
    }

    private int getBound() {
        int a = (int)Math.pow(9, 5);
        int bound = 1;
        while (bound < a) {
            a += a;
            bound *= 10;
        }
        return bound;
    }

    private int[] split(int n) {
        String s = String.valueOf(n);
        int[] digits = new int[s.length()];
        for (int i = 0; i < digits.length; i++) {
            digits[i] = s.charAt(i) - '0';
        }
        return digits;
    }

各桁のべき乗を求めるため、数字から各桁用の配列に格納するメソッドsplitを自作しました。