Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Integer solutions for a_1*x_1+a_2*x_2+a_3*x_3+ ...+a_4*x_n = k
Date: Tue, 18 Nov 2008 16:25:03 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 31
Message-ID: <gfuq8v$n6o$1@fred.mathworks.com>
References: <gfun9a$41t$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1227025503 23768 172.30.248.35 (18 Nov 2008 16:25:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 18 Nov 2008 16:25:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:501471

"Oriole " <oriole_ni@hotmail.com> wrote in message <gfun9a$41t$1@fred.mathworks.com>...
> Hello, 
> 
> I am wondering how to write a function for solving
> 
> a_1*x_1+a_2*x_2+a_3*x_3+ ...+a_4*x_n = k
> 
> where
> Inputs: 
> n, k, and vector of non-negaive integer coefficients a=[a_1, a_2, ...a_n].     
> k is some small positive integer, for example, k= 3, or k= 6, n is rather large positve integer, for example,, n = 20, or n= 60 or in some rare cases even n=100.
> 
> Output:
> The unknowns x_1, x_2, ...x_n are non-negative integers.
> 
> I have asked a simplier version of this problem here, where a=[1, 1, ...1], and got lots of help from Walter, Bruno, Roger, John (thank you). 
> 
> But this problem... seems really difficult,  is it even possible to solve it in Matlab? Any ideas?
> 
> Thank you for your help!
> Oriole

This is a Diophantine equation, as is the partitions
problem, which is just a special case of the
general Diophantine equation.

For n very large, this is a nasty problem. You can still
solve it recursively as we have shown you, but that
may be computationally expensive.

John