Sums payable by exactly n banknotes.

[Maximilian Hasler]

There's not much more to add...
Below is a PARI script that prints out, for given n, the set of
possible sums, and also those sums which are obtained in 2 or more
different ways. By suppressing the  "print" commands and the
"if(...#", the function will only give the result.
(Of course not very efficient.) You can also give as second parameter
another set of amounts for the bills.
Maximilian

A1(n,m=[1,5,10,20,50,100],S=[],t)={
forvec(v=vector(#m-1,i,[0,n]), if( #S+0==#
S=setunion( S, [t=v[1]+m[#m]*(n-v[#v])+sum(i=2,#v,m[i]*(v[i]-v[i-1]))])
,print(t))
,1); print(vecsort(eval(S))); #S}

e.g.:
(13:05) gp > A1(3)
120
110
60
30
[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]
%2 = 52

On Feb 16, 2008 11:59 AM, zak seidov <zakseidov at yahoo.com> wrote:
> Dear Neil, seqfans,
>
> 1) can anyone check/extend these figures?
> 2) what about case n => inf?
> 3) is this worth submitting?
>
> thanks, zak
>
>
> %N A1 Number of sums payable by exactly n banknotes of
> nominals 1,5,10,20,50,100.
>
> %S A1 6, 15, 52, 103, 174, 262, 360, 461, 561, 660.
>
> %e A1
> n=1: 6 payable sums are 1,5,10,20,50,100;
> n=2: 15 sums are 2,6,10,11,15,20,21,25,30,40,51,
> 55,60,70,100;
> n=3: 52 sums are in A135137;
> n=4: 103 sums are:
> 4,8,12,13,16,17,20,21,22,23,25,26,27,30,31,32,35,36,40,41,42,45,46,50,51,53,55,57,60,61,62,65,66,70,71,72,75,76,80,81,85,90,91,95,100,102,103,106,107,110,111,112,115,116,120,121,122,125,126,130,131,135,140,141,145,150,151,152,155,156,160,161,165,170,171,175,180,190,200,201,202,205,206,210,211,215,220,221,225,230,240,250,251,255,260,270,300,301,305,310,320,350,400.
>
>
>
>       ____________________________________________________________________________________
> Be a better friend, newshound, and
> know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
>
>