136
project euler136
天才解法の細かいところを詰めるのが難しかったので。
式変形して、(x,y,z)はd≦xなる正整数(x,d)と1対1対応し、n=x(4d-x)となる。
ここで、n=abかつa+b=0 mod 4かつa≦bならば、x=bと置くことで、ｄ≦xかつn=x(4d-x)となる(x,d)が必ず作れる。
(a,b)が「n=abかつa+b=0 mod 4かつa≦b」を満たすことを(条件※)を満たすということにする。
またx=aと置くことで異なる(x,d)が出来るための必要十分条件は「a≠bかつb＜3a」
したがってnが求めるものであるためには、「『条件※を満たす(a,b)は一意に存在する』(条件A)、かつ、『その(a,b)はa=bまたは3a≦bを満たす』(条件B)」ことが必要十分。mod4で場合分け
・n=1 mod 4のとき
(a,b)=(1,1),(3,3) mod4にしかならない
・n=2 mod 4のとき
(a,b)=(偶,奇)にしかならない
・n=3 mod 4のとき
(a,b)=(1,n)が自明に条件※を満たす。
もしnが4k+1型の素数pを持てば(p,n/p)が、もし4k+3型の(相異なるとは限らない)素数p,qを持てば(pq,n/pq)が(1,n)とは異なる条件※を満たす解となる。よって、条件Aを満たすにはnは奇素数であることが必要。このとき3=3a≦b=nなので条件Bを満たす
・n=4 mod 8のとき
(a,b)=(2,n/2)が自明に条件※を満たす。
もしn/4が(相異なるとは限らない)素数p,qを持てば(2p,n/2p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=4または4pが必要(pは奇素数)。
n=4のとき、a=b=2なので条件Bを満たす。
それ以外のとき、6=3a≦b=n/2なので条件Bを満たす
・n=8 mod 16のとき
(a,b)=(1,0),(2,0)mod 4にしかならない
・n=0 mod 16のとき
(a,b)=(4,n/4)が自明に条件※を満たす。
もしn/16が(相異なるとは限らない)素数p,qを持てば(4p,n/4p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=16または16pが必要(pは奇素数)。
n=16のとき、a=4=4なので条件Bを満たす。
それ以外のとき、12=3a≦b=n/4なので条件Bを満たす
以上から、求めるnは4,16,4p,16p,qに限る(pは奇素数、qはmod4で3の素数)
天才解法の細かいところを詰めるのが難しかったので。
式変形して、(x,y,z)はd≦xなる正整数(x,d)と1対1対応し、n=x(4d-x)となる。
ここで、n=abかつa+b=0 mod 4かつa≦bならば、x=bと置くことで、ｄ≦xかつn=x(4d-x)となる(x,d)が必ず作れる。
(a,b)が「n=abかつa+b=0 mod 4かつa≦b」を満たすことを(条件※)を満たすということにする。
またx=aと置くことで異なる(x,d)が出来るための必要十分条件は「a≠bかつb＜3a」
したがってnが求めるものであるためには、「『条件※を満たす(a,b)は一意に存在する』(条件A)、かつ、『その(a,b)はa=bまたは3a≦bを満たす』(条件B)」ことが必要十分。mod4で場合分け
・n=1 mod 4のとき
(a,b)=(1,1),(3,3) mod4にしかならない
・n=2 mod 4のとき
(a,b)=(偶,奇)にしかならない
・n=3 mod 4のとき
(a,b)=(1,n)が自明に条件※を満たす。
もしnが4k+1型の素数pを持てば(p,n/p)が、もし4k+3型の(相異なるとは限らない)素数p,qを持てば(pq,n/pq)が(1,n)とは異なる条件※を満たす解となる。よって、条件Aを満たすにはnは奇素数であることが必要。このとき3=3a≦b=nなので条件Bを満たす
・n=4 mod 8のとき
(a,b)=(2,n/2)が自明に条件※を満たす。
もしn/4が(相異なるとは限らない)素数p,qを持てば(2p,n/2p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=4または4pが必要(pは奇素数)。
n=4のとき、a=b=2なので条件Bを満たす。
それ以外のとき、6=3a≦b=n/2なので条件Bを満たす
・n=8 mod 16のとき
(a,b)=(1,0),(2,0)mod 4にしかならない
・n=0 mod 16のとき
(a,b)=(4,n/4)が自明に条件※を満たす。
もしn/16が(相異なるとは限らない)素数p,qを持てば(4p,n/4p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=16または16pが必要(pは奇素数)。
n=16のとき、a=4=4なので条件Bを満たす。
それ以外のとき、12=3a≦b=n/4なので条件Bを満たす
以上から、求めるnは4,16,4p,16p,qに限る(pは奇素数、qはmod4で3の素数)
