[seqfan] Re: Minimum quantity of coins

[Giovanni Resta]

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