tag:blogger.com,1999:blog-6555947.post111661351276481571..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Chickens and PrimesSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-6555947.post-1133702186274777142005-12-04T06:16:00.000-07:002005-12-04T06:16:00.000-07:00Ciao Suresh ! Non potevi esprimere meglio il tuo p...Ciao Suresh ! Non potevi esprimere meglio il tuo pensiero riguardo a Chickens and Primes . Complimenti per il tuo blog, รจ davvero bello! Continua a tenerlo aggiornato! Se ti va di visitare il mio sito che riguarda scommesse clicca su questo link: qui troverai solo <A HREF="http://www.giochi-scommesse.com" REL="nofollow">scommesse</A> !Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117220038212185392005-05-27T12:53:00.000-06:002005-05-27T12:53:00.000-06:00The general problem given n positive integers a_1,...The general problem <BR/><BR/>given n positive integers a_1, a_2, ..., a_n whose gcd is 1, find the largest integer which cannot be written as a nonnegative integer combination of them<BR/><BR/>is known as the Frobenius problem. It is also known as the coin problem (what is the largest amount you can't make change for). <BR/><BR/>There is no simple formula known for n > 3. If n is part of the input, the problem is NP-hard. Ravi Kannan gave a <A HREF="http://www.cs.yale.edu/homes/kannan/Papers/frobenius.pdf" REL="nofollow">non-trivial polynomial-time algorithm for fixed n</A> (polynomial in the number of bits used to represent the a_i). <A HREF="http://mathworld.wolfram.com/CoinProblem.html" REL="nofollow">MathWorld</A> has some more information. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>David ApplegateAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116980817906010962005-05-24T18:26:00.000-06:002005-05-24T18:26:00.000-06:00Given positive integers a, b, ..., z whose gcd is ...Given positive integers a, b, ..., z whose gcd is 1. It is not hard to show that all sufficiently large n can be written as an integral non-negative linear combination of a, b, ..., z<BR/><BR/>Do you guys know of a formula computing the largest n which cannot be written that way? <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116652443217869242005-05-20T23:14:00.000-06:002005-05-20T23:14:00.000-06:00An email from Nick Reingold Hi Suresh,The pro...<I>An email from Nick Reingold</I> <BR/>Hi Suresh,<BR/><BR/>The problem at your blog is very classical. Here's one approach:<BR/><BR/>Consider 0*B, 1*B, 2*B, ..., (A-1)*B. Since (A,B)=1, these are distinct<BR/>(mod A). Take N>(A-1)*(B-1)=(A-1)*B-A+1. Suppose that N=j*B (mod A),<BR/>with 0<=j<=A-1. If N<j*B then N+A<=j*B<=(A-1)*B, so N<=(A-1)*B-A,<BR/>which is impossible. So N>=j*B, and so can be written as k*A+j*B for<BR/>some k>=0.<BR/><BR/>On the other hand, (A-1)*B-A clearly cannot be written this way.<BR/><BR/>Thus f(M)=(A-1)*(B-1).<BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Nick ReingoldAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116628225317909492005-05-20T16:30:00.000-06:002005-05-20T16:30:00.000-06:00Another interesting version is how many can't you ...Another interesting version is how many can't you represent as such. In particular this is the coin exchange problem. If you had coins of denomination A and B, which is the largest number you can't change and how many can't you change? How about if you had k denominations?<BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116622406460556252005-05-20T14:53:00.000-06:002005-05-20T14:53:00.000-06:00ok. there is an elementary proof that is a bit str...ok. there is an elementary proof that is a bit stronger. the answer is AB - A - B, which is slightly stronger than what you propose. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116622245427856532005-05-20T14:50:00.000-06:002005-05-20T14:50:00.000-06:00One of the consequences of CRT I remember learning...One of the consequences of CRT I remember learning is that any integer can be expressed as pA + qB. Only, p and q may be negative. So, do some futzing around mod AB, and you can show that so long as N > AB - max(A,B) you can make both p and q non-negative.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>GrahamAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116620586871529262005-05-20T14:23:00.000-06:002005-05-20T14:23:00.000-06:00how ? Posted by Sureshhow ? <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1116620270961571752005-05-20T14:17:00.000-06:002005-05-20T14:17:00.000-06:00Doesn't this follow almost directly from the Chine...Doesn't this follow almost directly from the Chinese Remainder theorem?  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>GrahamAnonymousnoreply@blogger.com