From: "John D'Errico" <>
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$>
References: <gfun9a$41t$>
Reply-To: "John D'Errico" <>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: 1227025503 23768 (18 Nov 2008 16:25:03 GMT)
NNTP-Posting-Date: Tue, 18 Nov 2008 16:25:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: comp.soft-sys.matlab:501471

"Oriole " <> wrote in message <gfun9a$41t$>...
> 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.