Project Euler 30

C# PE

Problem 30

上限値を考える

何桁まで調べればよいのだろうか。9 の 5 乗で調べてみる。

[11] pry(main)> (1..10).each { |i| puts "i:#{i} #{9**5 * i}" }
i:1 59049
i:2 118098
i:3 177147
i:4 236196
i:5 295245
i:6 354294
i:7 413343
i:8 472392
i:9 531441
i:10 590490

9 の 5 乗は 59049 だから、1 桁増えても 59409 しか増えない。6 桁まで調べればいいのか。

プログラム

  • 各桁の 5 乗の和を、桁でソートして一致するかどうか確認しています。
  • SequenceEqual メソッドで、2 つの配列が等しいかどうか調べることができます。
using System;
using System.Collections.Generic;
using System.Linq;

class PE030 {
    static void Calc1(int p, int[] digits, List<int> acc) {
        if (p == digits.Length) {
            int sum = digits.Select(e => (int)Math.Pow(e, 5)).Sum();
            var x = sum.ToString().OrderBy(e => e).Select(e => e - '0').ToArray();
            if (digits.SequenceEqual(x)) {
                acc.Add(sum);
            }
            return;
        }

        int startDigit = p == 0 ? 0 : digits[p-1];
        for (int i = startDigit; i < 10; i++) {
            digits[p] = i;
            Calc1(p+1, digits, acc);
        }
    }

    static int Calc(int n) {
        int[] digits = new int[n];
        var acc = new List<int>();
        Calc1(0, digits, acc);

        foreach (var a in acc) Console.WriteLine(a);
        return acc.Sum();
    }

    static void Main() {
        int ans = 0;
        for (int i = 2; i <= 6; i++) {
            ans += Calc(i);
        }
        Console.WriteLine(ans);
    }
}

参考: