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^(q-s)*(2^a-1)/(2^b-1)=2^m*(2n+1)
2^(q-s)*(2^a-1)=2^m*(2n+1)(2^b-1)
thus q-s=m and we have
2^a-1=(2n+1)(2^b-1)
2^a-1=(2n+1)2^b-2n-1
2^a=(2n+1)2^b-2n
now let
n=2^i(2j+1)
then we have
2^a=(2n+1)2^b-2^(i+1)(2j+1)
2^a=2^(i+1)[(2n+1)2^(b-i-1)-2j-1]
2^(a-i-1)=(2n+1)2^(b-i-1)-(2j+1)
now if b-i-1=0 then we have
2^(a-i-1)=2n+1-2j-1
2^(a-i-1)=2(n-j)
2^(a-i-2)=n-j
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
1=(2n+1)2^(b-i-1)-2j-1
2(j+1)=(2n+1)2^(b-i-1)
j+1=(2n+1)2^(b-i-1)
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