Project Euler (13〜50)

50問目まで解きました。数学を使って工夫すると速く解けたりするようなものについてだけ自分の解答を書きます。

Problem 15

20x20のグリッドの左上から右下までの最短経路数を求めよ

これは2項係数、
\binom{40}{20}
の値を計算すれば良いです。2項係数の値はパスカルの三角形の値を上から下へ計算していく方法が効率的です。つまり、以下の漸化式を使います。
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}
コードは次のようになります。

a = [1,1]
2.upto 40 do |n|
    n.downto 0 do |k|
        a[k] = (k == 0 || k == n) ? 1 :
            a[k-1] + a[k]
    end
end
puts a[20]

a[k]の計算にa[k-1]を使いますから、内側のループはdowntoです。

Problem 21,23

Problem 21: 10000以下の全ての友愛数の和を求めよ
Problem 23: 2つの過剰数の和で表されない数の和を求めよ

友愛数も過剰数も約数の和を用いて判定します。約数の和はNの因数分解
N = p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n}
の時
(1+p_1+p_1^2+\cdots+p_1^{m_1})(1+p_2+\cdots+p_2^{m_2})\cdots(1+p_n+\cdots+p_n^{m_n}) \\= \frac{1-p_1^{m_1+1}}{1-p_1}\frac{1-p_2^{m_2+1}}{1-p_2} \quad \cdots\quad \frac{1-p_n^{m_n+1}}{1-p_n}
で求まるわけなので、Problem 12と同様にして高速に求める事ができます。
例えばProblem 21の場合は以下の様な感じになります。

N = 30000
d = Array.new(N+1,1)
exp = Array.new(N+1)
2.upto(N) do |n|
    if d[n] == 1 then
        exp.fill(0)
        n.step(N, n) do |k|
            exp[k] = exp[k/n] + 1
            d[k] *= (1-n**(exp[k]+1))/(1-n)
        end
    end
end
sum = 0
2.upto(10000) do |n|
    a = d[n]-n
    b = d[a]-a
    sum += n if a != b && b == n
end
puts sum

実行時間は0.36秒程度です。

Problem 26

1/dの循環節の長さが最大となるようなd (< 1000)を求めよ

循環節の長さをkとすると
\frac{10^k}{d} - \frac{1}{d}
が整数となるわけなので
10^k \equiv 1 \quad (\mathrm{mod} d)
が成立するようなkを調べれば良いです。

Problem 27

n^2 + an + b (n=0,1,2,...)が生成する素数列が最長となるようなa,b(|a|<1000,|b|<1000)を求めよ。

n=0で素数である必要があるからbは素数
n=1で素数である必要があるから1+a+bは素数。従ってaは奇数で、さらに1+a+b > 0。などの必要条件を調べて探索範囲を絞れば良いです。

N = 20000
sieve = []
primes = []
2.upto(N) do |n|
    next if sieve[n]
    primes.unshift(n) if n < 1000
    (2*n).step(N,n) {|k| sieve[k] = true}
end
max_len = 0
max = 0
primes.each do |b|
    break if b <= max_len
    (-b+2).step(999,2) do |a|
        next if sieve[1+a+b]
        n = 0
        while true
            p = n*n + a*n + b
            break if p < 0 || (p < N && sieve[p])
            raise "N is too small" if p >= N
            n+=1
        end
        max, max_len = a*b, n if n > max_len
    end
end
puts max

実行時間は0.40秒。

Problem 28

下の様にして螺旋状に並べた1001x1001の数字列の、対角にある数の和を求めよ。

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

群数列として考えて、一辺の長さが2*n+1の時の和の一般項を求めると
1 + \sum_{k=1}^n(16k^2+4k+4)
なのでつまり
\frac{16}{3}n^3+10n^2+\frac{26}{3}n+1
にn=500を代入して終わり。

Problem 31

1ペンスから1ポンド硬貨までを使って、2ポンドを支払う方法は何通りか?

以前書いたようにして漸化式を立てる。

Problem 39

p = a + b + cかつa^2+b^2=c^2
である自然数a,b,cを考える。最も解の数が多くなるpの値を求めよ。

これはProblem 9と同じく2元2次不定方程式の問題なので探索は不要。cを消去して因数分解すると
(p-a)(p-b)=\frac{p^2}{2}
となるので、まずpは偶数であることが必要。ここでa <= bとすればp-a >= p-bだから
\sqrt{p^2/2} \le p-a < p
の範囲でp^2/2の約数となるp-aの個数を数えれば良いです。

max = 0
max_p = 0
4.step(1000,2) do |p|
    count = 0
    Math.sqrt(p*p/2).ceil.upto(p) do |k|
        count += 1 if (p*p/2)%k == 0
    end
    max, max_p = count, p if max < count
end
puts max_p

実行時間は0.08秒。

Problem 40

0.123456789101112131415161718192021...
のような無限小数の少数第n位をdnとして
d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000
を求めよ

n桁の数を第n群として群数列的にやればいいです。

r = 1
[1,10,100,1000,10000,100000,1000000].each do |n|
    k, s = 0, 0
    while n > 9*10**k*(k+1)
        n -= 9*10**k*(k+1)
        k += 1
    end
    d = (n-1) % (k+1)
    n = 10**k + (n-1)/(k + 1)
    r *= (n / 10**(k-d))%10
end
puts r

実行時間は0.01秒。

Problem 42,44,45

これらの問題では三角数T(n),五角数P(n),六角数H(n)を扱いますが、これらは以下のようにして値からインデックスを簡単に求める事ができます。これに基づいて解答を作成すれば上手くできます。
T(n) = \frac{n(n+1)}{2} \rightarrow n = \lfloor \sqrt{2T(n)} \rfloor
P(n) = \frac{n(3n-1)}{2} \rightarrow n =\lceil\sqrt{\frac{2}{3}P(n)}\rceil
H(n) = n(2n-1) \rightarrow n = \left\lceil \sqrt{\frac{H(n)}{2}} \right\rceil

Problem 47

連続する4整数で、全てが4つの素因数からなる数であるものを求めよ

「素因数の数」を使いますが、これもProblem 21,23と同様に反復により求められます。

N = 1000000
sieve = Array.new(N+1, 0)
2.upto(N) do |n|
    if sieve[n] == 0 then
        n.step(N, n) do |k|
            sieve[k] += 1
        end
    end
    if n > 4 && (n-3..n).all? {|k| sieve[k] == 4}
        puts n-3
        exit
    end
end

実行時間は2.75秒。