[seqfan] Re: Minimum quantity of coins

[Harvey P. Dale]

	There is a Mathematica function that solves these sorts of problems quickly.  For example, to determine the minimum number of coins, of denominations 6 and 5, to pay 65 — Min[Total/@FrobeniusSolve[{5,6},65]].
	Best,
	Harvey
 


-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Giovanni Resta
Sent: Monday, June 8, 2015 11:29 AM
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: Minimum quantity of coins

On 06/08/2015 03:41 PM, Eric Angelini wrote:
>
> Hello SeqFans,
> To pay 12 with coins labelled 1 and 2 you'll need at least 6 coins (6 
> x "2" = 12); To pay 26 with coins labelled 2 and 6 you'll need at 
> least 5 coins (4 x "6" + 1 x "2" = 26); To pay 65 with coins labelled 
> 6 and 5 you'll need at least 11 coins (10 x "6" + 1 x "5" = 65); To 
> pay 511 with coins labelled 5 and 11 you'll need at least 47 coins (46 
> x "11" + 1 x "5" = 511); To pay 1147 with coins labelled 11 and 47 
> you'll need at least 29 coins (23 x "47" + 6 x "11" = 1147); To pay 4729 with coins labelled 11 and 47 you'll need at least 101 coins (100 x "47" + 1 x "29" = 4729); To pay 29101, etc.

The line that starts with "to pay 4929..." is wrong because you are using 47 and 11 instead of 47 and 29.

Said that, the first terms are
1, 2, 6, 5, 11, 47, 29, 101, 353, 497, 713, 785, 929, 857, 1001, 8705, 2297, 10001, 30665, 38009, 85313, 52697, 100001, 574265, 525737, 1000001, 5731625, 5268377, 10000001, 57415385, 52584617, 100000001, 573261545, 526738457, 1000000001, 5334993353, 5665006649, 9669986705, 5995019945, 10000000001, 63955179497, 46044820505, 100000000001, 514403384537, 585596615465, 928806769073, 656789846393, 1000000000001, 6911108617529, 4088891382473, 10000000000001, 46800022442249, 26399955115505, 100000000000001,...

apparently there is a sort-of pattern with terms of the form 10^k+1.

naive Mma code:
conc[x_,y_]:=FromDigits[Flatten[IntegerDigits/@{x,y}]];coins[x_,y_]:=Block[{a,b,r=Reduce[x*a+y*b==conc[x,y]
&& a>=0 && b>=0,{a,b},Integers]}, If[r===False,0, Min[a+b/.List at ToRules@r]]];
L={1,2};While[Length[L]<100 && Last[L]>0, AppendTo[L,coins[L[[-2]],L[[-1]]]]]; L

giovanni


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/