Register to reply

Finding pairs of numbers that meet a specific criteria

by musicgold
Tags: criteria, meet, numbers, pairs, specific
Share this thread:
musicgold
#1
Oct29-11, 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.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
gsal
#2
Oct31-11, 08:19 AM
P: 872
I would simply find the pairs in a brute-force 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?
musicgold
#3
Oct31-11, 10:47 AM
P: 180
Thanks gsal.

I did think about using the brute-force method, but before that I wanted to see if there was a more elegant solution.

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?
No there is no other explicit condition. However given the inherent structure ( every pair takes into account the pairs lower than it), I don't think you can start from (3, 194). I started from (0,0) because I felt it was an easy boundary given that we are not working with -ve integers.

Thanks.


Question cross posted at: http://mathforum.org/kb/thread.jspa?threadID=2310301

gsal
#4
Oct31-11, 04:33 PM
P: 872
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?
musicgold
#5
Oct31-11, 09:18 PM
P: 180
gsal,

Sorry, I don't understand your logic.
dlh
#6
Oct31-11, 10:32 PM
P: 4
It looks a bit like the n-queens problem, to me.

Definition of the n-queens 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
gsal
#7
Nov1-11, 02:51 AM
P: 872
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 upper-right to lower-left...
musicgold
#8
Nov1-11, 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 brute-force, to solve such a problem?
dlh
#9
Nov1-11, 07:34 PM
P: 4
musicgold, the usual way to solve it is to write a recursive program.
gsal
#10
Nov1-11, 08:05 PM
P: 872
I don't see this problem as being one to be solved with recursion...but I just may not see it.
Trisha07
#11
Dec10-11, 05:23 PM
P: 3
Thanks!
willem2
#12
Dec11-11, 06:21 PM
P: 1,395
Quote Quote by musicgold View Post
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.
Of course, there's more than one way to define the 100th pair.

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 n-th 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 pprime-ish 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