Project Euler 108 - メモ的な何か

ディオファントス逆数の問題

$1/x + 1/y = 1/n \ (x,y,n \in N)$ について式変形して $(x-n)y = nx$ とする. これは右辺>0 であるので左辺>0で,y>0なので $x>n$ となる. $x\lt=y$ とするとxが最大のとき $y=x$ となり $1/x+1/x = 1/n$ でこのとき $x=2n$ よってnについてxの範囲は $n\lt x\lt=2n$ である. $y=n*x/(x-n)$ が整数になれば良いので以下のようなコードを考えた.

gist.github.com

しかしコレを答えが出るまで実行するとかなりの時間がかかってしまう. もっとうまい方法はないのだろうか?

【2016/10/25　追記】

解答投稿欄を見たらあ上手いコードがあったので改定した. Gistに直接書いたのでコピペだと無理かも.

gist.github.com

なぜ f=2*3*5*7*11*13でf,2f,3f,..,15f を調べればよいのか？これは (x,y)の解が豊富に得られる可能性が高いから. 例えば同じ素数の積の2⁶と3571113では前者は(2⁰,2⁶),...,(2⁶,2⁰)の7通りの分解の仕方しかないが後者は (1,2*3*5*7*11*13),(2,3*5*7*11*13),... と (a,b)とするとそれぞれ{2,3,5,7,11,13} → {a,b}の写像の総数に等しいので2⁶通りある. 証明にはなっていないがなるべく多くの素数で表せたら豊富に解の組み合わせが得られる. f=2*3*5*7*11*13*15*17にするとnsols(f)で既に1000を超えてしまっている.

【注意】なんか上手くtex記法使えなくて崩壊してる.