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