Determine the smallest positive integer X, such that X is not expressible in the form (2P – 2Q)/(2R – 2S), where each of P, Q, R and S is a positive integer.
below I will show how to determine if a given number X has a (p,q,r,s) solution.
now let x=2^m*(2n+1) with m,n>=0
also let p=q+a and r=s+b like before then we have
thus q-s=m and we have
then we have
now if b-i-1=0 then we have
thus n-j must be a power of 2 (including 1=2^0)
now if instead b-i-1>0 then we have that a-i-1=0 and thus
but n=2^i(2j+1) and thus the right hand side is always bigger than the left hand side and thus there can be no solution here.
So in order to determine if there exists a solution for X first find the highest power of 2 that divides X, divide it out, subtract one, and divide by 2. Call this new number n. Now find the highest power of 2 that divides n and divide it out, subtract one, and divide by 2. call this number j. Now if n-j=2^k for some k>=0 there there is a solution for X.
Posted by Daniel
on 2009-11-08 07:16:04