Finding solution to distinct value table

[johnkubik]

Hey everyone!

If you have a table that has distinct values for each x,y pair how would you determine the x,y values from the table?

eg...
*table formatting is not working out for me, I am sure you can look at it and see what I was aiming for*


y
4 | 9 36 54 72 90

3 | 7 28 42 56 70

2 | 5 20 30 40 50

1 | 3 12 18 24 30

0 | 0 4 6 8 10
--------------------------------------------
0 - 1 - 2 - 3 - 4 - x

If I said... what is the x,y pairing of 70, how would you solve that mathematically?

The equation here is (x*2+2)(y*2+1)=z, right?

So, if you have z=70 you would have 4*x*y +2x+4y+2=70.

Understandably, there would be duplicate values if the table go larger (y=2, x=8, z=20 same as (y=2, x=1, z=20)... I am more so concerned with the set of numbers that is unique.

That being said: is it guess and check? Or do you HAVE to know 2 out of 3 (z and x, or z and y) of the variables?

 

[Mark44]

Hey everyone!

If you have a table that has distinct values for each x,y pair how would you determine the x,y values from the table?

eg...
*table formatting is not working out for me, I am sure you can look at it and see what I was aiming for*


y
4 | 9 36 54 72 90

3 | 7 28 42 56 70

2 | 5 20 30 40 50

1 | 3 12 18 24 30

0 | 0 4 6 8 10
--------------------------------------------
0 - 1 - 2 - 3 - 4 - x

Is there a typo in the row where y = 0? All the other rows have a certain pattern. If the first number in that row were 1, then each row above is some multiple of that row.

If I said... what is the x,y pairing of 70, how would you solve that mathematically?

The equation here is (x*2+2)(y*2+1)=z, right?

So, if you have z=70 you would have 4*x*y +2x+4y+2=70.

Understandably, there would be duplicate values if the table go larger (y=2, x=8, z=20 same as (y=2, x=1, z=20)... I am more so concerned with the set of numbers that is unique.

One value, 30, already is duplicated in the table. Any method that would give you a row and column would give you two sets of results for this value.

That being said: is it guess and check? Or do you HAVE to know 2 out of 3 (z and x, or z and y) of the variables?

 

[johnkubik]

Shoot, you are right... I meant to remove any duplicate values. But, even with the duplicate values what would be the method to solve for it?

And yes, typo at y=0, x=0... it should be 2.

I am at a conceptual block when it comes to understanding the methodology behind knowing what x,y pair correspond to which z in a table like this. (if there are duplicate numbers does that change the solution?)

The question still stands, if I know the z how do I get the x and y.



Thank you for your response!

 

[Mark44]

Shoot, you are right... I meant to remove any duplicate values. But, even with the duplicate values what would be the method to solve for it?

And yes, typo at y=0, x=0... it should be 2.

Shouldn't it be 1 in that position? In every other row, the pattern is
N 4N 6N 8N 10N, where N is the first number in that row.

If the bottom row were
1 4 6 8 10, the pattern would be preserved.

I am at a conceptual block when it comes to understanding the methodology behind knowing what x,y pair correspond to which z in a table like this. (if there are duplicate numbers does that change the solution?)

That was exactly my point. Since 30 appears in two rows, it is not possible to get a unique pair of values (x, y) for that value. So do duplicates change "the solution?" Yes, because there will be two pairs of (x, y) values that map to 30.

The question still stands, if I know the z how do I get the x and y.
Thank you for your response!

 

[jbriggs444]

Given the formula that you came up with [ (2x+2)(2y+1) ] the x=0 column is all wrong.

If you correct that error then look at the y=0 row. That row contains all of the positive even numbers.

Now look at the rest of the table. Even numbers everywhere. Every entry in your table is a duplicate of an entry in the first row. So the solution is simple: set y=0 and solve for x in terms of z.

 

[johnkubik]

Thank you for the reply.

Does setting y=0 and solving for x in terms of z mean that I have to just try every number over the range z=m to n? Or is there an easier way to determine what the answer would me?

 

[jbriggs444]

Does setting y=0 and solving for x in terms of z mean that I have to just try every number over the range z=m to n? Or is there an easier way to determine what the answer would me?

Algebra.

Start with z = (2x+2) * (2y+1)

Now assume that y=0. Substitute "0" into that equation where "y" was.

Simplify the resulting equation so that you have z in terms of x.

Now rearrange that equation so that you have x in terms of z.


A slightly different way to approach the problem is to start with z = (2x+2) * (2y+1)
Divide by 2
Now you have z = (x+1) * (2y+1)

Where you are taking x and y to be non-negative integers.

Now do a change of variables

i = x+1
j = 2y+1

So that the equation is now z = i * j

Where i is a positive integer and j is a positive integer that is odd.

The problem now becomes:

Factor z into i and j such that j is odd.

The simple solution is to take i = z and j = 1. [Determining x and y given i and j is an exercise left for the reader]

The harder problem is to find all solutions for a given z. That's (almost) integer factorization and is a well-researched and difficult problem.

 

[johnkubik]

Thank you for that response. Very well written.

The only problem I have conceptually is that if it is a unique value table, with each x,y pair having a unique z (and, although, the table I provided is not unique can we operate under the premise it is) how are we not able to say, ok... z is some value, and we know that value is a unique value in this table, here is the location and the subsequent x,y pair.


I just don't understand.

If you have a unique table, and are given a z, how do you get the x,y?

 

[jbriggs444]

The only problem I have conceptually is that if it is a unique value table, with each x,y pair having a unique z (and, although, the table I provided is not unique can we operate under the premise it is) how are we not able to say, ok... z is some value, and we know that value is a unique value in this table, here is the location and the subsequent x,y pair.

So you are thinking of a table that is entirely arbitrary and which may or may not be generated according to some fixed formula. And you want a scheme by which one can do a "reverse lookup" and find an object's position in the table based on its value.

This is a fairly common application in computer science. Versions show up in things like "content addressible memory" and "google".

Warning: I'm no guru on this stuff. The state of the art is well beyond what I know of.

If you want to do this efficiently, you need details. How many values are in the table? How cheap is memory? How fast do you need to retrieve values from the table? How often do you need to retrieve values from the table? How cheap is memory? How cheap are more processors? How much time can you afford to spend building an index? How often will the indexed data be changed? How much locality of reference can be expected?

Techniques that can be used include:

Unordered lists (accessed with sequential search)
Sorted lists (accessed with a binary search)
Height-balanced binary trees (accessed with a binary search)
B-trees (accessed with a tree search).
Hash tables.

The general problem is of some interest in crypotography -- find a function f() such that given an input x there is an efficient algorithm to compute f(x) but given an output f(x) there is no easy algorithm to compute input x. This class of functions would include cryptographic hash functions such as MD5 and SHA.

Or, find a function f(k,p) such that given an input p and key k it is easy to compute f(k,p) and given an input f(k,p) and key k it is easy to compute p but given an output f(k,p) and an input p it is difficult to compute k. This class of functions would include ciphers such as AES.