読者です 読者をやめる 読者になる 読者になる

Project Euler 34

Problem 34

最大何桁まで求めたら良いのか。

[1] pry(main)> def f(n) n < 1 ? 1 : n*f(n-1) end
=> :f
[2] pry(main)> (1..12).each { |i| puts "i:#{i} #{i*f(9)}" }
i:1 362880
i:2 725760
i:3 1088640
i:4 1451520
i:5 1814400
i:6 2177280
i:7 2540160
i:8 2903040
i:9 3265920
i:10 3628800
i:11 3991680
i:12 4354560
=> 1..12

9! = 362880 だから、1 桁増えても、最大で 362880 しか増えない。8 * 9! = 2903040 で 8 桁にとどかないので、7 まで調べればよい。

using System;
using System.Collections.Generic;
using System.Linq;

class PE034 {
    static int Fact(int n) {
        return n < 1 ? 1 : n * Fact(n-1);
    }
    
    static int Calc1(int p, int[] digits) {
        if (p == digits.Length) {
            int sum = digits.Select(e => Fact(e)).Sum();
            int[] xs = sum.ToString().Select(e => e - '0').OrderBy(e => e).ToArray();
            if (xs.SequenceEqual(digits)) {
                Console.WriteLine("found:{0}", sum);
                return sum;
            }
            return 0;
        }

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

    static int Calc() {
        int ans = 0;
        for (int i = 2; i < 9; i++) {
            ans += Calc1(0, new int[i]);
        }
        return ans;
    }

    static void Main() {
        Console.WriteLine(Calc());
    }
}