Determine the smallest positive integer X, such that X is not expressible in the form (2^{P} – 2^{Q})/(2^{R} – 2^{S}), 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
2^(qs)*(2^a1)/(2^b1)=2^m*(2n+1)
2^(qs)*(2^a1)=2^m*(2n+1)(2^b1)
thus qs=m and we have
2^a1=(2n+1)(2^b1)
2^a1=(2n+1)2^b2n1
2^a=(2n+1)2^b2n
now let
n=2^i(2j+1)
then we have
2^a=(2n+1)2^b2^(i+1)(2j+1)
2^a=2^(i+1)[(2n+1)2^(bi1)2j1]
2^(ai1)=(2n+1)2^(bi1)(2j+1)
now if bi1=0 then we have
2^(ai1)=2n+12j1
2^(ai1)=2(nj)
2^(ai2)=nj
thus nj must be a power of 2 (including 1=2^0)
now if instead bi1>0 then we have that ai1=0 and thus
1=(2n+1)2^(bi1)2j1
2(j+1)=(2n+1)2^(bi1)
j+1=(2n+1)2^(bi1)
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 nj=2^k for some k>=0 there there is a solution for X.

Posted by Daniel
on 20091108 07:16:04 