Register to reply 
Finding pairs of numbers that meet a specific criteria 
Share this thread: 
#1
Oct2911, 11:10 AM

P: 180

Hi,
I am struggling with this strange problem. I have to find pairs of positive integers that satisfy two specific conditions. 1. you can’t go from one pair to another by subtracting/adding the same number to both members of the pair. 2. You can’t go from one pair to another by subtracting/adding a number from one of the numbers in the pair. I have so far found the following pairs using a graph paper. Note that the order of the numbers in a pair is not important. (0,0) (1,2) (3, 5) (4, 7) (6, 10) (8, 13) I want to able to find say 100th pair. How should I go about doing this? Also, what branch of mathematics handles this kind of problems? Thanks. 


#2
Oct3111, 08:19 AM

P: 879

I would simply find the pairs in a bruteforce manner by writing a simple program in the language of your preference.
Is there any other condition for the pairs? Can you start from (3,194) for example, and start incrementing 3 and reducing 394? why do you seem to just be going up on both numbers? 


#3
Oct3111, 10:47 AM

P: 180

Thanks gsal.
I did think about using the bruteforce method, but before that I wanted to see if there was a more elegant solution. Thanks. Question cross posted at: http://mathforum.org/kb/thread.jspa?threadID=2310301 


#4
Oct3111, 04:33 PM

P: 879

Finding pairs of numbers that meet a specific criteria
The reason why I thought of starting with a pair where the two numbers are far apart and then simply increment one and reduce the other one is because this would intrinsically let you not have to worry about condition 1...am I correct?



#5
Oct3111, 09:18 PM

P: 180

gsal,
Sorry, I don't understand your logic. 


#6
Oct3111, 10:32 PM

P: 4

It looks a bit like the nqueens problem, to me.
Definition of the nqueens problem: Place n queens on an n*n chessboard so that no queen is on the same diagonal or in the same row or column as any other queen. The coordinate pts (x, y) you are choosing could represent a queen at the position (x, y) on a 100*100 chessboard. Adding/subtracting a number from both members of a pair is the same as moving the pair along a diagonal; and adding/subtracting a number from one member of a pair is the same as moving along a row or column. http://www.math.utah.edu/~alfeld/queens/queens.html 


#7
Nov111, 02:51 AM

P: 879

I was thinking that I might be able to break down condition 1 into two statements, like:
1.a you can’t go from one pair to another by subtracting the same number to both members of the pair. 1.b you can’t go from one pair to another by adding the same number to both members of the pair. But after reading dlh's post, which sounds like it is totally related, I realize that condition 1 may also include: 1. you can’t go from one pair to another by subtracting a number from of the members of the pair and adding the same number to the other one. Doing the latter would place the new pair on the same diagonal...diagonal from upperright to lowerleft... 


#8
Nov111, 10:04 AM

P: 180

Thanks gsal.
dlh, Yes, that is a similar problem. Thanks a lot. Is there any other way, other than the bruteforce, to solve such a problem? 


#9
Nov111, 07:34 PM

P: 4

musicgold, the usual way to solve it is to write a recursive program.



#10
Nov111, 08:05 PM

P: 879

I don't see this problem as being one to be solved with recursion...but I just may not see it.



#11
Dec1011, 05:23 PM

P: 3

Thanks!



#12
Dec1111, 06:21 PM

P: 1,396

However, if you start with (0,0), and then always take the lowest first number that's still available and then the lowest second number that's still available, it seem that the nth pair is: [tex] (\lfloor \phi n \rfloor, \lfloor (\phi+1) n \rfloor) [/tex] where [itex] \phi [/itex] is the golden ratio or [itex] \frac {1}{2} + \frac {\sqrt{5}}{2} [/itex] or 1.618034... and [itex] \lfloor x \rfloor [/itex] is x rounded down to the nearest integer. This sequence (the first number of the pairs) appears in the Online encyclopedia of integer sequences, http://oeis.org/A066096 but I didn't see this application. Still working on a proof by induction. It's correct up to n=100. 


Register to reply 
Related Discussions  
Help in Finding a Polymer that Satisfies Certain Physical Criteria  Materials & Chemical Engineering  3  
Proof: Infinitely many pairs of consecutive pprimeish numbers  Calculus & Beyond Homework  0  
A physics undergrad university with specific criteria for a SAM student  Career Guidance  1  
ARE integers ordered pairs of natural numbers:  General Math  4  
Find amicable pairs and perfect numbers  General Math  0 