Prev: now open all blocked site with our proxy
Next: Compaq
From: deepakc on 3 Jan 2010 18:50
Respected Computer Scientists and Mathematicians,

The Frobenius Coin Problem asks whether some target monetary sum S can
be achieved using given coin denominations.

I have written a paper describing a bounded Rational Generating
Function, where the coefficient of x^i is 0, if and only if, the
monetary target of 'i' cannot be obtained using given coin
denominations.

I have my paper to ARXIV moments ago, and it should become live at
http://arxiv.org/abs/1001.0415 within 24 hours from now.

The basic idea of my paper, is that I give a Linear Recurrance
Relation, for E_i, the integer sequence representing the number of
ways that the given coin denominations may be arranged as a stack,
whose total monetary worth is 'i'. The Linear Recurrence Relation for
E_i is given by the following Theorem:

Let L be the largest of the given N coin denominations, and the binary
vector <B_1, B_2, …B_j, …B_L-1, B_L> be such that B_j is 1, if j is a
coin denomination, and 0 otherwise. Then the number of ways that coins
from the given denominations may be arranged as a stack, such that the
total monetary worth of the stack is equal to i, is given by the
following Linear Recurrence Relation for E_i
E_0 = 1, and,
E_i = B_L E_i-L + B_L-1 E_i-L+1 + …+ B_2 E_i-2 + B_1 E_i-1 when i is
an integer greater than 0, and,
E_i = 0 when i is an integer lesser than 0.

Please read my paper at http://arxiv.org/abs/1001.0415 for the
detailed proof, as soon as it becomes live.

l look forward to your expert comments and reviews of my paper.

Yours faithfully,
-Deepak
From: deepakc on 7 Jan 2010 10:24
I have the following 2 updates:

UPDATE-1: Today, I read about the Skolem-Mahler-Lech (SML) restriction
for Linear Recurrences. Please note that the SML restriction applies
to Linear Recurrences over the characteristic 0. My Theorem-1 on the
other hand, has the B vector defined such that the characterstic is
never 0, because element Bj is 1 if j is a coin denomination, and 0
otherwise. So the SML result does not restrict E_i in my paper to give
0 values over periodic intervals. Thus, Theorem-1 of my paper
continues to remain correct.

UPDATE-2: In the proof of Theorem-1, though I explained well on
obtaining the coefficient of any term in E_i, I am not sure whether I
explained well enough, on why E_i will contain all possible terms
involving B1^K1 B2^K2...BL^KL, such that values of K1 + 2K2 + 3K3 + ...
+ LKL = i. The reason is very simple: - Note that I stated that in the
proof that our assumption is that E_i-1, E_i-2...E_i-L contain all
possible stack formations. As a result of this assumption, it follows
that every term in E_t is a subset of some term in E_s, where t and s
are both integers and t < s < i. Hence, in order to reach from E_t to
E_i, it suffices to multiply E_t by B_i-t, and no need to multiply E_t
by sums of smaller denominations (example: No need to multiply E_t by
"B3+B4+B4", where 3+4+4 = i-t, because such terms will already be
coming to E_i from other routes, i.e. from E_(t+3) B8, from E_(t+7)
B4, and from E_(t+8) B3 ). I did not include this explanation, because
I felt that it was obvious from our assumption that E_i-1, E_i-2...E_i-
L contain all possible stack formations.

faithfully,
-Deepak
From: deepakc on 7 Jan 2010 14:29
> Hence, in order to reach from E_t to E_i, it suffices to multiply E_t by B_i-t,
> and no need to multiply E_t by sums of smaller denominations (example:
> No need to multiply E_t by "B3+B4+B4", where 3+4+4 = i-t

A small typo-error in my above post. The corrected sentence should
read as follows: Hence, in order to reach from E_t to E_i, it suffices
to multiply E_t by B_i-t, and no need to multiply E_t by products of
smaller denominations (example: no need to multiply E_t by "B3 B4 B4",
where 3+4+4 = i-t

So my Theorem-1 continues to remain correct.

faithfully.
-Deepak
From: deepakc on 8 Jan 2010 09:52
Hi All,

I have enhanced my explanations, and have created the second Version
of my paper available at the same site http://arxiv.org/abs/1001.0415

faithfully,
-Deepak
 | 
Pages: 1
Prev: now open all blocked site with our proxy
Next: Compaq