Sums payable with change

[Robert Israel]

I get
1, 6, 33, 95, 188, 288, 388, 488, 588, 688, 788, 888, 988, 1088, 1188,...

It looks like for n >= 4, a(n) = 100 n - 212.  It should be possible
to prove this.  It seems that if B[n] is the number of
amounts payable with exactly n banknotes (allowing change), and
C[n] = B[n]\B[n-1], then C[n] = C[5] + 100 (n-5) where

C[5] = {33, 37, 63, 67, 73, 77, 83, 87, 113, 117, 123, 127, 128, 132, 134, 
136, 138, 142, 143, 147, 153, 157, 158, 162, 164, 166, 168, 172, 174, 176, 
178, 182, 184, 186, 188, 192, 193, 197, 203, 207, 208, 212, 214, 216, 218, 
222, 224, 226, 229, 231, 235, 239, 241, 244, 246, 248, 252, 254, 256, 259, 
261, 265, 269, 271, 275, 279, 281, 285, 289, 291, 294, 296, 298, 302, 304, 
306, 309, 311, 315, 319, 321, 325, 330, 340, 345, 349, 351, 355, 360, 370, 
380, 390, 395, 399, 401, 405, 410, 420, 450, 500}

Cheers,
Robert

On Tue, 19 Feb 2008, zak seidov wrote:

> Let both customer and seller have unlimited number of
> banknotes of DENOMINATIONs
> (not NOMINALs as they say in Russian!)
> 1, 5, 10, 20, 50, and 100.
>
> Using exactly THREE banknotes (no change in seller's
> cash, only customer pays),
> there are 52  payable in (A135137)
> 3,7,11,12,15,16,20,21,22,25,26,30,31,35,40,41,45,50,52,56,60,61,65,70,71,75,80,90,101,102,105,106,110,111,115,120,121,125,130,140,150,151,155,160,170,200,
> 201,205,210,220,250,300
>
> Additionally there are
> 43 sums payable with change:
> 0,1,4,5,6,8,9,10,14,18,19,24,29,39,44,46,48,49,51,54,55,59,69,79,81,85,89,91,94,95,96,98,99,100,104,109,119,145,149,180,190,195,199
> e.g., 1=1+1-1 (customer pays two and gets back one),
> 5=20-10-5  (customer pays 20 and gets back 10 and 5),
> 109=100+10-1 (customer pays 100+10 and gets back 1).
>
> Hence there are 52+43=95 sums payable  using exactly
> THREE banknotes in the deal
> (i.e. with change allowable).
>
> In the case of TWO banknotes there are 33 payable
> sums:
> 0, 2, 4, 5, 6, 9, 10, 11, 15, 19, 20, 21, 25, 30, 40,
> 45, 49, 50, 51, 55,60, 70, 80, 90, 95, 99, 100, 101,
> 105, 110, 120, 150, 200.
>
> In the case of ONE banknote there are 6 payable sums
> (no change as only ONE banknote available):
> 1,5,10,20,50,100.
> Finally with ZERO banknote only one sum is possible,
> namely zero.
> Hence, the beginning of new suggested sequence is:
> a(0)=1, a(1)=6, a(2)=33, a(3)=95.
> Can anyone check/extend this?
> thanks, zak
> Cf. A124146, A135137, A135454
>
>
>      ____________________________________________________________________________________
> Be a better friend, newshound, and
> know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
>