Project Euler - Problem 180

何をやりたい？何もやりたくない

Rational zeros of a function of three variables

n を整数とし，3 つの関数

f_{1, n} (x, y, z) = x^{n + 1} + y^{n + 1} - z^{n + 1}
f_{2, n} (x, y, z) = (xy + yz + zx)(x^{n - 1} + y^{n - 1} - z^{n - 1})
f_{3, n} (x, y, z) = xyz(x^{n - 2} + y^{n - 2} - z^{n - 2})

とその結合

f_n (x, y, z) = f_{1, n} (x, y, z) + f_{2, n} (x, y, z) - f_{3, n} (x, y, z)

について考える．
x, y, z が全て a / b (0 < a < b ≦ k) の形の有理数で，かつ少なくとも 1 つの n に対して f_n (x, y, z) = 0 が成立するとき，(x, y, z) をオーダー k の golden triple と呼ぶことにする．

s(x, y, z) = x + y + z とする．
全てのオーダー 35 の golden triple に対して，区別可能な全ての s(x, y, z) の総和を t = u / v とする．
ただし s(x, y, z) および t は既約分数とする．

u + v を求めよ．

f_n (x, y, z) = … = (x + y + z)(xⁿ + yⁿ - zⁿ) = 0

⇔ xⁿ + yⁿ = zⁿ

オッ

x = a_x / b_x , y = a_y / b_y , z = a_z / b_z とおけば，

(a_xb_yb_z)ⁿ + (b_xa_yb_z)ⁿ = (b_xb_ya_z)ⁿ (n > 0)
(b_xa_ya_z)^-n + (a_xb_ya_z)^-n = (a_xa_yb_z)^-n (n < 0)

余白が狭い感じの定理により n = ±1, ±2 に限定される．n は整数なので負の場合も含むのがいやらしい．

C++ でやると通分時のオーバーフローによって死ぬので python でやった．

k = 35 なので 6 重ループを回していけるかと思ったがだいぶ遅かった (C++ なら問題なく終わる)．

最終的に分母 35 以下の既約分数で 1 より小さいものの集合をつくり，x と y の対称性を利用して範囲を削ることでどうにか 56 秒ほどに収まった．

C++ の速さと python の便利さをいいとこ取りしたいが……

import math
from fractions import Fraction

def GCD(m, n):
    k = 1
    while k != 0:
        k = m % n
        m = n
        n = k
    return m

def PE0180():
    k = 35
    fracs = set()
    for a in range(1, k):
        for b in range(a + 1, k + 1):
            fracs.add(Fraction(a, b))
    l = list(fracs)
    s = set()
    for x in range(len(l)):
        for y in range(x, len(l)):
            for z in range(len(l)):
                ax = l[x].numerator
                bx = l[x].denominator
                ay = l[y].numerator
                by = l[y].denominator
                az = l[z].numerator
                bz = l[z].denominator
                p0 = ax * by * bz
                p1 = bx * ay * bz
                p2 = bx * by * az
                q0 = bx * ay * az
                q1 = ax * by * az
                q2 = ax * ay * bz
                if p0 + p1 == p2 or q0 + q1 == q2 or p0 * p0 + p1 * p1 == p2 * p2 or q0 * q0 + q1 * q1 == q2 * q2:
                    s.add(l[x] + l[y] + l[z])
    ans = sum(s)
    print(ans.denominator + ans.numerator)


PE0180()

絶滅

どうでもいい

Project Euler - Problem 180

Rational zeros of a function of three variables