All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Positive Integer ≠ (2P – 2Q)/(2R – 2S) (Posted on 2009-11-07) Difficulty: 4 of 5
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.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
solution conditions | Comment 2 of 3 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information