紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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

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