Is this an integer programming problem?

[rumborak]

At work I am writing a somewhat complex piece of software, and inside it at some point I have to solve the following problem:

I have several "streams", each of which has equally spaced points according to a proportionality factor 'a', i.e. X=a*n. Each stream has a different 'a'.
As an example:
Stream 1, a = 1.5: X = 0, 1.5, 3, 4.5 etc
Stream 2, a = 1.0, X = 0, 1, 2, 3 etc
Stream 3 ...

The question to solve: is there a value X that is a valid point for all streams, other than the trivial 0?
This problem strikes me as integer programming, but I have no good idea how to go about it, short of brute force.

 

[Mentallic]

To get a value of X that will be valid for all streams, you'll first need to multiply the value of 'a' in each stream by a sufficient integer such that the result is an integer if 'a' happens to not be an integer itself. Once you've done that for all streams, then multiply all the resulting values from each stream together. In your example, since a₁ (a in stream 1) is 1.5, then multiplying that by 2 gives us 3, and since a₂ is already an integer, we calculate that X=3*1=3 will be in both streams. Extending your example such that a₃=7.25, then multiply that by 4 to give 29 and hence X=3*1*29=87 will be found in all streams.

 

[rumborak]

Hmm, that's an interesting idea (and somehow it feels similar to Common Denominator calculation), but sadly my example used simple values for 'a' for illustrative purposes, not because they are actually constrained to it.
So, the 'a's should be considered real numbers, e.g. 1.7853467 etc. Maybe I'm not seeing it, but I don't think your method would work for those, as it seemed to rely on the easy "integerizability" of the a values.

 

[Mentallic]

For more complicated decimals, to "integeralize" it, you just need to convert it into a fraction and multiply by the denominator.

1.73853467=\frac{173853467}{100000000}

and hence

1.73853467\times 100000000=173853467

 

[jbriggs444]

So, the 'a's should be considered real numbers, e.g. 1.7853467 etc.

If any pair of a's has a ratio that is irrational then there can be no non-zero integer multiple of one that can also be an integer multiple of the other.

 

[fresh_42]

If any pair of a's has a ratio that is irrational then there can be no non-zero integer multiple of one that can also be an integer multiple of the other.

Yes, but in programming you will always have finitely many digits. Irrationals cannot occur explicitly, so they will always look like those in post #4.

 

[jbriggs444]

Yes, but in programming you will always have finitely many digits. Irrationals cannot occur explicitly, so they will always look like those in post #4.

Agreed, but that just pushes the problem back. Any instance of the problem that can be successfully input into the computer using a's presented as finite decimal strings can be solved. But not every solvable instance of the problem can be input into the computer using finite decimal strings.

 

[Merlin3189]

Now you've soled the op, can I just ask a little BTW?

If any pair of a's has a ratio that is irrational ...

Is that the same as saying, if any a is irrational?
Or is there some other way of getting an irrational ratio?

 

[jbriggs444]

Is that the same as saying, if any a is irrational?
Or is there some other way of getting an irrational ratio?

$\pi, \frac{\pi}{2} and \frac{3\pi}{7}$ are all in rational ratios with one another despite all being irrational.

But yes, if one were to trivially re-scale the problem so that $a_1 = 1$, "if any pair of a's has a ratio that is irrational" would be equivalent to saying "if any [rescaled] a is irrational".

 

[rumborak]

Thanks everybody. While (as it so often is) it didn't "solve" my programming problem, it definitely made me understand the problem space much better now.