PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 157 / ディオファントス方程式 1/a + 1/b = p/10^n を解く

ディオファントス方程式 1/a + 1/b = p/10^n (a, b, p, n は正の整数で a ≤ b) について考える。
n = 1 のとき,この方程式は次の20個の解を持つ。

1/1+1/1=20/10
1/1+1/2=15/10
1/1+1/5=12/10
1/1+1/10=11/10
1/2+1/2=10/10
1/2+1/5=7/10
1/2+1/10=6/10
1/3+1/6=5/10
1/3+1/15=4/10
1/4+1/4=5/10
1/4+1/20=3/10
1/5+1/5=4/10
1/5+1/10=3/10
1/6+1/30=2/10
1/10+1/10=2/10
1/11+1/110=1/10
1/12+1/60=1/10
1/14+1/35=1/10
1/15+1/30=1/10
1/20+1/20=1/10

1 ≤ n ≤ 9 について, この方程式の解はいくつ存在するか?

Problem 157 - Project Euler


与式を p について解きます。

 p=10^n \times \dfrac{a+b}{ab}

a, b の最大公約数を g として

 a=gA,\, b=gB,\, (A,\, B)=1

とおいて p の式に代入すると次のようになります。

 p=10^n \times \dfrac{A+B}{gAB}

A+B と AB は互いに素なので,AB は 10^n の約数です。

 (A,\, B)=(2^i,\, 5^j),\, (1,\, 2^i 5^j)

について調べれば十分。p の個数は g の個数と同じで,これは
10^n(A+B)/(AB) の約数の個数として求められます。