R = mX + b, S = nY + c ...

[NotLKH]

I'm wondering if any of you know a general method for the following: {I've developed one, Perhaps you've got a better way.}


How would you determine Integral values (X , Y) such that R = S, and R is the first such number >= 0, given m, b, n and c?

For example, lets say R = 11x₀ + 5, and S = 17y₀ + 3, determine x₀ and y₀ to produce the first R, S greater than 0, such that R = S.




-Lou

[RAEsquivelC]

Well, Lou, I’m not sure that what I show below meets your "general method" requirement, but, here’s what I arrived at:

Required conditions:
1) R = mx + b
2) S = ny + c
3) R = S
4) R >= 0 and S >= 0
All above values are integers.

Solution:
mx + b = ny + c This satisfies conditions 1), 2) and 3)
5) x = (ny + c – b)/a
By substituting appropriate values of y, obtain x.
Check for R >= 0.

Example:
R = 11x + 5
S = 17y + 3
By inspection of the first equation, x must be either 0 or positive for R >=0
By inspection of the second equation, y must also be either 0 or positive for S >= 0
The above two conditions satisfies condition 4).

By inspection, for x = 0 , R <> S, so x >0
Likewise, for y = 0, R <> S, so, y > 0

Substituing values in 5) above:
x = (17y + 3 – 5)/11, or,
x = (17y - 2)/11

Substituting successive values of y, 1 ,2, 3, …:
y=1
x=(17-2)/11 =15/11 <> integer, so, y = 1 is not a solution.

y=2
x=(17*2-2)/11 = 32/11 <> integer, so, y = 2 is not a solution

y=3
x=(17*3-2)/11 = 49/11 <> integer, so, y=3 is not a solution

y=4
x=(17*4-2)/11 = 66/11 = 6. R = 11*6 + 5 =
So, x=6, y-4 is the first solution, for the equations given, that satisfies conditions 1) through 4).

By the way, does NotLKH mean that the OP is Not LKH? If not, then, who is LKH? (Sorry, Lou, but I couldn't pass that one up).

[NotLKH]

Not Bad, but can you do it more deterministically?

For Example, attached is an image of how I do it:

[NotLKH]

Originally posted by RAEsquivelC
By the way, does NotLKH mean that the OP is Not LKH? If not, then, who is LKH? (Sorry, Lou, but I couldn't pass that one up).

[RAEsquivelC]

Does this meet your “more deterministic” idea?

Required conditions:
1) R = mx + b
2) S = ny + c
3) R = S
4) R >= 0 and S >= 0
All above values are integers.

Solution:
mx + b = ny + c 1) = 2) This satisfies conditions 1), 2) and 3)
5) x = (ny + c – b)/a
If n>a, obtain n = pa + q/a, where q/a is a proper fraction.
By substituting appropriate values of y, obtain x.
Check for R >= 0.

Example:
R = 11x + 5
S = 17y + 3
By inspection of the first equation, x must be either 0 or positive for R >=0
By inspection of the second equation, y must also be either 0 or positive for S >= 0
The above two conditions satisfies condition 4).

By inspection, for x = 0 , R <> S, so x >0
Likewise, for y = 0, R <> S, so, y > 0

Substituing values in 5) above:
x = (17y + 3 – 5)/11, or,
5) x = (17y - 2)/11, and
x = y + (6y – 2)/11

So, 6y – 2 = 11z
Substituting successive values for z = 0, 1 ,2, 3, …:
z=0, 6y = 2, y = 1/3, y is not an integer, so, not a solution
z=1, 6y = 13, y = 2 + 1/13, y is not an integer, so, not a solution
z=2, 6y = 24, y = 4, this is a solution!

Substituting y in 5):
x= (17*4 – 2)/11 = 66/11
x = 6

So, x = 6, y = 4 is the first solution, for the equations given, that satisfies conditions 1) through 4).

[NotLKH]

Originally posted by RAEsquivelC
...
Substituting successive values for z = 0, 1 ,2, 3, …:
z=0, 6y = 2, y = 1/3, y is not an integer, so, not a solution
z=1, 6y = 13, y = 2 + 1/13, y is not an integer, so, not a solution
z=2, 6y = 24, y = 4, this is a solution!
...

Substituting successive values of y, 1 ,2, 3, …:
y=1
x=(17-2)/11 =15/11 <> integer, so, y = 1 is not a solution.

y=2
x=(17*2-2)/11 = 32/11 <> integer, so, y = 2 is not a solution

Hmm, I just think this "test all numbers and see which one works" way is excessive computation.

[RAEsquivelC]

Lou, I do believe you read part of my latest (07/30/03 05:05 AM) post, which uses "z" for testing values in a simplified trial-and-error method, and, somehow, followed up with adding part of my original (07/29/03 08:19 PM) try at your posting, which makes my proposed solutions look worse than what they really are!
PLEASE re-read my 07/30/03 05:05 AM posting, and include quotes ONLY from that posting for comment. Thanks.

Now, as to testing for z=0, 1, 2, 3, ... Well, I did have to use z from z=0 to z=4 to find the solution...but, you had to substitute four times in much more complicated expressions before you could come up with the solution. I believe my method is simpler and easier, even if it took one more try than yours. However, I realize that you want "...a more methodical solution", and, you are certainly entitled to your opinion on your thread.

By the way, I hope you noticed the scarcity of solutions offered! Me, I looked at you original posting for various days, before I decided to give it a try. It took a little thinking to get going, as an attack method isn't all that obvious. Where in the world do you come up with these little treasures?

[NotLKH]

Where did I come up with this?

Well, I have a project that is going to use a very large range of numbers and hopefully find an arrangement satisfying some predifined conditions. There are many levels that could be explored, and each level's range of numbers vary from each other level, and as the index of each level increases, so does the range. For example, what I call "Level 5" must use 61 sequential numbers inclusively, While "Level 4" required only 37.

Sometime last year, I created a progie to spit out solutions for the "Level 5", but it took over an hour to find the very first one, in contrast to 10's of thousands for "Level 4" over the same timeframe.

I'm trying to optimize this, So I've developed a new strategy, useing Modular arithmatic.

Approximately Half of the numbers per level can be assigned as the result of an equation of the other numbers. I've decided to use Modular Arithematic, develop Modded equations for the prime numbers 2, 3, 5, etc.... which should allow me to build sub sets of the solutions Mod 2, Mod 3, etc...

So, useing the elements returned, I'll need to find where these solutions intersect with each other.

Now, many years ago, I developed the method to find the integral intersection of 2 sets of linear equations, but I never progied it. So, I recently whipped up a progy to do it, and it works great. But, I decided to see if anyone here had a method that exceed my humble attempt.

BTW, I included the portion from your first post just because of its similarity to that area in the second post, in terms of its "Trial and Error" approach.

BTBTW, Would you like to try the following:

41*X₀ + 23 = 71*Y₀ + 6

Attached is the return from my program:




-Lou

[RAEsquivelC]

For the case 41x +23 = 71y + 6, I got x = 197, y = 114, R = S = 8100. Not that I want to spend the rest of my life doing this sort of thing, unless I have a reason that I like for doing it. And, then I would probably proceed to create a program for the solution!

By the way, you mentioned a level 4 with 37, and a level 5 with 61. Hmm, I'm an Electrical Engineer, and, for "round" cross sections of stranded conductors, we have the number of strands as:

1) 1
2) 1+6=7
3) 1+6+12=19
4) 1+6+12+18=37
5) 1+6+12+18+24=61

Is the above 4) 37 and 5) 61 a mere coincidence with your Level 4 with 37 and Level 5 with 61???