Check out Gomory's Cutting Plane Method for integer linear programming: http://en.wikipedia.org/wiki/Cutting-plane_method You may not be able to tell from the description above, but if you do this in 2 dimensions, you will find that you are doing the same calculation as a continued fraction. At 10:44 AM 9/16/2008, Christian Boyer wrote:

Bonjour Henry,

Ooops, sorry, I saw your answer after those from Dan and Victor. Yes, my problem is close to these other problems.

Christian.

-----Message d'origine----- De : Henry Baker [mailto:hbaker1@pipeline.com] Envoyé : mardi 16 septembre 2008 16:42 À : Christian Boyer Cc : 'math-fun' Objet : Re: [math-fun] Equation mixing integers and reals

Isn't this similar to the "integer linear programming" problem (integer version of linear programming problem) ?

It looks like you may be able to reduce this to some sort of knapsack problem.

Of course, there's always the issue of how to represent the "reals" in this problem.

At 06:42 AM 9/16/2008, Christian Boyer wrote:

...

Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n

where k , k , ..., k are n REAL constants 1 2 n

and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n

If we try to have the best possible approximations of

f(x , x , ... x ) = 0 1 2 n

do you know good algorithms giving best values of (x , x , ..., x )? 1 2 n

When n = 2, a good algorithm is to compute the continued fraction of k / k 2 1 At each step of the algorithm, the continued fraction will give more and more excellent (x , x ). 1 2

But which algorithm(s) for n > 2?

Christian.